;;; -*-lisp-*-
;;;
;;; Compute factorials
;;;
;;; (c) 2006 Mark Wooding
;;;

;;;----- Licensing notice ---------------------------------------------------
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as published by
;;; the Free Software Foundation; either version 2 of the License, or
;;; (at your option) any later version.
;;; 
;;; This program is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;; GNU General Public License for more details.
;;; 
;;; You should have received a copy of the GNU General Public License
;;; along with this program; if not, write to the Free Software Foundation,
;;; Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

(defpackage #:mdw.factorial
  (:use #:common-lisp)
  (:export #:factorial))
(in-package #:mdw.factorial)

(defun factorial (n)
  "Compute a factorial.  This is a little bit optimized: we try to multiply
   values which are similar in size."
  (when (minusp n)
    (error "negative factorial argument ~A" n))
  (let ((stack nil))
    (do ((i 2 (1+ i)))
	((> i n))
      (let ((f i))
	(loop
	  (unless stack (return))
	  (let ((top (car stack)))
	    (when (< f top) (return))
	    (setf f (* f top))
	    (pop stack)))
	(push f stack)))
    (do ((stack stack (cdr stack))
	 (a 1 (* a (car stack))))
	((null stack) a))))

;;;----- That's all, folks --------------------------------------------------