Friday, September 06, 2013

About 3x+1, hash table scavenging

Regarding the ongoing work on the 3x+1 program I talked about here, I set up a generational scavenger of sorts for the hashed table used during the T^k(r) sieve calculation.  This strategy assumes the sieve gaps will be relatively small compared to the sieve size, so you only need a comparatively few recent j, T^k(r) pairs to detect all paths that join.  With this new algorithm, I calculated the following 2^32 and 2^33 sieve approximations using no more than 1gb of RAM.

  • 2^32 sieve: gap >= 11102 (e.g. 2661008385), skip rate 92.617%.
  • 2^33 sieve: gap >= 11102 (e.g. 2661008385), skip rate 92.916%.
In addition, since the program uses far less memory (with cache misses mostly in sequential as opposed to random order), the approximations take somewhat less CPU time to produce than the full results.

The implication of these results is that it's entirely feasible now to run calculations using the largest sieve size currently supported by the program, namely a 2^33 sieve, by default.  This is a huge improvement: with the original setup, such an operation would have been from counterproductive to impossible in practice.

More to come later.