[Haskell-cafe] faster factorial function via FFI?

Dan Drake haskell-cafe at dandrake.org
Mon Apr 23 19:25:39 EDT 2007


On Mon, 23 Apr 2007 at 12:03PM -0700, David Roundy wrote:
> I'm curious: what is your application? I've never seen one in which
> factorials actually need be computed.  In physics, one factorial is
> generally divided by another (e.g. for combinatorics), so it's rarely
> wise to take the actual factorials.  And to be honest, we usually take
> the thermodynamic limit and then use Stirling's approximation.  I
> guess they also show up in Taylor expansions, but then we never go far
> enough for the factorial to be expensive.

This is combinatorics, so I can't just say "oh, this is small" and cross
it off like physicists do. :)

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

set partitions of [1..n] with "type p", where c_i is the number of i's
in p. Knuth, in his new Art of Computer Programming book, asks which
integer partition maximizes the number of set partitions. I'm trying to
figure it out.

Usings Ints everywhere isn't an option, because my final answers are
definitely Integers -- although I might try using Ints in some places. I
am still very new to Haskell and keep butting up against the type
system, so initially I made everything an Integer so that my code would
work!

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?!

Dan

-- 
Ceci n'est pas une .signature.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070423/33785848/attachment.bin


More information about the Haskell-Cafe mailing list