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

From: Laurent (laurent.orseau at gmail.com)
Date: Mon Apr 8 12:33:11 EDT 2013

Would it make sense to use memoization more broadly for the definition of
the factorial in the math lib, maybe with a `provide'd parameter to control
how many values can be memoized?
https://github.com/plt/racket/blob/master/collects/math/private/number-theory/factorial.rkt

While building big numbers (around 800!) I had to redefine my own factorial
and binomial functions with memoization, otherwise it would take too long.

Also, probably `binomial' could take advantage of this memoization, just
like `permutations' does.
https://github.com/plt/racket/blob/master/collects/math/private/number-theory/binomial.rkt

Currently (in DrRacket, so not entirely accurate, but should be close
enough):
> (time
   (for ([n 100])
     (binomial 10000 4000)))
cpu time: 4072 real time: 4075 gc time: 440
> (time
   (for ([n 10000])
     (binomial 800 400)))
cpu time: 9424 real time: 9430 gc time: 836
> (time (for ([i 1000])
          (factorial 10000)))
cpu time: 11441 real time: 11630 gc time: 276


which makes it impractical in some cases.

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

Posted on the users mailing list.