[Haskell-cafe] faster factorial function via FFI?

[Dan Weston]

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 at spamcop.net wrote:
> 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