Why is mpz_mul_ui() so slow in this loop?

[Foursheds]

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