Hi Jordan,<br><br><div class="gmail_quote">2013/4/24 Jordan Schatz <span dir="ltr"><<a href="mailto:jordan@noionlabs.com" target="_blank">jordan@noionlabs.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
I'm working through some programing puzzles, and one of them was to find the sum of all primes less the 2 million, the new math/number-theory collection (thanks Neil) makes it easy:<br></blockquote><div><br></div><div>
I better take the blame for the number-theory collection :-)</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
#lang racket<br>
<br>
(require math/number-theory)<br>
<br>
;;takes about 4 seconds<br>
(apply + (filter prime? (range 1 2000000)))<br>
<br>
But I thought that spoiled the fun, and I was surely making racket work more<br>
then necessary testing each number in the range, so I thought the Sieve of<br>
Eratosthenes would be fast and fun:<br>
<br>(define (sieve-of-eratosthenes n)<br></blockquote><div> ... </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> (define A (make-vector n #t))<br></blockquote>
<div> ... </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">But it is dead slow....<br></blockquote><div><br></div><div>The easiest way to make your sieve faster is to allocate a smaller vector.</div>
<div>Since 2 is the only even prime, you know in advance that every other</div><div>element of the vector contains false. Using this fact you kan reduce</div><div>the size of the vector to n/2.</div><div><br></div><div>This change is relatively easy to make. You can however take the</div>
<div>idea further and use the same trick with 3. Since 2*3=6 we look at</div><div>the remainders from division with 6. The remainders 0, 2, and 4</div><div>indicate an even number, and the remainders 0 and 3 are numbers</div>
<div>that 3 divide. Primes must therefore have remainder 1 or 5 when</div><div>divided by 6. Omitting numbers with remainders 0,2,3,4 from the</div><div>vector reduces the size of the vector to n/3.</div><div>Extending to the first three primes is also possible.</div>
<div><br></div><div>In the number-theory module I used remainders modulo 60=2*2*3*5.</div><div>The trick is that there are exactly 16 numbers modulo 60, that</div><div>stems from non-primes. One can therefore represent the block of 60</div>
<div>remainders in only 2 bytes. See the gory details in:</div><div><br></div><div><a href="https://github.com/plt/racket/blob/master/collects/math/private/number-theory/small-primes.rkt">https://github.com/plt/racket/blob/master/collects/math/private/number-theory/small-primes.rkt</a></div>
<div><br></div><div>/Jens Axel</div><div><br></div><div><br></div><div> </div></div>