speedup help

[Andrew J Bromage]

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