Commit | Line | Data |
---|---|---|
874125c4 MW |
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. | |
b2c12b4e | 14 | ;;; |
874125c4 MW |
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. | |
b2c12b4e | 19 | ;;; |
874125c4 MW |
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 | |
77f935da | 25 | (:use #:common-lisp)) |
874125c4 MW |
26 | (in-package #:mdw.factorial) |
27 | ||
77f935da | 28 | (export 'factorial) |
874125c4 | 29 | (defun factorial (n) |
77f935da MW |
30 | "Compute a factorial." |
31 | ||
32 | ;; This is a little bit optimized: we try to multiply values which are | |
33 | ;; similar in size. | |
874125c4 MW |
34 | (when (minusp n) |
35 | (error "negative factorial argument ~A" n)) | |
77f935da MW |
36 | (do ((i 2 (1+ i)) |
37 | (stack nil (do ((s stack (cdr s)) | |
38 | (f i (* f (car s)))) | |
39 | ((or (null s) (< f (car s))) | |
40 | (cons f s))))) | |
41 | ((> i n) | |
42 | (do ((s stack (cdr s)) | |
43 | (a 1 (* a (car s)))) | |
44 | ((null s) a))))) | |
874125c4 MW |
45 | |
46 | ;;;----- That's all, folks -------------------------------------------------- |