Collatz 猜想的机器化验证及其优化

前言

Collatz 猜想非常简单,任何一个掌握加减乘除的小学生都能明白,然而,它却是本世纪最困难的几个数学问题之一,本页的 banner 几乎就是其猜想的全部内容,完整的描述是:对于非 0 自然数,若它是一个偶数,将它除以 2,若它是一个奇数,将它乘 3 之后加 1,对于得到的数一直这样操作,最后都会陷入 4 -> 2 -> 1 的循环。试试来证明或者证伪它吧,说不定会获得菲尔兹奖呢(笑)。华裔数学家 Terence Tao 使用解析的方法解决了这个问题的 “99%“,有兴趣了解的可以参见论文

基本实现

运行环境:

CPU: i7-9700K 4.5GHz

RAM: 8GB x 2 3600MHz

思路很简单不用多说,不过有一个情况需要注意一下,比如对于 7 这个数,对其进行运算之后得到的链是 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 4 -> 2 -> 1,显然,这个链中出现的所有的数都不需要再进行验证了,于是我们可以用一个集合把它们存起来用于验证以提高程序性能。

程序的要求是从命令行接收一个数 max,验证区间 [1, max] 内的所有自然数是否都符合猜想。

use num_bigint::{BigUint, ToBigUint};
use num_integer::Integer;
use num_iter::range;
use num_traits::One;
use std::collections::HashSet;
use std::env;
use std::ops::Shr;
use std::time::Instant;

fn main() {
    let args = env::args().collect::<Vec<_>>();
    if args.len() != 2 {
        panic!("Should accept one maximum value");
    }
    let max = args
        .last()
        .unwrap()
        .parse::<u32>()
        .unwrap()
        .to_biguint()
        .unwrap();
    if verify(max.clone()) {
        println!("The numbers in the range 1 to {} agree with the guess", max);
    } else {
        println!("WTF");
    }
}

fn verify(max: BigUint) -> bool {
    let mut verified = [1, 2, 4]
        .iter()
        .map(|t| t.to_biguint().unwrap())
        .collect::<HashSet<_>>();

    let now = Instant::now();
    let mut current: BigUint = One::one();
    while current <= max {
        let mut target = current.clone();
        if verified.contains(&target) {
            target += 1_u32;
        } else {
            while verified.insert(target.clone()) {
                if target.is_even() {
                    target = target.shr(1);
                } else {
                    target = target * 3_u32 + 1_u32;
                }
            }
        }
        current += 1_u32;
    }
    let elapsed = now.elapsed().as_secs_f64();
    println!("{}s", elapsed);

    let test_set = range(One::one(), max + 1_u32).collect::<HashSet<_>>();
    test_set.is_subset(&verified)
}

Cargo.toml

[package]
name = "collatz_conjecture"
version = "0.1.0"
edition = "2018"


[dependencies]
num-bigint = "0.4"
num-iter = "0.1.42"
num-integer = "0.1.44"
num-traits = "0.2.14"

优化性能

先试一个小点的数吧,1000_0000 好了

Collatz conjecture benchmark 1

看起来有点慢,可能是因为没上优化?先来几个唾手可得的:

Cargo.toml

[profile.release]
lto = true
codegen-units = 1
panic = "abort"

.cargo/config.toml

[target.x86_64-pc-windows-msvc]
rustflags = ["-C", "target-cpu=native"]

再跑三次看看

Collatz conjecture benchmark 2

不能说完全相同,只能说毫无变化(笑),看来优化的方向不太对,不过这么做倒也有益无害了,可以尝试从下面几个角度考虑

注意到我们使用 BigUint 来表示数,这样做的目的是防止潜在的 overflow 错误,然而 BigUint 内部是一个 Vec,所以如果要验证的数字越大,并且假设它没有在验证其他数的时得到的链中出现过,那么验证它所得到的链会很长,此时堆分配带来的性能损失就较为可观了。一个简单的想法是,我们换一个堆分配器看看情况,例如使用 mimalloc

Collatz conjecture benchmark 3

可以说是立竿见影了,性能一下提升了 20% 左右。

  • 并行

提高性能时,最容易想到的策略就是并发或者并行了。熟悉 Rust 的读者可能会想到 rayon,基于上面的堆分配方案来试试看。

此处只展示函数 verify() 的代码

fn verify(max: BigUint) -> bool {
    let verified = Mutex::new(
        [1, 2, 4]
            .iter()
            .map(|t| t.to_biguint().unwrap())
            .collect::<HashSet<_>>(),
    );

    let now = Instant::now();
    let all = range(One::one(), max.clone() + 1_u32).rev().collect::<Vec<_>>();

    all.into_par_iter().for_each(|t| {
        let mut verified_lock = verified.lock();
        let mut current = t.clone();
        while verified_lock.insert(current.clone()) {
            if current.is_even() {
                current = current.shr(1);
            } else {
                current = current * 3_u32 + 1_u32;
            }
        }
    });
    let elapsed = now.elapsed().as_secs_f64();
    println!("{}s", elapsed);

    let test_set = range(One::one(), max + 1_u32).collect::<HashSet<_>>();
    let result = test_set.is_subset(&*verified.lock());
    result
}

结果

Collatz conjecture benchmark 4

大出所料,甚至更慢了!这是为什么呢,程序的正确性是没有问题的,这是因为若要开始验证一个数是不是符合猜想,就必须要获得已验证过的集合的锁,所以在同一时刻,其实只有一个线程在运行,其他线程都在等待获取锁,解决的办法是,我们不使用验证集合这个技巧,接着改代码。

fn verify(max: BigUint) {
    let verified =
        [1, 2, 4]
            .iter()
            .map(|t| t.to_biguint().unwrap())
            .collect::<HashSet<_>>();

    let now = Instant::now();
    let all = range(One::one(), max.clone() + 1_u32).rev().collect::<Vec<_>>();

    all.into_par_iter().for_each(|t| {
        let mut current = t.clone();
        while !verified.contains(&current) {
            if current.is_even() {
                current = current.shr(1);
            } else {
                current = current * 3_u32 + 1_u32;
            }
        }
    });
}

结果

Collatz conjecture benchmark 5

这才是多线程该有的威力嘛,但是验证集合的优化足够给力,所以没有出现多线程的性能是单线程性能的 8 倍这样的情况。

但是,我们还可以更进一步,正如之前在堆分配那里提到的,如果不使用 BigUint,将节省掉大量的的频繁管理内存的时间,但是由于目前无法估计链中数的上界,所以对于广泛性的验证来说是 unsound 的。

有趣的是,当以 1000_0000 为基时,单线程和多线程差别不大。

多线程版本
单线程版本

1_0000_0000 为基时,多线程才能领先。

Collatz conjecture benchmark 8

源代码:TENX-S/collatz_conjecture

版本控制

Version Action Time
1.0 Init 2021-09-28
1.1 Fix typo 2021-09-28
1.2 Fix typo 2021-09-28
1.3 Revise the wording 2021-09-30