Re: [Haskell-cafe] faster factorial function via FFI?

A thing of beauty is a joy forever. Simple, fast, elegant. If I learn any more from this list, someone is going to start charging me tuition! :) Dan ajb@spamcop.net wrote:

G'day all.

Quoting Dan Weston :

...

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