Binomial improvements

[bodrato at mail.dm.unipi.it]

Ciao!

Il Ven, 9 Dicembre 2011 2:39 pm, Torbjorn Granlund ha scritto:
> The code is about 2.5 times faster than the old code, at least for
> arguments of the type 2n over n.  (This code as well as the old code is
> still slow for large operands; we need a factorisation based algorithm
> over a threshold.  I think Marco is working on that.)

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.

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.
I'm sure that we can get rid of it if we optimize your 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.

Regards,
Marco

-- 
http://bodrato.it/software/combinatorics.html#bin_uiui