Binomial improvements

[bodrato at mail.dm.unipi.it]

Ciao,

Il Dom, 11 Dicembre 2011 3:46 am, Torbjorn Granlund ha scritto:
> Now the code beats the repo code everywhere on my test machines.  I
> suspect that your improved basecase code might still be somewhat better
> in some area, but perhaps the difference is negligible?

Great!

On shell, for binomial(1234,k) the faster algorithm is:
 - with k < 14, the current GMP 5.0.1 basecase;
 - with 14 < k < 540, your_bdiv_uiui code;
 - with 540 < k (<620), the code using prime sieving.

> I suspect that one remaining optimisation for the smallest operands is
> to get rid of the final lshift.  By being cleverer with 2 removal from

You can get rid of the final lshift (and all i2cnt and j2cnt update code)
by pre-computing the exponent of 2 in advance:
cnt = popcount(k) + popcount(n - k) - popcount(n)

Regards,
m

-- 
http://bodrato.it/software/