speedup help

[Andrew Rock]

On Tuesday, March 4, 2003, at 10:26 AM, Damien R. Sullivan wrote:

> So, I'm having to calculate 'n choose k' an awful lot.  At the moment 
> I've got
> this:
>
> 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
>     where
>     res = last * (m-n+1) `div` n
>     last = res
>

Try this:

comb :: Integral a => a -> a -> a
comb n r = c n 1 1
    where
    c n' r' p | r' > r    = p
              | otherwise = c (n' - 1) (r' + 1) (p * n' `div` r')

Cheers,
Rock.
--
Andrew Rock -- A.Rock@cit.gu.edu.au -- http://www.cit.gu.edu.au/~arock/
School of Computing and Information Technology
Griffith University -- Nathan, Brisbane, Queensland 4111, Australia