From: ···········@gmail.com
Subject: How to write a efficient Sieve of Eratosthenes algorithm in lisp?
Date: 
Message-ID: <1159605466.539194.284890@c28g2000cwb.googlegroups.com>
Hi all,

I came across this programming challenge problem set yesterday and get
hooked because the online judge supports lisp :-)

I was playing around with this problem:

http://www.spoj.pl/problems/PRIME1/

At first I attack it with the Miller-Rabin-test, but it wouldn't scale
with 100000 targets to test.

Next, I use the sieve of Eratosthenes method, and it runs in
reasonable time to find primes in range 800000 - 900000.

However, the ultimate test is to find primes in range 999900000 -
1000000000, which is quite a challenge.

Base on my observation, once the number is larger than fixnum, the
boxing and unboxing of bignum takes a big hit in memory usage and
performance (GC).

I use clisp because the online judge only supports CLISP (and GCL,
which I don't use). I also tried it on lispworks 5, the result is
slightly better because its fixnum range is larger than clisp, but
it's still not good enough to find primes in 999900000 - 1000000000
efficiently.


Also, my sieve algorithm is n log (n) (?), so even if the space
requirement is solved it is still running too slow.

Reading a comment in their forum, it looks like that the python guys
have tricks to tackle this problem in 1.36s !

http://www.spoj.pl/forum/viewtopic.php?t=3226&sid=4a08b56fa3d4dbcaa99a02bd1b2114ea

Specifically, someone mention a trick that can speed up the sieve
algorithm significantly.

> Don't write a Python loop to "cross out" sieve entries. Use list
> slice notation instead. For example, rather than
>
> Code:
> for i in xrange(0, n, 3):
>     a[i] = 0
> do
>
> Code:
> a[0:n:3] = [0] * ((n-1)//3 + 1)
>
> Then you're doing only one statement "at Python speed" rather than
> (potentially) millions.

Is there a way to optimize the lisp code below in a similar way?

(loop for x from (start-index n) upto (number->index high) by n
      do (setf (sbit sieve x) 0))


Below are my test results and code. I'd love to hear your suggestions.

-- fungsin

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

CL-USER>  (test-sieve-primes-in-range 200000)

Real time: 0.4375 sec.
Run time: 0.4375 sec.
Space: 12632 Bytes
GC: 1, GC time: 0.015625 sec.

CL-USER>  (test-sieve-primes-in-range 900000)

Real time: 1.171875 sec.
Run time: 1.171875 sec.
Space: 12632 Bytes

CL-USER>  (test-sieve-primes-in-range 100000000)

Real time: 215.14063 sec.
Run time: 214.26563 sec.
Space: 5251187000 Bytes
GC: 5181, GC time: 25.84375 sec.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(declaim (optimize (speed 3) (debug 0) (safety 0)))

(defun sieve-primes-in-range (low high)
  "Create a bit array with size (high - low + 1). A bit is 1 to
indicate the number is prime, 0 otherwise."
  (let* ((size (1+ (- high low)))
         (sieve (make-array size
                            :element-type 'bit
                            :initial-element 1)))
    ;; number 1 is not consider prime
    (when (= low 1) (setf (sbit sieve 0) 0))
    (labels ((number->index (n) (- n low))
             (index->number (i) (+ i low))
             (start-index (n)
               (number->index (max (+ n n)
                                   (* n (ceiling low n)))))
             (clear-sieve (n)
               ;; start with the first multiple that are in the range
[low,high]
               (loop for i from (start-index n) upto (number->index
high) by n
                     do (setf (sbit sieve i) 0))))
      ;; filtering out the non-primes, start with number 2
      (loop for n from 2 upto high
            unless (and (>= n low)
                        (= (sbit sieve (number->index n)) 0))
            do
            (clear-sieve n))
      #-(and)
      (loop for x from 0 to (1- size)
            if (= 1 (sbit sieve x)) do
            (format t "~D~%" (index->number x)))
      (terpri))))

(defun test-sieve-primes-in-range (high)
  "Test at most 100000 numbers, as stated in the problem set."
  (time (sieve-primes-in-range (max 1 (- high 100000)) high)))

From: vanekl
Subject: Re: How to write a efficient Sieve of Eratosthenes algorithm in lisp?
Date: 
Message-ID: <1159617577.683124.74440@i3g2000cwc.googlegroups.com>
are you compiling your file?

i made one small change:

  (loop for n from 2 upto (isqrt high)...

and these are my results (sbcl):

;;;; (time (sieve-primes-in-range 999900000 1000000000)) ...
Evaluation took:
  0.03 seconds of real time
  0.03 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  2,035,712 bytes consed.

clisp should be a little slower than sbcl, but not that much.

Lou Vanek


···········@gmail.com wrote:
> Hi all,
>
> I came across this programming challenge problem set yesterday and get
> hooked because the online judge supports lisp :-)
>
> I was playing around with this problem:
>
> http://www.spoj.pl/problems/PRIME1/
>
> At first I attack it with the Miller-Rabin-test, but it wouldn't scale
> with 100000 targets to test.
>
> Next, I use the sieve of Eratosthenes method, and it runs in
> reasonable time to find primes in range 800000 - 900000.
>
> However, the ultimate test is to find primes in range 999900000 -
> 1000000000, which is quite a challenge.
>
> Base on my observation, once the number is larger than fixnum, the
> boxing and unboxing of bignum takes a big hit in memory usage and
> performance (GC).
>
> I use clisp because the online judge only supports CLISP (and GCL,
> which I don't use). I also tried it on lispworks 5, the result is
> slightly better because its fixnum range is larger than clisp, but
> it's still not good enough to find primes in 999900000 - 1000000000
> efficiently.
>
>
> Also, my sieve algorithm is n log (n) (?), so even if the space
> requirement is solved it is still running too slow.
>
> Reading a comment in their forum, it looks like that the python guys
> have tricks to tackle this problem in 1.36s !
>
> http://www.spoj.pl/forum/viewtopic.php?t=3226&sid=4a08b56fa3d4dbcaa99a02bd1b2114ea
>
> Specifically, someone mention a trick that can speed up the sieve
> algorithm significantly.
>
> > Don't write a Python loop to "cross out" sieve entries. Use list
> > slice notation instead. For example, rather than
> >
> > Code:
> > for i in xrange(0, n, 3):
> >     a[i] = 0
> > do
> >
> > Code:
> > a[0:n:3] = [0] * ((n-1)//3 + 1)
> >
> > Then you're doing only one statement "at Python speed" rather than
> > (potentially) millions.
>
> Is there a way to optimize the lisp code below in a similar way?
>
> (loop for x from (start-index n) upto (number->index high) by n
>       do (setf (sbit sieve x) 0))
>
>
> Below are my test results and code. I'd love to hear your suggestions.
>
> -- fungsin
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> CL-USER>  (test-sieve-primes-in-range 200000)
>
> Real time: 0.4375 sec.
> Run time: 0.4375 sec.
> Space: 12632 Bytes
> GC: 1, GC time: 0.015625 sec.
>
> CL-USER>  (test-sieve-primes-in-range 900000)
>
> Real time: 1.171875 sec.
> Run time: 1.171875 sec.
> Space: 12632 Bytes
>
> CL-USER>  (test-sieve-primes-in-range 100000000)
>
> Real time: 215.14063 sec.
> Run time: 214.26563 sec.
> Space: 5251187000 Bytes
> GC: 5181, GC time: 25.84375 sec.
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> (declaim (optimize (speed 3) (debug 0) (safety 0)))
>
> (defun sieve-primes-in-range (low high)
>   "Create a bit array with size (high - low + 1). A bit is 1 to
> indicate the number is prime, 0 otherwise."
>   (let* ((size (1+ (- high low)))
>          (sieve (make-array size
>                             :element-type 'bit
>                             :initial-element 1)))
>     ;; number 1 is not consider prime
>     (when (= low 1) (setf (sbit sieve 0) 0))
>     (labels ((number->index (n) (- n low))
>              (index->number (i) (+ i low))
>              (start-index (n)
>                (number->index (max (+ n n)
>                                    (* n (ceiling low n)))))
>              (clear-sieve (n)
>                ;; start with the first multiple that are in the range
> [low,high]
>                (loop for i from (start-index n) upto (number->index
> high) by n
>                      do (setf (sbit sieve i) 0))))
>       ;; filtering out the non-primes, start with number 2
>       (loop for n from 2 upto high
>             unless (and (>= n low)
>                         (= (sbit sieve (number->index n)) 0))
>             do
>             (clear-sieve n))
>       #-(and)
>       (loop for x from 0 to (1- size)
>             if (= 1 (sbit sieve x)) do
>             (format t "~D~%" (index->number x)))
>       (terpri))))
>
> (defun test-sieve-primes-in-range (high)
>   "Test at most 100000 numbers, as stated in the problem set."
>   (time (sieve-primes-in-range (max 1 (- high 100000)) high)))
From: ···········@gmail.com
Subject: Re: How to write a efficient Sieve of Eratosthenes algorithm in lisp?
Date: 
Message-ID: <1159627262.423573.270680@c28g2000cwb.googlegroups.com>
vanekl wrote:
>
> i made one small change:
>
>   (loop for n from 2 upto (isqrt high)...

My face is red. Thanks for spotting this glaring error.