Optimizing the collatz conjecture

[kittech]

I'm trying to optimize this code so the u64::MAX is computable in reasonable time.
The only best optimization i could come up was multi thread the searching by using rayon and if the number is powers of 2 to minimize the time.
The code:

use rayon::iter::IntoParallelIterator;
use rayon::iter::ParallelIterator;

const fn calculate(start: u128) -> (u128, u32) {
    let mut val = start;
    let mut steps = 0;

    'calculation: loop {
        if val == 1 {
            break 'calculation (start, steps);
        }

        if (val & (val - 1)) == 0 {
            steps += val.ilog2();
            break 'calculation (start, steps);
        }

        val = if val % 2 == 0 { val / 2 } else { val * 3 + 1 };
        steps += 1;
    }
}

fn test_u32() -> (u128,u32) {
    let val = u32::MAX as u128;
    (1..val).into_par_iter()
        .filter(|x| x & (x - 1) != 0)
        .map(calculate)
        .max_by_key(|a| a.1)
        .unwrap()
}

fn test_any(num: u128) -> (u128,u32) {
    calculate(num)
}

fn main() {
    assert_eq!(test_u32(), (2610744987,1050));
    assert_eq!(test_any(32), (32,5));
}

[kpreid]

I'm trying to optimize this code so the u64::MAX is computable in reasonable time.

u64::MAX is a huge number, and you cannot really do anything with that many values in a reasonable amount of time on a single computer.

Let's suppose you have a ludicrously fast computer that has:

• 32 cores,
• a 10 GHz clock,
• and a SIMD arithmetic instruction that increments 16 integers during one clock cycle.

Then to run a program that just counts from 0 to u64::MAX — doesn't do anything else, just counts, and doesn't even know when to stop — would take

(2 ^ 64) / (10 GHz) / 16 / 32 = 41.7 days

to reach the end. And when you want to do actual computation with each one of these u64s, you'll have to multiply that entire time by the number of clock cycles each execution of calculate() takes.

[kittech]

But even if that would be way too much time, do you know how could i at least make it faster for u32::MAX and slightly bigger numbers?
Also i would consider myself a beginner in rust, i just wanted to know if it is possible

[quinedot]

The records through 63 bits are known, so for those cases you could just use a lookup table .

See also the technical details page (class records algorithm section) for some ways you could speed up the calculation by skipping numbers that can't be records.