# [racket] Why is this slow?

Hi Jordan,
2013/4/24 Jordan Schatz <jordan at noionlabs.com>
>*
*>* 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:
*>*
*
I better take the blame for the number-theory collection :-)
>* #lang racket
*>*
*>* (require math/number-theory)
*>*
*>* ;;takes about 4 seconds
*>* (apply + (filter prime? (range 1 2000000)))
*>*
*>* But I thought that spoiled the fun, and I was surely making racket work
*>* more
*>* then necessary testing each number in the range, so I thought the Sieve of
*>* Eratosthenes would be fast and fun:
*>*
*>* (define (sieve-of-eratosthenes n)
*>*
* ...
>* (define A (make-vector n #t))
*>*
* ...
>* But it is dead slow....
*>*
*
The easiest way to make your sieve faster is to allocate a smaller vector.
Since 2 is the only even prime, you know in advance that every other
element of the vector contains false. Using this fact you kan reduce
the size of the vector to n/2.
This change is relatively easy to make. You can however take the
idea further and use the same trick with 3. Since 2*3=6 we look at
the remainders from division with 6. The remainders 0, 2, and 4
indicate an even number, and the remainders 0 and 3 are numbers
that 3 divide. Primes must therefore have remainder 1 or 5 when
divided by 6. Omitting numbers with remainders 0,2,3,4 from the
vector reduces the size of the vector to n/3.
Extending to the first three primes is also possible.
In the number-theory module I used remainders modulo 60=2*2*3*5.
The trick is that there are exactly 16 numbers modulo 60, that
stems from non-primes. One can therefore represent the block of 60
remainders in only 2 bytes. See the gory details in:
https://github.com/plt/racket/blob/master/collects/math/private/number-theory/small-primes.rkt
/Jens Axel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130424/2e56906e/attachment.html>