Why is mpz_mul_ui() so slow in this loop?

[Richard B. Kreckel]

Hi,

Foursheds wrote:
> 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?

Well, using CLN [1] on top of GMP, this program

#include <iostream>
#include <cln/cln.h>
using namespace std;
using namespace cln;

int main()
{
     cl_I x = binomial(400000,200000);
     cout << x << endl;
}

takes less than half a second.

Cheers
    -richy.

[1] <http://www.ginac.de/CLN>
-- 
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>