[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?

An interesting question. First of all it seems that especially binomial
can be improved. Second I think there is a difference between
non-permanent caching and permanent caching. I see no problem
with non-permanent caching. For caching between calls I am not
sure, what is the best solution for a general purpose library.
I lean towards non-caching functions as standard, but it would
be nice to offer both versions in the library. The same problem
arises in prime? . Having a large table of small primes
improve the running time, but is a reasonable table
size 10^3, 10^4 or 10^5 ?

/Jens Axel



2013/4/8 Laurent <laurent.orseau at gmail.com>

> 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
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>
>


-- 
-- 
Jens Axel Søgaard
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130408/e942ac94/attachment.html>