[Haskell-cafe] faster factorial function via FFI?

[ajb at spamcop.net]

G'day all.

Quoting Dan Weston <westondan at imageworks.com>:

> Why all the fuss? n! is in fact very easily *completely* factored into
> prime numbers [...]

It's even easier than that.

primePowerOf :: Integer -> Integer -> Integer
primePowerOf n p
  = (n - s p n) `div` (p-1)
  where
    s p 0 = 0
    s p n = let (q,r) = n `divMod` p in s p q + r

factorisedFactorial :: Integer -> [(Integer,Integer)]
factorisedFactorial n = [ (p, primePowerOf n p) | p <- primesUpTo n ]

factorial :: Integer -> Integer
factorial = product . zipWith (^) . factorisedFactorial

(Implement primesUpTo using your favourite prime sieve.)

Manipulating prime factors like this is sometimes MUCH faster than
computing products for this kind of combinatorial work, because Integer
division is quite expensive.

Cheers,
Andrew Bromage