[Haskell-cafe] faster factorial function via FFI?

ajb at spamcop.net ajb at spamcop.net
Tue Apr 24 23:00:03 EDT 2007


G'day all.

Quoting Bryan O'Sullivan <bos at serpentine.com>:

> Well... The zipWith (^) should be map (uncurry (^)).

Err... yes.

> And the performance of this approach is strongly dependent on the
> efficiency of your prime sieve, so you're moving the complexity around,
> not eliminating it.

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.

> The binary splitting method doesn't need a source of primes, and
> performs half decently on numbers such as fact 1e6 (5.5 million digits
> computed in about 5 seconds).

And on the other hand, if you're computing something other than just
a factorial (e.g. a complex combinatorial function, like the OP said),
prime factoring avoids large Integer divisions, which are often many
times more expensive than large Integer multiplications.

Cheers,
Andrew Bromage


More information about the Haskell-Cafe mailing list