Why is mpz_mul_ui() so slow in this loop?

[Torbjorn Granlund]

"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.

-- 
Torbjörn