[Haskell-cafe] faster factorial function via FFI?

Bryan O'Sullivan bos at serpentine.com
Wed Apr 25 00:07:38 EDT 2007


ajb at spamcop.net wrote:

> Yes and no.  Standard algorithms for computing and manipulating
> combinatorial-sized Integers strongly depend on the properties of
> your Integer implementation.
> 
> Manipulating lists of prime factors can also be more efficient,
> because most of the numbers you deal with are machine-word-sized.

Yep.  By the way, if approximations are good enough, the OP could use 
Gosper's formula:

gosper :: Integral a => a -> a

gosper n | n < 143 = let n' = fromIntegral n
                          g = sqrt ((n' * 2 + 1/3) * pi)
                                * n'**n' * exp (-n')
                      in round g

The accuracy of this approximation increases with n, until you hit the 
ceiling of whatever your Double implementation can manage (142, typically).

	<b


More information about the Haskell-Cafe mailing list