<div dir="ltr"><pre style><font color="#a52a2a">Hi Laurent,</font></pre><pre style><font color="#a52a2a"><br></font></pre><pre style><span style="color:rgb(165,42,42);font-family:arial">I am curious to see how fast the libgmp versions of factorial</span><br> </pre><pre style><font color="#a52a2a">and binomial are on your computer. Om my computer libgmp</font></pre><pre style><font color="#a52a2a">is much faster than the Racket one.</font></pre><pre style><font color="#a52a2a"><br> </font></pre><pre style><font color="#a52a2a">Since the libgmp versions converts a Racket bignum into</font></pre><pre style><font color="#a52a2a">a mpz, there is some overhead, so a proper solution</font></pre><pre style> <font color="#a52a2a">would be to use a Racket version for small numbers,</font></pre><pre style><font color="#a52a2a">and then call the libgmp for large numbers.</font></pre><pre style><font color="#a52a2a"><br></font></pre> <pre style><font color="#a52a2a">An even better solution would be to have a builtin bignum->mpz.</font></pre><pre><font color="#a52a2a"><br></font></pre><pre style><font color="#a52a2a">/Jens Axel</font></pre><pre style> <font color="#a52a2a"><br></font></pre><pre><font color="#a52a2a">#lang racket (require math/private/bigfloat/gmp) (require (for-syntax racket/base) ffi/unsafe ffi/unsafe/define racket/runtime-path) (define-runtime-path libgmp-so (case (system-type) [(macosx) '(so "libgmp.10.dylib")] [(windows) '(so "libgmp-10.dll")] [else '(so "libgmp")])) (define (get-gmp-fun name type) (get-ffi-obj name gmp-lib type (make-not-available name))) (define mpz-fac-ui (get-gmp-fun '__gmpz_fac_ui (_fun _mpz-pointer _int -> _mpz-pointer))) (define (fact n) (define n! (new-mpz)) (mpz-fac-ui n! n) (mpz->integer n!)) (define mpz-bin-ui (get-gmp-fun '__gmpz_bin_ui (_fun _mpz-pointer _mpz-pointer _int -> _mpz-pointer))) (define (bin n k) (define b (new-mpz)) (mpz-bin-ui b (integer->mpz n) k) (mpz->integer b)) (require (only-in math factorial)) (time (for ([i (in-range 2000 2100)]) (factorial i))) (time (for ([i (in-range 2000 2100)]) (fact i))) (require (only-in math binomial)) (time (for ([n 100]) (bin 10000 4000))) (time (for ([n 100]) (binomial 10000 4000)))</font><span style="color:rgb(165,42,42)"> </span></pre><div><br></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>