The Collatz Conjecture can be summarized as follows - Take any positive integer n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start
with, you will always eventually reach 1. The property has also been
called oneness - Wikipedia
So, for starters, i decided to write a program that will compute the Collatz sequence for a 64 bit number i.e. from 0 to 18,446,744,073,709,551,615 which equals 264 − 1. After reaching the end of the cycle for a given number the program prints out the number N and the length of the cycle S. However, it does not print every cycle length, it only prints the next cycle that is greater than the previously computed cycle length.
The above code was compiled using gcc with full optimization. The executable was run on a 3.0 GHz Core i7 Quad with 8 GB RAM. The process priority was changed to SCHED_RR using the chrt command. It took the machine two weeks to generate the output shown below. The largest cycle sequence we were able to compute was 1428 for the 13 digit number shown. In the next part of this article i shall be posting details about running the same code on my NVidia GPU using CUDA along with some insane optimizations.
Oh, and there is also a short-film on the Collatz Conjecture...
No comments:
Post a Comment