Binomial improvements

Torbjorn Granlund tg at gmplib.org
Sun Dec 11 04:29:46 CET 2011


Torbjorn Granlund <tg at gmplib.org> writes:

  OK, I've beaten my code some further.
  
  (1) Now the number of allowable factors that fit into a limb is tabled.
      This table takes into account that the mulN functions now shift out
      twos.
  (2) Less scratch space usage, for this needs the latest repo bdiv
      updates (allowing dividend/quotient operand overlap).
  (3) Misc minor optimisations.
  
  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
  the dividend, that might be possible.
  
  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?
  
  (If this code survives and in its present form, we need to generate the
  table.  I have dumbmp code for that.)

Forgot to point to the updated code: See http://gmplib.org/devel/ under
New binomial code.

-- 
Torbjörn


More information about the gmp-devel mailing list