[Shootout-list] nsieve in Lisp
Dima Dorfman
d+shootout@trit.org
Tue, 4 Jan 2005 06:56:59 +0000
--i9LlY+UWpKt15+FH
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Isaac Gouy <igouy2@yahoo.com> wrote:
> > NB: Specifying the array element-type as (integer 0 1) causes CMUCL
> > to create a bit array. We're supposed to have a separate benchmark
> for
> > that, but I don't think it would be fair to go out of our way to
> > break this optimization. This is a good test of the compiler.
>
> "Boolean values in Common Lisp are represented by the reserved symbols
> T and NIL"
>
> Is that correct? If so, use T and Nil, not 0 and 1.
Yes, that's true. I knew that, but I thought {0, 1} would have been
clearer in this case. I've attached a version that uses {nil, t}.
Incidentally (and I didn't know this yesterday), CMUCL does not optimize
the nil/t array as well as the 0/1 variant. Oh well. If you want to,
just put the old version as nsieve_bits and this one as nsieve, but I
still think that the old one is fair for the regular nsieve test.
Dima.
--i9LlY+UWpKt15+FH
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="nsieve.lisp"
;;; nsieve benchmark for The Computer Language Shootout
;;; Written by Dima Dorfman, 2005
(defun nsieve (m)
(declare (type integer m))
(let ((a (make-array (list m) :initial-element t
:element-type 'boolean)))
(flet ((clear (i)
(loop for j from (+ i i) to (1- m) by i
do (setf (aref a j) nil))))
(loop for i from 2 to (1- m)
when (aref a i) do (clear i)
count (aref a i)))))
(defun test (n)
(let ((m (* 10000 (expt 2 n))))
(format t "Primes up to~T~d~T~d~%" m (nsieve m))))
(defun main ()
(let* ((args #+sbcl sb-ext:*posix-argv*
#+cmu extensions:*command-line-strings*
#+gcl si::*command-args*)
(n (parse-integer (car (last args)))))
(when (>= n 0) (test n))
(when (>= n 1) (test (- n 1)))
(when (>= n 2) (test (- n 2)))))
--i9LlY+UWpKt15+FH--