Why is mpz_mul_ui() so slow in this loop?
foursheds at btinternet.com
Tue Jan 13 14:24:22 CET 2009
Thanks Richard, I've had some difficulty getting cln working on Mac
OSX, so I'l report back when I do.
On 12 Jan 2009, at 19:43, Richard B. Kreckel wrote:
> 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
>> 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 &
>> 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  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.
>  <http://www.ginac.de/CLN>
> Richard B. Kreckel
> gmp-discuss mailing list
> gmp-discuss at swox.com
More information about the gmp-discuss