[Haskell-cafe] faster factorial function via FFI?
westondan at imageworks.com
Tue Apr 24 13:25:18 EDT 2007
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! :)
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)
> 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.
> Andrew Bromage
More information about the Haskell-Cafe