[Haskell-cafe] faster factorial function via FFI?
David Roundy
droundy at darcs.net
Mon Apr 23 20:14:39 EDT 2007
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
More information about the Haskell-Cafe
mailing list