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
More information about the gmp-discuss
mailing list