[Haskell-cafe] faster factorial function via FFI?
Stefan O'Rear
stefanor at cox.net
Mon Apr 23 19:36:12 EDT 2007
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
More information about the Haskell-Cafe
mailing list