| 1 | ;;; -*-lisp-*- |
| 2 | ;;; |
| 3 | ;;; Compute factorials |
| 4 | ;;; |
| 5 | ;;; (c) 2006 Mark Wooding |
| 6 | ;;; |
| 7 | |
| 8 | ;;;----- Licensing notice --------------------------------------------------- |
| 9 | ;;; |
| 10 | ;;; This program is free software; you can redistribute it and/or modify |
| 11 | ;;; it under the terms of the GNU General Public License as published by |
| 12 | ;;; the Free Software Foundation; either version 2 of the License, or |
| 13 | ;;; (at your option) any later version. |
| 14 | ;;; |
| 15 | ;;; This program is distributed in the hope that it will be useful, |
| 16 | ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 17 | ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 18 | ;;; GNU General Public License for more details. |
| 19 | ;;; |
| 20 | ;;; You should have received a copy of the GNU General Public License |
| 21 | ;;; along with this program; if not, write to the Free Software Foundation, |
| 22 | ;;; Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
| 23 | |
| 24 | (defpackage #:mdw.factorial |
| 25 | (:use #:common-lisp) |
| 26 | (:export #:factorial)) |
| 27 | (in-package #:mdw.factorial) |
| 28 | |
| 29 | (defun factorial (n) |
| 30 | "Compute a factorial. This is a little bit optimized: we try to multiply |
| 31 | values which are similar in size." |
| 32 | (when (minusp n) |
| 33 | (error "negative factorial argument ~A" n)) |
| 34 | (let ((stack nil)) |
| 35 | (do ((i 2 (1+ i))) |
| 36 | ((> i n)) |
| 37 | (let ((f i)) |
| 38 | (loop |
| 39 | (unless stack (return)) |
| 40 | (let ((top (car stack))) |
| 41 | (when (< f top) (return)) |
| 42 | (setf f (* f top)) |
| 43 | (pop stack))) |
| 44 | (push f stack))) |
| 45 | (do ((stack stack (cdr stack)) |
| 46 | (a 1 (* a (car stack)))) |
| 47 | ((null stack) a)))) |
| 48 | |
| 49 | ;;;----- That's all, folks -------------------------------------------------- |