[racket] Math - factorial.rkt, binomial.rkt and memoization

Hi Laurent,


I am curious to see how fast the libgmp versions of factorial

and binomial are on your computer. Om my computer libgmp

is much faster than the Racket one.


Since the libgmp versions converts a Racket bignum into

a mpz, there is some overhead, so a proper solution

would be to use a Racket version for small numbers,

and then call the libgmp for large numbers.


An even better solution would be to have a builtin bignum->mpz.


/Jens Axel


#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)))




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/ae97e9a8/attachment-0001.html>