Skip to content

Highly optimized rust program to find the number with the largest steps from 1 to n following the collatz conjecture

Notifications You must be signed in to change notification settings

kaitlek/collatz-optimized

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Collatz-optimized

Finds number N which took the largest steps to reach 1 following the collatz conjecture

~130x faster than original C collatz conjecture programs!

pub fn compute(mut input: u64) -> u64 {
    let start: u64 = input - 1;
    input *= input & 1;
    
    let mut count: u64 = 0;

    while input > 1 {
        count += 1;
        input *= start.wrapping_sub(input) >> 63;
        let m: u64 = (input & 1) ^ 1;
        input = m * (input >> 1) + (m ^ 1) * ((input * 3 + 1) / 2);
    }

    count
}   

Traditional C program to check stopping time checking numbers 1 - 100000000

Time taken: 47.14 seconds.
Found largest: 949 (#63728127)

Collatz-Optimized checking numbers 1 - 100000000

>>> Found largest: 949 (#63728127)
>>> Took 0.355 s to compute

Simply run with

cargo run --release {num}

Inspired and checked with this article

About

Highly optimized rust program to find the number with the largest steps from 1 to n following the collatz conjecture

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages