speedup help

Damien R. Sullivan dasulliv@cs.indiana.edu
Mon, 3 Mar 2003 19:26:55 -0500

So, I'm having to calculate 'n choose k' an awful lot.  At the moment I've got

comb :: Integer -> Integer -> Integer
comb m 0 = 1
comb m n = (numerator(toRational (fact m) / toRational (fact n * fact (m-n))))
where fact is a memoized factorial function.  It's not perfectly memoized,
though; I use lists, since that's easier by default.  They should be arrays,
and possibly just changing that would speed comb up a lot.  (Comb is currently
40% of runtime, fact is 23%.)  But I think it should be possible to speed up
comb itself, too.

comb is only called from here:
sumbn n = sum [ bernoulli i * fromIntegral(comb (n+1) i) | i <- [0 .. n-1] ]

Here was one try:

fcomb :: Integer -> Integer -> Integer
fcomb m 0 = 1
fcomb m n = res 
    res = last * (m-n+1) `div` n 
    last = res

except, obviously, this doesn't work.  I hope it's clear what I'm trying to
do, or what I would be in a more imperative language -- in C I'd probably have
some static variable in fcomb.  I figure monads are needed, but I've been
unable to figure them out enough to apply them here.  Will the monadism
propagate all the way up and require changing lots of function types?  Bleah.
I'm using ghc, can I sneak some mutable in here instead?

Any advice?  Also on using arrays, where my parameters come off the command
line.  I imagine in C++ I'd just precompute a bunch of tables and then just
use those values in the actual algorithm.


-xx- Damien X-) 

(if you're curious, this is for a class, but not a class on using Haskell.  I
chose to use Haskell for this assignment after ghc -O, to my surprise,
outperformed ocaml.  I suspect GMP deserves the real credit, but hey.)