# speedup help

**Andrew Rock
**
A.Rock@cit.gu.edu.au

*Tue, 4 Mar 2003 11:20:02 +1000*

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