[Haskell-cafe] faster factorial function via FFI?

[Stefan O'Rear]

On Mon, Apr 23, 2007 at 06:25:39PM -0500, Dan Drake wrote:
> 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

That formula isn't even correct.  Consider p = replicate n 1, that is
n partitions each of size 1.  There is only one way to do this - put
each element in its own partition.  However, your formula gives:

                     n!
---------------------------------------------
1! * 1! * 1! * 1! ... * 1^n * 2^0 * 3^0 * ...

==

n!
--
1

It might go faster if you used the right equation.

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

Don't forget than n! is easily partially factored - it is 1 * 2 * 3 * ... * n

Stefab