# Why is mpz_mul_ui() so slow in this loop?

Foursheds foursheds at btinternet.com
Mon Jan 12 11:30:36 CET 2009

```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:

unsigned long n = 400000, k = 200000;
mpz_t C;
mpz_init_set_ui(C, n); // start when k=1 C=n
for(long i=2; i<=k; i++)
{
mpz_mul_ui(C, C, n-(i-1));
mpz_tdiv_q_ui (C, C, i);
}

I'm getting the correct result, but this loop of 200k multiply &
divides is taking 15 seconds!
I haven't profiled it yet, but obviously, doing the same amount of
multiply & divides with a double takes a fraction of a second.

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.

Is there anything I can do to resolve this problem?

Thanks

Steve

P.S. using doubles the same calculation would be:
c = ((double)(n-(i-1))/i)*c;

Am I right in thinking there's no way to do that on a single line
using mpz_t?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20090112/761bf6b6/attachment.html
```