Why is mpz_mul_ui() so slow in this loop?

[Fredrik Johansson]

On Mon, Jan 12, 2009 at 11:30 AM, Foursheds <foursheds at btinternet.com> wrote:
> Hi,
> I'm a newbie to gmp,  I've just started using it because I need to calculate
> large Combinations up to n = 400000.
> I'm using an iterative method as factorials with mpz_fac_ui() are just too
> slow to calculate with numbers of this size.
> So to calculate C(400000,  200000) I would have:

There is a GMP function mpz_bin_uiui that does what you want, but
according to the manual it uses the same algorithm so it is probably
not much faster than your implementation.

For large binomial coefficients, it is much better to use prime
factorization. You could either find the factorizations of n!, k!,
(n-k)! and subtract exponents, or use a slightly more clever approach
as described here:
http://www.luschny.de/math/factorial/FastBinomialFunction.html. With
this algorithm computing C(400000, 200000) takes 0.4 seconds on my
computer (I implemented it using GMPY) compared to 14 seconds with the
builtin GMPY (GMP) function.

> When I comment out the multiply, the problem disappears, so it is the
> multiply causing the slow down; I assume this is because the value of C is
> becoming so large.

That's right.

> Is there anything I can do to resolve this problem?

Assuming you need full precision, computing C(400000,  200000) is
going to be slow (by some measure) regardless of the algorithm used.
If you only need a floating-point approximation like
1.25653730526692e+120409 you could use the direct formula n!/k!/(n-k)!
with approximate factorials computed e.g. by MPFR.

Fredrik