Hi, I'm trying to write a program that will calculate large prime
numbers, I have written two separate programs that can calculate the
100th prime number but break down around the 500th, I have no idea
whether they are breaking down because the numbers are too big or
because the code is inefficient. For those interested, I'm using clisp
downloaded from http://www.gigamonkeys.com/lispbox/#download
Here's my code:
;first program, goes through all numbers incrementing numbers when it
finds a prime, when ;numbers = iterations (the number of the prime we
are looking for) we return the most recent prime ;number.
(defun new-primes (pnumber number iteration)
(cond
((= iteration number)
( - pnumber 1 ))
(t
(let ((prime 1))
;see if the number has any factors less than or equal to its square
root (ceiling rounds up a number)
(loop for x from 2 to (ceiling (sqrt pnumber))
do
(cond
((= 0 (mod pnumber x))
;if it does, set prime to 0 (does return leave the loop?)
(return
(setq prime 0)))))
(cond
((= prime 0)
;if the number is not prime, move on to next number
(new-primes (+ 1 pnumber) number iteration))
(t
(progn
;if it is prime, print it and increment the number of primes found
(format t "~A~%" pnumber)
(new-primes (+ 1 pnumber) (+ 1 number) iteration ))))))))
SECOND PROGRAM
;this uses a list of primes and sees if a number has factors in that
list, for some reason it
;did not work when I tried to add something to only check factors up to
the square root of the number
(setq prime-list '(2))
(defun primes (number iterations)
(cond
((= iterations 0)
prime-list)
(t
(progn
(let ((composite 1))
(loop for e in prime-list
do
(cond
;if the number is divisible by a prime
;we note it, and stop checking (hopefully that's what
;the return does)
((= (mod number e) 0)
(progn
(setq composite 0)
(return nil)))
;commented out square root stuff
;((> e (sqrt number))
; (return nil))))
))
;(format t "number is ~A list is ~A~%" number list)
;then we call the function again, with a larger number
;and cons the number to the prime list if appropiate.
(cond
((equal composite 1)
(progn
(setq prime-list (cons number prime-list))
(format t "~A~%" number))))
(primes (+ 1 number) (- iterations composite)))))))
Neither of these functions gets past primes in the 6000s... Am I
missing out on something tremendously inefficient in my code or is
their some problem with LISP? Any help would be greatly appreciated, I
don't want answers to the problem I just want to know why my answers
aren't working.
················@gmail.com wrote:
> Neither of these functions gets past primes in the 6000s... Am I
> missing out on something tremendously inefficient in my code or is
> their some problem with LISP? Any help would be greatly appreciated, I
> don't want answers to the problem I just want to know why my answers
> aren't working.
I believe this is more a problem with your algorithms and not Lisp. I
suggest looking into non-recursive methods for calculating primes.
Check out the Sieve of Eratosthenes algorithm.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Hope this helps,
AnthonyF
·················@gmail.com wrote:
> I believe this is more a problem with your algorithms and not Lisp.
Nothing but tail calls there. What's wrong with them?
--
Dan
www.prairienet.org/~dsb
Dan Bensen wrote:
> ·················@gmail.com wrote:
> > I believe this is more a problem with your algorithms and not Lisp.
>
> Nothing but tail calls there. What's wrong with them?
>
> --
> Dan
> www.prairienet.org/~dsb
Ug, I thought about lack of tail call optimization after I posted.
Good call.
AF
Dan Bensen <··········@cyberspace.net> writes:
> ·················@gmail.com wrote:
>> I believe this is more a problem with your algorithms and not Lisp.
>
> Nothing but tail calls there. What's wrong with them?
Common Lisp doesn't specify anything relative to tail calls.
Implementations don't necessarily implement tail call optimization.
clisp doesn't on interpreted code, to ease debugging.
In any case, what's recursive in primes?
--
__Pascal Bourguignon__ http://www.informatimago.com/
Litter box not here.
You must have moved it again.
I'll poop in the sink.
>> Nothing but tail calls there. What's wrong with them?
Pascal Bourguignon wrote:
> clisp doesn't on interpreted code, to ease debugging.
Interesting. That sounds like the answer to the OP.
> In any case, what's recursive in primes?
Nothing that a simple loop can't handle. I just didn't see any obvious
blunders in the code.
--
Dan
www.prairienet.org/~dsb
On Sun, 31 Dec 2006 05:08:54 +0100, Pascal Bourguignon <···@informatimago.com>
tried to confuse everyone with this message:
>Dan Bensen <··········@cyberspace.net> writes:
>
>> ·················@gmail.com wrote:
>>> I believe this is more a problem with your algorithms and not Lisp.
>>
>> Nothing but tail calls there. What's wrong with them?
>
>Common Lisp doesn't specify anything relative to tail calls.
>Implementations don't necessarily implement tail call optimization.
>clisp doesn't on interpreted code, to ease debugging.
>
But, it needs to be said, if you compile this code, the programs work just fine.
(compile 'new-primes)
and so on...
--
|Don't believe this - you're not worthless ,gr---------.ru
|It's us against millions and we can't take them all... | ue il |
|But we can take them on! | @ma |
| (A Wilhelm Scream - The Rip) |______________|
From: Kalle Olavi Niemitalo
Subject: Re: Stack overflow in relatively simple programs
Date:
Message-ID: <87hcvcuj64.fsf@Astalo.kon.iki.fi>
·················@gmail.com" <················@gmail.com> writes:
> Hi, I'm trying to write a program that will calculate large prime
> numbers, I have written two separate programs that can calculate the
> 100th prime number but break down around the 500th, I have no idea
> whether they are breaking down because the numbers are too big or
> because the code is inefficient.
If I do (progn (new-primes 1 0 6000) (values)) on CLISP 2.38, I
get primes (or at least they look like primes) 1 to 5233 and then
a segmentation fault. If I first (compile 'new-primes), I get
from 1 to 59359 just fine, or even to 746773 if I use 60000
instead of 6000. Compiling the code sure helps.
However, Common Lisp does not require the compiler to convert
tail calls to jumps. So if you want to be sure that the program
does not exhaust the stack in any Common Lisp implementation,
you should change the recursion to iteration yourself.
> ;first program, goes through all numbers incrementing numbers when it
> finds a prime, when ;numbers = iterations (the number of the prime we
> are looking for) we return the most recent prime ;number.
Please write shorter comment lines so they don't wrap when you post.
(Or use #| ... |# but that may be a bit ugly.)
> ;see if the number has any factors less than or equal to its square
> root (ceiling rounds up a number)
> (loop for x from 2 to (ceiling (sqrt pnumber))
You could use ISQRT here. It rounds down rather than up but that
doesn't matter because the square root rounded up is already too
large to be a divisor.
> (cond
> ((= 0 (mod pnumber x))
> ;if it does, set prime to 0 (does return leave the loop?)
> (return
> (setq prime 0)))))
RETURN leaves the LOOP: http://clhs.lisp.se/Body/06_aad.htm
However, the NEVER keyword of LOOP might be more idiomatic; then
you would also get NIL or T as the result, rather than 0 or 1.
http://clhs.lisp.se/Body/06_aaec.htm
Another option would be to use FLOOR, which returns the quotient
and the remainder as multiple values. Then you wouldn't need the
ISQRT call. Whether that is an advantage depends on the
implementation, though. My times:
;; using iteration, all integers as divisors, and FLOOR
(time (let ((*standard-output* (make-broadcast-stream))) (primes-kon-1 50000)))
;; SBCL 0.9.5.50:
;; 15.884 seconds of real time
;; 9.66953 seconds of user run time
;; 0.315952 seconds of system run time
;; 0 page faults and
;; 93,996,496 bytes consed.
;; CLISP 2.38:
;; Real time: 47.774345 sec.
;; Run time: 31.116268 sec.
;; Space: 16400072 Bytes
;; GC: 24, GC time: 0.309957 sec.
;; using iteration, a list of primes, and FLOOR
(time (let ((*standard-output* (make-broadcast-stream))) (primes-kon-2 50000)))
;; SBCL 0.9.5.50:
;; 4.403 seconds of real time
;; 3.341492 seconds of user run time
;; 0.254961 seconds of system run time
;; 0 page faults and
;; 94,401,232 bytes consed.
;; CLISP 2.38:
;; Real time: 12.539415 sec.
;; Run time: 8.943641 sec.
;; Space: 16800072 Bytes
;; GC: 25, GC time: 0.514923 sec.
;; using iteration, a list of primes, ISQRT, and MOD
(time (let ((*standard-output* (make-broadcast-stream))) (primes-kon-3 50000)))
;; SBCL 0.9.5.50:
;; 6.144 seconds of real time
;; 4.07738 seconds of user run time
;; 0.277958 seconds of system run time
;; 0 page faults and
;; 94,404,528 bytes consed.
;; CLISP 2.38:
;; Real time: 11.906337 sec.
;; Run time: 8.326734 sec.
;; Space: 16800072 Bytes
;; GC: 25, GC time: 0.509925 sec.
On SBCL, calling ISQRT at the beginning of the loop apparently
takes 22% more user run time than calling FLOOR on each
iteration. On CLISP however, it takes 7% less.
> I don't want answers to the problem I just want to know why my
> answers aren't working.
I won't post my functions yet, then.
The problem with your second program is that it puts the primes on the
front of the list. So when you check for primeness, you iterate
through the list from front (the larger primes) to back (the smaller
primes). This will work but it's obviously inefficient. And it won't
work when you look for your current prime to be greater than the sqrt
of your candidate, because you're starting from the larger primes that
you've seen.
This is one of those times when you will have to do some fancy list
manipulation and put your latest results on the end of the list. You
need to do this right or your program will be horribly inefficient.
The best way is to use a tail pointer. You want code something like
this:
(defvar prime-list (cons nil nil))
(defun setup-result-list ()
(setf (car prime-list) (list 2))
(setf (cdr prime-list) (last (car prime-list))))
(defun add-result (result)
(setf (cddr prime-list) (cons result nil))
(setf (cdr prime-list) (cddr prime-list)))
Then at the end you can just print (cadr prime-list) and you will get
the largest prime you found.
("prime-list" is obviously no longer the best name for that variable.)
Here's my version of your second program, written according to my own
taste. I left the *prime-list* variable outside the function in case
you want to see all the primes.
(defvar *prime-list* (cons nil nil))
(defun setup-result-list ()
(setf (car *prime-list*) (list 2))
(setf (cdr *prime-list*) (last (car *prime-list*))))
(defun add-result (result)
(setf (cddr *prime-list*) (cons result nil))
(setf (cdr *prime-list*) (cddr *prime-list*)))
(defun primes (number iterations)
(setup-result-list)
(do* ((current number (1+ current))
(limit (isqrt current) (isqrt current))
(target-count iterations))
((zerop target-count) (cadr prime-list))
(do* ((list (car prime-list) (cdr list))
(element (car list) (car list))
(composite (zerop (mod current element)) (zerop (mod current element))))
((or composite
(null element)
(> element limit))
(unless composite
(add-result current)
;; (format t "~A~%" current)
(decf target-count)))))))
--
Fred Gilham ······@csl.sri.com
In 1981, an OSHA epidemiological study of 2,500 workers, half of whom
had been exposed to PCBs for over 17 years, found that the number of
deaths from cancer was 10 percent lower than what would be expected
for a group with the same profile in the general population.
Mistake in my code as posted:
((zerop target-count) (cadr prime-list))
should be
((zerop target-count) (cadr *prime-list*))
--
Fred Gilham ······@csl.sri.com
GOVERNMENT: A large charity organization with a coercive fund-raising
arm. PUBLIC SCHOOLS: Government-run (see above) schools with coercive
admissions departments.
Sorry, there was a mistake in my code as posted. I forgot to put the
"*" around two of the prime-list instances. Should have been:
(defun primes (number iterations)
(setup-result-list)
(do* ((current number (1+ current))
(limit (isqrt current) (isqrt current))
(target-count iterations))
((zerop target-count) (cadr *prime-list*))
(do* ((list (car *prime-list*) (cdr list))
(element (car list) (car list))
(composite (zerop (mod current element)) (zerop (mod current element))))
((or composite
(null element)
(> element limit))
(unless composite
(add-result current)
;; (format t "~A~%" current)
(decf target-count)))))))
--
Fred Gilham ······@csl.sri.com
GOVERNMENT: A large charity organization with a coercive fund-raising
arm. PUBLIC SCHOOLS: Government-run (see above) schools with coercive
admissions departments.
················@gmail.com wrote:
> Hi, I'm trying to write a program that will calculate large prime
> numbers, I have written two separate programs that can calculate the
> 100th prime number but break down around the 500th, I have no idea
> whether they are breaking down because the numbers are too big or
> because the code is inefficient.
Others have deconstructed the problems with the program, I'd just add:
* Common Lisp implementations limit the size of the stack to make it
easier to find bugs. Normally recursion that puts lots of stuff on the
stack is because of a bug. Normally there is a parameter in the
implementations to increase the stack size if you want it to be bigger.
* Often Common Lisp compilers don't implement tail-call elimination in
interpreted code, but almost all do in compiled code. So if you want
to use tail-calls then compile your code even when debugging.