Andrew J Bromage
Tue, 4 Mar 2003 12:25:01 +1100
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
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
= 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.