Factorials with Clojure and SBCL

I've been playing with Clojure for a few days now, and have to admit being really impressed. It's almost as flexible as Lisp, and has simple and complete access to the massive Java class libraries. It's also fully dynamic, unlike the largely static Java language that it shares a platform with.

One of the somewhat contrived examples used to show off dynamic languages is calculations of factorials: this quickly differentiates languages that are more considerate to the machine than the programmer, as the explosive growth of values produced by the function quickly overflows the register-bound int and long types in C and Java.

So I tried this out in Clojure, and hacked out this in a few minutes:

(defn factorial [x]
  (loop [current x
	 accum   1]
    (if (= current 1)
      accum
      (recur (- current 1)
	     (* current accum)))))

loop/recur offers optimisation similar to tail call optimisation, allowing you to avoid blowing the stack with large numbers. Trying this out with 100,000, my dual core Macbook Pro chugged away for just over four minutes to produce a number almost half a million digits long.

I was impressed.

Curious about how a more traditional Lisp would cope, I tried this largely equivalent code out in SBCL:

(defun factorial (x)
  (labels ((helper (current accum)
	     (if (= current 1)
		 accum
		 (helper (1- current)
			 (* current accum)))))
    (helper x 1)))

which, on the same machine, performed the same calculation in under 13 seconds. WOW.

The purely iterative version:

(defun factorial (x)
  (do ((current x (1- current))
       (accum 1 (* current accum)))
      ((= current 1)
       accum)))

performed almost identically.

Pretty awesome. :-)