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