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