[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