Re: How to write a efficient Sieve of Eratosthenes algorithm in lisp?

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


fungsin.lui@xxxxxxxxx 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)))

.

Relevant Pages

  • How to write a efficient Sieve of Eratosthenes algorithm in lisp?
    ... the ultimate test is to find primes in range 999900000 - ... Also, my sieve algorithm is n log, so even if the space ... Is there a way to optimize the lisp code below in a similar way? ... (loop for x from (start-index n) ...
    (comp.lang.lisp)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slower with larger sieve sizes due to the large number of memory accesses. ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slows down based on size memory used ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: As the Crow flies.
    ... Almost any sieve would do. ... counting primes < 1000000 ... mark.c:50: warning: return type defaults to ?int? ... mark.c:56: warning: format ?%lld? ...
    (talk.origins)
  • Re: Segfault City
    ... C offers no guarantee that there is any character with a code point ... Not those exact words, but yes, it's true that the Standard offers no such ... but I am in the mood to write a Sieve. ... Number of primes in the sieve: ...
    (comp.lang.c)
Loading