Why is mpz_mul_ui() so slow in this loop?

[Foursheds]

Thanks Richard, I've had some difficulty getting cln working on Mac  
OSX, so I'l report back when I do.

Steve

On 12 Jan 2009, at 19:43, Richard B. Kreckel wrote:

> 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/>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at swox.com
> https://gmplib.org/mailman/listinfo/gmp-discuss