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