Why is mpz_mul_ui() so slow in this loop?
Richard B. Kreckel
kreckel at ginac.de
Mon Jan 12 20:43:04 CET 2009
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/>
More information about the gmp-discuss
mailing list