<!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>Hi Eli and Jens Axel,</DIV>
<DIV>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.</DIV>
<DIV>Jos </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=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> Sunday, March 18, 2007 10:33
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 18, jos koot wrote:<BR>> Hi Eli,<BR>> I am
interested in how you solved the problem using a vector while<BR>> not
knowing beforehand the maximum number that will be generated<BR>> while
cycling.<BR><BR>My code does not use vectors... (But a standard approach
is to wrap<BR>vector access by a layer that copies the vector to one that is
twice<BR>the size whenever a larger index is used.)<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>