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 -- [EMAIL PROTECTED] -- http://www.cit.gu.edu.au/~arock/ School of Computing and Information Technology Griffith University -- Nathan, Brisbane, Queensland 4111, Australia
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
