Binomial improvements

Torbjorn Granlund tg at
Sat Dec 10 17:23:55 CET 2011

bodrato at writes:
  I tested the speed of your code with the many implementations I tested
  last year (all available on my web page, in the same file as fac_ui). On
  shell, for binomial(1234,k) the faster algorithm is:
   - with k < 35, the current GMP 5.0.1 basecase (or my slight update of it);
   - with 35 < k < 290, your_uiui4 code;
   - with 290 < k < 450, my mpz_pro_bin_uiui;
   - with 450 < k (<620), the code using prime sieving.
Darn, I had expected to displace the current GMP code always.

  mpz_pro_bin_uiui is a simple code: it computes the odd factor of the
  product n...(n-k+1) and divides by the odd component of the factorial of

That's more-or-less what my uiui4 does...

  I'm sure that we can get rid of it if we optimize your code.
It would be nice to reduce the number of algorithms, yes.  Perhaps some
of the ideas of my code could be moved to your algorithms, and thereby
displace my code.

  The main problem, as usual for "bidimensional" problems, will be how to
  trace the threshold. The value of k can be a first approximation.

What's the status of the div&con code now?  Still competitive someplace?


More information about the gmp-devel mailing list