[racket] Why is this slow?

From: Shannon Severance (srs at s53.me)
Date: Wed Apr 24 05:45:47 EDT 2013

This one I will need to study, since it uses new to me Racket stuff. And
it is quick. On my machine:
> (time (apply + (gb-sieve-of-eratosthenes n)))
cpu time: 485 real time: 497 gc time: 118
142913828922


Compare:
> (time (apply + (filter prime? (range 2 n))))
cpu time: 9788 real time: 9974 gc time: 1851
142913828922
> (time (apply + (soe n)))
cpu time: 1049 real time: 1065 gc time: 311
142913828922
> (time (apply + (sieve-of-eratosthenes n)))
cpu time: 266955 real time: 274532 gc time: 218362
142913828922

Machine info in separate email to the list.



On 4/24/13 2:17 AM, "Gary Baumgartner" <gfb at cs.toronto.edu> wrote:

>#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 (in-range 2 (sqrt n))]
>        #:when (vector-ref A i))
>    (for ([j (in-range (sqr i) n i)])
>      (vector-set! A j #f)))
>
>  ;; Now all i such that A[i] is true are prime.
>  (for/list ([i (in-range 2 n)]
>             #:when (vector-ref A i))
>    i))
>
>(time (apply + (sieve-of-eratosthenes 2000000)))




Posted on the users mailing list.