G'day all. On Mon, Mar 03, 2003 at 04:59:21PM -0800, Hal Daume III wrote:
I think you would get a big speed-up if you got rid of all the rational stuff and just used:
comb m n = fact m `div` (fact n * fact (m-n))
Or, even better, if you didn't multiply stuff that you're just going to divide out in the first place. choose :: (Integral a) => a -> a -> Integer choose m n | m < 0 = 0 | n < 0 || n > m = 0 | n > m `div` 2 = choose' n (m-n) | otherwise = choose' (m-n) n where choose' i' j' = let i = toInteger i' j = toInteger j' in productRange (i+1) j `div` factorial j factorial :: (Integral a) => a -> Integer factorial n = productRange 1 n productRange :: (Integral a) => Integer -> a -> Integer productRange b n | n < 5 = case n of 0 -> 1 1 -> b 2 -> b*(b+1) 3 -> (b*(b+1))*(b+2) 4 -> (b*(b+3))*((b+1)*(b+2)) _ -> 0 | otherwise = let n2 = n `div` 2 in productRange b n2 * productRange (b+toInteger n2) (n-n2) Note that productRange uses a divide-and-conquer algorithm. The reason for this is that it's more efficient to multiply similarly-sized Integers than dissimilarly-sized Integers using GMP. Cheers, Andrew Bromage