Binomial improvements
Torbjorn Granlund
tg at gmplib.org
Sat Dec 10 17:23:55 CET 2011
bodrato at mail.dm.unipi.it 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
k.
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.
Indeed.
What's the status of the div&con code now? Still competitive someplace?
--
Torbjörn
More information about the gmp-devel
mailing list