[racket] Why is this slow?

If you'd like to see some code about the same sort of problem scaled up, I
have a pair of blog posts about summing the first billion prime numbers
using Racket (it gets even more interesting, since the sieves start getting
too large to hold in a single vector):

http://blog.jverkamp.com/2012/11/01/the-sum-of-the-first-billion-primes/
Calculates a direct sum using naive prime testing, prime testing using
previous primes, and the Sieves of Eratosthenes, Atkin, and Sundaram.

http://blog.jverkamp.com/2012/11/29/one-billion-primes-segmented-sieve/
Uses a segmented Sieve of Eratosthenes which runs about three times faster
than the previous best.

Another trick (if you can call it that) that I picked up on this mailing
list a bit ago was that converting code to Typed Racket for numeric
problems can do wonders. Without it, Racket has to do a lot more checking
to make sure you aren't adding apples and oranges. So even just by adding a
few type annotations (and not changing anything else) you can get some
pretty impressive boosts.

Here's some more on that:
http://blog.jverkamp.com/2013/04/16/adventures-in-optimization-re-typed-racket/

(Granted, if you make the change below using integer-sqrt and in-range, the
runtime is already only 0.85 seconds on my machine, so that may not
strictly be necessary. :)

JP


On Wed, Apr 24, 2013 at 1:37 AM, Jordan Schatz <jordan at noionlabs.com> wrote:

>
> 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:
>
> #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:
>
> #lang racket
> ;; Input: an integer n > 1
> (define (sieve-of-eratosthenes n)
>   ;; Let A be an array of Boolean values, indexed by integers 2 to n,
>   ;; initially all set to true.
>
>   ;; for i = 2, 3, 4, ..., √n :
>   ;;   when A[i] is true:
>   ;;     for j = i², i²+i, i²+2i, ..., n:
>   ;;       A[j] := false
>   (define A (make-vector n #t))
>   (for ([i (range 2 (sqrt n))])
>     (when (vector-ref A i)
>       (for ([p (range 0 n)])
>         #:break (> (+ (* i i) (* p i) 1) n)
>         (let ([j (+ (* i i) (* p i))])
>           (vector-set! A j #f)))))
>
>   ;; Now all i such that A[i] is true are prime.
>   (filter number?
>    (for/list ([i (range 2 n)])
>      (when (vector-ref A i) i))))
>
> ;;takes about 17 seconds
> (time (apply + (sieve-of-eratosthenes 2000000))
>
> But it is dead slow....
>
> Thanks,
> Jordan
>
>
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130425/e7e25222/attachment.html>