chiark / gitweb /
mop: New macro with-slot-variables.
[lisp] / factorial.lisp
... / ...
CommitLineData
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 --------------------------------------------------