[Haskell-cafe] faster factorial function via FFI?

[David Roundy]

On Mon, Apr 23, 2007 at 06:25:39PM -0500, Dan Drake wrote:
> I'm finding the number of set partitions that correspond to a certain
> integer partition. If p = p_1, p_2,...,p_k is an integer partition of n,
> then there are
> 
>                                    n!
>              ----------------------------------------------
>              p_1! * p_2! * ... * p_k! * 1^c_1 * ... * k^c_k
...
> Doing cancellation before computing the factorials is also an option,
> but in general I'll have a lot of small numbers on the bottom, and would
> need to do a lot of integer factoring on the top -- and my impression is
> that integer factoring is quite slow, faster than integer multiplication
> -- that's why RSA works, right?!

In many cases, cancelling out the largest factorial on the bottom should be
a win:

                        n!
x =          ------------------------
             p_1! * p_2! * ... * p_k!

x n ps = product [max ps..n] / (product $ concat $ map (\p->[1..p]) $ delete (max ps) ps)

and yes, that's pseudocode... max has wrong type.

of course, this only helps if you've got a big p.  At least there's always
a biggest p.
-- 
David Roundy
Department of Physics
Oregon State University