[racket] Math - factorial.rkt, binomial.rkt and memoization
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>