Why is mpz_mul_ui() so slow in this loop?

[David Gillies]

400k choose 200k is a 120 thousand digit number. GMP is fast. It is not magic.

On Mon, Jan 12, 2009 at 4:30 AM, Foursheds <foursheds at btinternet.com> wrote:
> 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?
>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at swox.com
> https://gmplib.org/mailman/listinfo/gmp-discuss
>
>



-- 
David Gillies
San Jose
Costa Rica