Why is mpz_mul_ui() so slow in this loop?

Torbjorn Granlund tg at swox.com
Mon Jan 12 15:38:14 CET 2009

"David Gillies" <daggillies at gmail.com> writes:

  400k choose 200k is a 120 thousand digit number. GMP is fast. It is not magic.
Alas, I believe it could be computed quite fast using GMP, surely much
faster than the naive loop.

And the naive loop could be sped up by using mpz_divexact_ui for the
divisions, since the are known to exact.

A non-naive algorithm would do some sieving.  An example is the algorithm
at http://www.luschny.de/math/factorial/FastBinomialFunction.html.

Another nice speedup will be to use GMP 4.3, due out within days.


More information about the gmp-discuss mailing list