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

On Mon, Apr 8, 2013 at 9:34 PM, Bradley Lucier <lucier at math.purdue.edu>wrote:

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


Indeed, it's impressively fast!
% racket fast-factorial.rkt
cpu time: 5760 real time: 5771 gc time: 28

Probably this should replace the default factorial version then.

Laurent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130409/eace779f/attachment.html>