Binomial -- faster for large args

Kevin Ryde user42 at zip.com.au
Sat May 15 01:50:16 CEST 2004


abbott at module.dima.unige.it writes:
>
> The following routine (called "binomial") seems to be usefully
> faster than that supplied with GMP 4.1.3 (on my Linux/Athlon box)
> at least for larger values of n and r

If it gets into karatsuba etc range for some muls then that's likely.

>     mpz_gcd(g,num,den);
>     mpz_divexact(num,num,g);
>     mpz_divexact(den,den,g);
>     mpz_mul(ans,ans,num);
>     mpz_divexact(ans,ans,den);

gcd is normally pretty slow, without actually measuring it I'd imagine
just dividing would be better.

Oh, and divexact is not yet sub-quadratic, plain mpz_tdiv_q might be
faster.


More information about the gmp-devel mailing list