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)))
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)))