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