# speedup help

**Andrew J Bromage
**
ajb@spamcop.net

*Tue, 4 Mar 2003 12:25:01 +1100*

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