[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>