mdw@git.distorted.org.uk Git - lisp/blob - factorial.lisp

   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 --------------------------------------------------