;;; 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))
+ (:use #:common-lisp))
(in-package #:mdw.factorial)
+(export 'factorial)
(defun factorial (n)
- "Compute a factorial. This is a little bit optimized: we try to multiply
- values which are similar in size."
+ "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))))
+ (do ((i 2 (1+ i))
+ (stack nil (do ((s stack (cdr s))
+ (f i (* f (car s))))
+ ((or (null s) (< f (car s)))
+ (cons f s)))))
+ ((> i n)
+ (do ((s stack (cdr s))
+ (a 1 (* a (car s))))
+ ((null s) a)))))
;;;----- That's all, folks --------------------------------------------------