factorials in many incarnations

frontera000 (bob bae) — Tue, 26 Sep 2006 02:53:59 GMT

// http://www.cs.indiana.edu/~sganz/publications/icfp99/paper.pdf



;; simple definition of factorial:

;; this will run into trouble due to precision



(define (factorial-1  num)

  (if (= num 0)

      1

      (* num (factorial-1 (- num 1)))))



;; factorial using imported GMP package:

;; it works better but runs into trouble with too deep call stack



(load "gmp.lsp")



(define (factorial-gmp num)

  (if (= num 0)

      "1"

      (GMP:* (string num) (factorial-gmp (- num 1)))))



;; Finally, a trampoline style recursive definition of

;; factorial which simulates tail recursive implementation

;; avoiding call stack overflow



(define (factorial-acc num acc)

  (if (= num 0)

      (land (string acc))

      (bounce factorial-acc (- num 1) (GMP:* (string num) (string acc)))))



(define (factorial-trampoline num)

  (trampoline factorial-acc num 1))



(define (trampoline func num acc)

  (set 'bouncer (bounce func num acc))

  (catch (while 1

		(set 'bouncer (bouncer))

		(if (not (lambda? bouncer))

		    (throw bouncer)))))



(define (bounce)

  (letex (func (args 0) num (args 1) acc (args 2))

	(lambda() (func num acc))))



(define (land val)  val)

Factorial in Scheme

willpost () — Thu, 23 Mar 2006 12:59:22 GMT

;Calculate the factorial of a number
;(factorial 5) = 1 * 2 * 3 * 4 * 5 = 120
;(factorial 50) = 30414093201713378043612608166064768844377641568960512000000000000



(define factorial

  (lambda (n)

    (if (= n 0) 1

        (* n (factorial (- n 1))))))

DZone Snippets: Factorial code

factorials in many incarnations

Factorial in Scheme