<div dir="ltr">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):<div>
<br></div><div><a href="http://blog.jverkamp.com/2012/11/01/the-sum-of-the-first-billion-primes/" target="_blank">http://blog.jverkamp.com/2012/11/01/the-sum-of-the-first-billion-primes/</a><br>
</div><div>Calculates a direct sum using naive prime testing, prime testing using previous primes, and the Sieves of Eratosthenes, Atkin, and Sundaram.</div><div><br></div><div><a href="http://blog.jverkamp.com/2012/11/29/one-billion-primes-segmented-sieve/" target="_blank">http://blog.jverkamp.com/2012/11/29/one-billion-primes-segmented-sieve/</a><br>
</div><div>Uses a segmented Sieve of Eratosthenes which runs about three times faster than the previous best.</div><div><br></div><div>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. </div>
<div><br></div><div style>Here's some more on that:</div><div style><a href="http://blog.jverkamp.com/2013/04/16/adventures-in-optimization-re-typed-racket/">http://blog.jverkamp.com/2013/04/16/adventures-in-optimization-re-typed-racket/</a><br>
</div><div style><br></div><div style>(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. :)<br></div><div style>
<br></div><div style>JP</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Apr 24, 2013 at 1:37 AM, Jordan Schatz <span dir="ltr"><<a href="mailto:jordan@noionlabs.com" target="_blank">jordan@noionlabs.com</a>></span> wrote:<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<br>
of all primes less the 2 million, the new math/number-theory collection (thanks<br>
Neil) makes it easy:<br>
<br>
#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>
#lang racket<br>
;; Input: an integer n > 1<br>
(define (sieve-of-eratosthenes n)<br>
;; Let A be an array of Boolean values, indexed by integers 2 to n,<br>
;; initially all set to true.<br>
<br>
;; for i = 2, 3, 4, ..., √n :<br>
;; when A[i] is true:<br>
;; for j = i², i²+i, i²+2i, ..., n:<br>
;; A[j] := false<br>
(define A (make-vector n #t))<br>
(for ([i (range 2 (sqrt n))])<br>
(when (vector-ref A i)<br>
(for ([p (range 0 n)])<br>
#:break (> (+ (* i i) (* p i) 1) n)<br>
(let ([j (+ (* i i) (* p i))])<br>
(vector-set! A j #f)))))<br>
<br>
;; Now all i such that A[i] is true are prime.<br>
(filter number?<br>
(for/list ([i (range 2 n)])<br>
(when (vector-ref A i) i))))<br>
<br>
;;takes about 17 seconds<br>
(time (apply + (sieve-of-eratosthenes 2000000))<br>
<br>
But it is dead slow....<br>
<br>
Thanks,<br>
Jordan<br>
<br>
<br>
<br>
____________________<br>
Racket Users list:<br>
<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br>
</blockquote></div><br></div>