[racket] Math library kudos

From: Neil Toronto (neil.toronto at gmail.com)
Date: Wed Feb 20 10:34:12 EST 2013

On 02/19/2013 05:28 PM, Joe Gilray wrote:
> Racketeers,
> Thanks for putting together the fantastic math library.  It will be a
> wonderful resource.  Here are some quick impressions (after playing
> mostly with math/number-theory)

The thanks in this case goes to Jens Axel, who wrote almost all of the 
number theory functions.

> 1) The functions passed all my tests and were very fast.  If you need
> even more speed you can keep a list of primes around and write functions
> to use that, but that should be rarely necessary

I'm glad to hear they passed your tests as well. FWIW, when I reviewed 
Jens Axel's code before its initial commit, I didn't find any errors, 
either. (Which is amazing. Usually, adding another observer to a 
software system collapses its state to a mess of bug-ridden filth.)

> ...
> 2b) combinations calculator
> ; function that returns the number of combinations, not the combinations
> themselves
> ; faster than using n! / (r! (n-r)!)
> (define (combinations n r)
>    (cond
>      [(or (< n 0) (< r 0)) (error "combinations: illegal arguments, n
> and r must be >= 0")]
>      [(> r n) 0]
>      [else
>       (let lp ([mord n] [total 1] [mult #t])
>         (cond
>           [(or (= 0 mord) (= 1 mord)) total]
>           [(and mult (= mord (- n r))) (lp r total #f)]
>           [(and mult (= mord r)) (lp (- n r) total #f)]
>           [mult (lp (sub1 mord) (* total mord) #t)]
>           [else (lp (sub1 mord) (/ total mord) #f)]))]))

We have this one under the name `binomial'. But yours is about 8% faster 
in my tests with random inputs in [0..1000], which has me curious.

Neil ⊥

Posted on the users mailing list.