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 <jor...@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 >
____________________ Racket Users list: http://lists.racket-lang.org/users
