[tdoyjpic] Testing the Collatz conjecture on 10-million-bit numbers

tl;dr: No counterexamples to the Collatz conjecture were found.

Assume the Collatz conjecture is false; that is, there exist starting numbers which do not end in the 4-2-1 cycle.

Further major assumption: these counterexamples become much more numerous for larger integers; the reason the Collatz conjecture has seemed true in the range that it has been verified so far is because of the Strong Law of Small Numbers.

Then, we might be able to find counterexamples simply by testing some random large starting numbers.  One problem: when testing a number, how can one tell if it is a counterexample, not headed to a 4-2-1 cycle?  How can one tell if one has iterated enough?

Simple practical solution: start by testing small random numbers and gradually increase the size.  The smaller numbers will all reach 4-2-1, and the number of iterations and computation time can be recorded for each of them.  As the numbers get larger, the number of iterations and computation time will increase sort of smoothly.  If we encounter a number which is taking much longer than the extrapolation of the trend seen thus far, then we know something weird is going on with it.

We tested random starting numbers as large as 10313058 bits, the last one taking 74494956 iterations over 12 hours of computing time (though it was not very optimized code).  Every number tested converged to 4-2-1.

Source code in Haskell and logs.

We wish we had SIMD accelerated (e.g., GPU) small*large arbitrary precision multiplication (previously mentioned) to compute 3*x for large x.  x/2 could also be accelerated with SIMD.  x+1 will only astronomically rarely overflow the least significant limb.

Previous similar attempt, which was much slower because then large integers were represented as lists of Bool.