[plt-scheme] Effect of caching using hash-tables vs vectors

Sounds like you could use that kind of a strategy to go way further
than just C integers. Are C integers really the biggest numbers people
have found to converge?

Robby

On 3/19/07, Eli Barzilay <eli at barzilay.org> wrote:
> On Mar 19, jos koot wrote:
> > Hi Eli and Jens Axel,
> > Thanks for your responses. The idea of copying a vector into a
> > larger one is straight forward. But when looking for the maximum
> > cycle for the numbers 1 to 1e7, the size of the vector will grow
> > beyond practical limits. Even when storing the cycles of odd numbers
> > only, computing the maximum cycle for the numbers 1 up to but not
> > including 1e7 would require a vector of length (/ (sub1
> > 20114203639877) 2) = 10057101819938 = about 1e13. I managed to
> > compute this by memorizing the cycles of odd numbers <= 250000001 in
> > a vector and hashing the others (requiring 107176 hash-table
> > entries). The vector gives a hit/lookup rate of about 56%. The
> > hash-table is not very effective, for it provides a hit/lookup rate
> > of about 0.3%. Indeed, without the hash, the computation takes about
> > the same amount of time. It was a nice exercise.
>
> I think that my line started by observing that you can get rid of more
> than just the even numbers.  Something like this:
>
> * You test all numbers, starting from 1 and going up.
>
> * By the time you reach N, you know that sequences that started with
>   1..N-1 all converged, so you don't need to test the sull Collatz
>   sequence that starts at N -- it's enough to stop as soon as you
>   reach some smaller number.
>
> * This means that all even numbers are automatically fine, because N/2
>   is always smaller than N.
>
> * But similar to that, there are other bit patterns that are always
>   good.  For example, if your number is 4n+1, then the sequence will
>   be:
>     4n+1
>     3(4n+1)+1 = 12n+4
>     6n+2
>     3n+1
>   which is smaller than 4n+1
>
> * This means that a binary suffix of `0' and `01' make the number
>   safe, so looking at the last two binary digits you need to test only
>   `11'.  When you continue going up, you get more than one
>   alternative, obviously.
>
> * At some point I saw that there was a connection between safe bit
>   suffixes and collatz sequences -- so I wrote a program that for each
>   suffix computes the next set of suffixes to try, verify them using a
>   generated C program, and the resulting process is a list of bigger
>   suffixes to try.  The limit I reached was due to the size of C
>   integers.
>
> --
>           ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
>                   http://www.barzilay.org/                 Maze is Life!
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>