# 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

```