<div dir="ltr"><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">> Would it make sense to use memoization more broadly for the definition of the factorial </span><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">> in the math lib, maybe with a `provide'd parameter to control how many values can be </span></div> <div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">> memoized?</span><br></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">An interesting question. First of all it seems that especially binomial</span></font></div> <div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">can be improved. Second I think there is a difference between </span></font></div><div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">non-permanent caching and permanent caching. I see no problem</span></font></div> <div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">with non-permanent caching. For caching between calls I am not</span></font></div><div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">sure, what is the best solution for a general purpose library.</span></font></div> <div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">I lean towards non-caching functions as standard, but it would</span></font></div><div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">be nice to offer both versions in the library. The same problem</span></font></div> <div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">arises in prime? . Having a large table of small primes </span></font></div><div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">improve the running time, but is a reasonable table</span></font></div> <div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">size 10^3, 10^4 or 10^5 ? </span></font></div><div style><br></div><div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">/Jens Axel</span></font></div> <div style><font face="arial, sans-serif"><span style="font-size:16.363636016845703px"><br></span></font></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/4/8 Laurent <span dir="ltr"><<a href="mailto:laurent.orseau@gmail.com" target="_blank">laurent.orseau@gmail.com</a>></span><br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div>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?<br> <a href="https://github.com/plt/racket/blob/master/collects/math/private/number-theory/factorial.rkt" target="_blank">https://github.com/plt/racket/blob/master/collects/math/private/number-theory/factorial.rkt</a><br><br> </div><div>While building big numbers (around 800!) I had to redefine my own factorial and binomial functions with memoization, otherwise it would take too long.<br><br>Also, probably `binomial' could take advantage of this memoization, just like `permutations' does.<br></div><a href="https://github.com/plt/racket/blob/master/collects/math/private/number-theory/binomial.rkt" target="_blank">https://github.com/plt/racket/blob/master/collects/math/private/number-theory/binomial.rkt</a><br> <br></div>Currently (in DrRacket, so not entirely accurate, but should be close enough):<br>> (time<br> (for ([n 100])<br> (binomial 10000 4000)))<br>cpu time: 4072 real time: 4075 gc time: 440<br>> (time<br> (for ([n 10000])<br> (binomial 800 400)))<br>cpu time: 9424 real time: 9430 gc time: 836<br>> (time (for ([i 1000])<br> (factorial 10000)))<br>cpu time: 11441 real time: 11630 gc time: 276<br><br><br></div>which makes it impractical in some cases.<span class="HOEnZb"><font color="#888888"><br> <br></font></span></div><span class="HOEnZb"><font color="#888888">Laurent<br></font></span></div> <br>____________________<br> Racket Users list:<br> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br> <br></blockquote></div><br><br clear="all"><div><br></div>-- <br>-- <br>Jens Axel Søgaard<br><br> </div>