Binomial improvements
Torbjorn Granlund
tg at gmplib.org
Sun Dec 11 18:27:12 CET 2011
bodrato at mail.dm.unipi.it writes:
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.
Nice, more improvement that I had anticipated. It is always nice to
reduce the number of distinct functions.
I suggest that we use Niels' proposed method for the really small
operands. Another precomputed table...
We actually have a table of primes and their inverses mod B
(trialdivtab.h). We could use that, together with a new, small table of
which entries we should use. But I suspect a new table will be better,
since we could use extremely streamlined code.
> 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)
That's very clever, and surely an improvement if popc_limb is fast.
--
Torbjörn
More information about the gmp-devel
mailing list