[Haskell-cafe] faster factorial function via FFI?

ajb at spamcop.net ajb at spamcop.net
Tue Apr 24 00:07:31 EDT 2007


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


More information about the Haskell-Cafe mailing list