My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
Cache  
Summary of the cache system for Collatz.
Updated Sep 6, 2009 by timothy....@gmail.com

Introduction

The program utilizes a metacache of precomputed maximum cycle lengths over intervals of size 150 from 1 to 999900 (inclusive).

Details

To take advantage of this cache, we consider the computations of numbers in the input range {a,b} in three sections: first we find the the maximum cycle length (mcl) of a number from {a, x1 = <first number greater than 'a' that is divisible by 150>} computing naively, next find the mcl over {x1, x2 = <greatest number strictly less than 'b' divisible by 150>} using the metacache, and finally the mcl over {x2,b} naively once again. Of course, for some inputs {a,b} it is not appropriate to do the second or third computation, in particular if (i) b < x1 or (ii) b < x3 = <the second-least number greater that 'a' divisible by 150>. In these cases the mcl over {a,b} is computed naively, however {a,b} is guaranteed to be reasonably small.

Powered by Google Project Hosting