Comments on: Prime numbers in Common Lisp

By: Sterling Camden

Sterling Camden — Wed, 19 May 2010 17:48:21 +0000

Thanks, Bruce. I probably could have figured out a way to make gcf and lcd share common code and pass in a function that differentiates their behavior.

By: Bruce

Bruce — Wed, 19 May 2010 08:47:27 +0000

Your examples are most instructive. I particularly like the elegance of your gcf algorithm.

By: Sterling Camden

Sterling Camden — Sat, 24 Oct 2009 17:36:22 +0000

Your examples are most instructive. I particularly like the elegance of your gcf algorithm.

By: Sterling Camden

Sterling Camden — Fri, 23 Oct 2009 16:10:48 +0000

Thanks, todavies. I’ll have to fully digest your algorithm when I get some more free time.

By: todavies

todavies — Thu, 22 Oct 2009 03:10:16 +0000

Oops, i misread your numbers – it says 10000 not 100000…

(time (nth-prime 10000))
Evaluation took:
0.075 seconds of real time
0.048003 seconds of total run time (0.048003 user, 0.000000 system)

I’m running your version (wrapped in a package) on the same system –

(time (prime::nth-prime 10000))
Evaluation took:
1.308 seconds of real time
1.188074 seconds of total run time (1.152072 user, 0.036002 system)

(time (prime::nth-prime 100000))
Evaluation took:
200.507 seconds of real time
135.396462 seconds of total run time (120.423526 user, 14.972936 system)

Conclusion – vectors are your friends…

http://www.cs.mu.oz.au/~todavies/primes.lisp for the source

By: todavies

todavies — Thu, 22 Oct 2009 02:53:47 +0000

I think you are largely suffering from a bad algorithm – using lists is bad when you occasionally want random access (I saw a use of #’last too!!!)… although yes clisp is slow compared to nearly every other lisp unless you are using big numbers (bigger than 8 bytes) cause its the only widely used implementation that doesn’t native compile, but it has GMP,
with my implementation on a 4 year old Thinkpad R60i using sbcl starting with 2&3 in the list:

(time (nth-prime 100000))
Evaluation took:
2.279 seconds of real time
…snip…

(time (nth-prime 1000000))
Evaluation took:
49.503 seconds of real time
28.997812 seconds of total run time (28.861803 user, 0.136009 system)
…snip…