<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META http-equiv=Content-Type content="text/html; charset=iso-8859-1"> <META content="MSHTML 6.00.6000.16414" name=GENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=#ffffff> <DIV>Thanks,</DIV> <DIV>Most interesting. I am not familiar with the sull Collatz sequence, but you did provide a clear answer and a nice pointer to chase.</DIV> <DIV>Jos Koot</DIV> <DIV> </DIV> <DIV>(((((lambda(x)((((((((x x)x)x)x)x)x)x)x))<BR>    (lambda(x)(lambda(y)(x(x y)))))<BR>   (lambda(x)(x)x))<BR>  (lambda()(printf "Greetings, Jos~n"))))</DIV> <BLOCKQUOTE style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px"> <DIV style="FONT: 10pt arial">----- Original Message ----- </DIV> <DIV style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><B>From:</B> <A title=eli@barzilay.org href="mailto:eli@barzilay.org">Eli Barzilay</A> </DIV> <DIV style="FONT: 10pt arial"><B>To:</B> <A title=jos.koot@telefonica.net href="mailto:jos.koot@telefonica.net">jos koot</A> </DIV> <DIV style="FONT: 10pt arial"><B>Cc:</B> <A title=jensaxel@soegaard.net href="mailto:jensaxel@soegaard.net">Jens Axel Søgaard</A> ; <A title=dyoo@cs.wpi.edu href="mailto:dyoo@cs.wpi.edu">Daniel Yoo</A> ; <A title=plt-scheme@list.cs.brown.edu href="mailto:plt-scheme@list.cs.brown.edu">plt-scheme@list.cs.brown.edu</A> </DIV> <DIV style="FONT: 10pt arial"><B>Sent:</B> Monday, March 19, 2007 1:38 PM</DIV> <DIV style="FONT: 10pt arial"><B>Subject:</B> Re: [plt-scheme] Effect of caching using hash-tables vs vectors</DIV> <DIV><BR></DIV>On Mar 19, jos koot wrote:<BR>> Hi Eli and Jens Axel,<BR>> Thanks for your responses. The idea of copying a vector into a<BR>> larger one is straight forward. But when looking for the maximum<BR>> cycle for the numbers 1 to 1e7, the size of the vector will grow<BR>> beyond practical limits. Even when storing the cycles of odd numbers<BR>> only, computing the maximum cycle for the numbers 1 up to but not<BR>> including 1e7 would require a vector of length (/ (sub1<BR>> 20114203639877) 2) = 10057101819938 = about 1e13. I managed to<BR>> compute this by memorizing the cycles of odd numbers <= 250000001 in<BR>> a vector and hashing the others (requiring 107176 hash-table<BR>> entries). The vector gives a hit/lookup rate of about 56%. The<BR>> hash-table is not very effective, for it provides a hit/lookup rate<BR>> of about 0.3%. Indeed, without the hash, the computation takes about<BR>> the same amount of time. It was a nice exercise.<BR><BR>I think that my line started by observing that you can get rid of more<BR>than just the even numbers.  Something like this:<BR><BR>* You test all numbers, starting from 1 and going up.<BR><BR>* By the time you reach N, you know that sequences that started with<BR>  1..N-1 all converged, so you don't need to test the sull Collatz<BR>  sequence that starts at N -- it's enough to stop as soon as you<BR>  reach some smaller number.<BR><BR>* This means that all even numbers are automatically fine, because N/2<BR>  is always smaller than N.<BR><BR>* But similar to that, there are other bit patterns that are always<BR>  good.  For example, if your number is 4n+1, then the sequence will<BR>  be:<BR>    4n+1<BR>    3(4n+1)+1 = 12n+4<BR>    6n+2<BR>    3n+1<BR>  which is smaller than 4n+1<BR><BR>* This means that a binary suffix of `0' and `01' make the number<BR>  safe, so looking at the last two binary digits you need to test only<BR>  `11'.  When you continue going up, you get more than one<BR>  alternative, obviously.<BR><BR>* At some point I saw that there was a connection between safe bit<BR>  suffixes and collatz sequences -- so I wrote a program that for each<BR>  suffix computes the next set of suffixes to try, verify them using a<BR>  generated C program, and the resulting process is a list of bigger<BR>  suffixes to try.  The limit I reached was due to the size of C<BR>  integers.<BR><BR>-- <BR>          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:<BR>                  <A href="http://www.barzilay.org/">http://www.barzilay.org/</A>                 Maze is Life!<BR></BLOCKQUOTE></BODY></HTML>