Lisp - Bagley's computer language shootout

Author

Bagley's computer language shootout

Nicolas Neuss

2005-06-03, 4:00 pm

Hello,

this ugly benchmark was just mentioned again on sci.math.num-analysis and I
looked at one of the entries, namely "nsieve". It occured to me that the
CMUCL contribution could be written much nicer in the following way:

nsieve.lisp (a shortened version of the version there):
---------------------------------------------------------------------------
(defun nsieve (m)
(let ((a (make-array m :initial-element t :element-type 'boolean)))
(loop for i from 2 to (1- m) when (aref a i) do
(loop for j from (+ i i) to (1- m) by i
do (setf (aref a j) nil))
count (aref a i))))

(defun main (n)
(let ((m (* 10000 (expt 2 n))))
(format t "Primes up to~T~8<~d~>~T~8<~d~>~%" m (nsieve m))))
---------------------------------------------------------------------------

Together with the compilation command:

lisp -noinit -eval "(progn (compile-file \"nsieve.lisp\") (ext:quit))"

and the run command (one line, %A is some number):

lisp -noinit -eval "(progn (load \"nsieve\") (main (parse-integer (car (last extensions:*command-line-strings*)))) (ext:quit))" %A

I would suggest that people contributing to this shootout should follow
this pattern, such that we do not clutter nice CL programs with argument
parsing.

Probably Bagley won't like this, but other languages have complicated
invocation lines, too.

Yours, Nicolas.

P.S.: What concerns myself, I do not want to communicate any more with this
guy (Bagley). I have tried it once, without much success.

Nicolas Neuss

2005-06-03, 4:00 pm

First, the link: http://shootout.alioth.debian.org

Second, correct program with the same output as the original:
---------------------------------------------------------------------------
(defun nsieve (m)
(let ((a (make-array m :initial-element t :element-type 'boolean)))
(loop for i from 2 below m when (aref a i) do
(loop for j from (+ i i) below m by i
do (setf (aref a j) nil))
count (aref a i))))

(defun test (n)
(let ((m (* 10000 (expt 2 n))))
(format t "Primes up to~T~8<~d~>~T~8<~d~>~%" m (nsieve m))))

(defun main (n)
(loop for k from n downto (- n 2) do (test k)))
---------------------------------------------------------------------------

Wade Humeniuk

2005-06-04, 4:00 am

Paul Dietz wrote:

>
> In CMUCL, :element-type 'boolean is equivalent to :element-type T.
> If you're trying to save memory, consider a bit vector, or an
> array of element type (unsigned-byte 8) (and make corresponding
> changes in the logic.)
>

I was thinking the same thing (and a few other things), try...

(defconstant +p+ 0)
(defconstant +not-p+ 1)

(defun nsieve (m)
(let ((a (make-array m :initial-element +p+ :element-type '(unsigned-byte 8))))
(declare (type (simple-array (unsigned-byte 8) (*)) a)
(optimize (speed 3) (safety 0)))
(loop for i from 2 below m
when (= +p+ (aref a i)) do
(loop for j from (+ i i) below m by i
do (setf (aref a j) +not-p+))
and count 1)))

Wade

Nicolas Neuss

2005-06-04, 8:57 am

Nicolas Neuss <my.name@iwr.uni-heidelberg.de> writes:

> [Unfortunately, I have not been able to link this page correctly from
> <http://www.cliki.net/Benchmarks>. Could someone tell me what I did
> wrong or simply correct it?]

OK, corrected it myself. It was a simple typo.

Nicolas.

Bulent Murtezaoglu

2005-06-04, 3:57 pm

>>>>> "NN" == Nicolas Neuss <my.name@iwr.uni-heidelberg.de> writes:
[...]
NN> P.S.: What concerns myself, I do not want to communicate any
NN> more with this guy (Bagley). I have tried it once, without
NN> much success.

When he was activaly maintaining his shootout pages, Doug Bagley was
easy and pleasant to communicate with. I probably exchanged a few
dozen e-mails with him back then and had no complaints. It looks like
he's no longer interested in the shootout though. Perhaps you should
try to contact the new team?

cheers,

BM

Sponsored Links