[racket] Math - factorial.rkt, binomial.rkt and memoization

On Apr 8, 2013, at 3:11 PM, users-request at racket-lang.org wrote:

I would never recommend against using GMP for bignum code, but I use code like this for factorial, based on the idea of binary splitting:

(define (iota m n)
 (let loop ((result '())
	     (n (- n 1)))
   (if (<= m n)
	(loop (cons n result)
	      (- n 1))
	result)))

(define (partial-factorial m n)
 ;; computes the product (m+1) * ... * (n-1) * n
 (if (< (- n m) 10)
     (apply * (iota (+ m 1) (+ n 1)))
     (* (partial-factorial m (quotient (+ m n) 2))
        (partial-factorial (quotient (+ m n) 2) n))))

(define (factorial n)
 (partial-factorial 0 n))

In Gambit, even in the interpreter, this is pretty fast:

(define a (time (factorial 1000000)))
(time (factorial 1000000))
    6466 ms real time
    6462 ms cpu time (6011 user, 452 system)
    645 collections accounting for 370 ms real time (212 user, 160 system)
    1712593016 bytes allocated
    84704 minor faults
    32 major faults

Brad