speed of unbalanced division

Torbjorn Granlund tg at gmplib.org
Sun Jun 2 17:39:25 CEST 2013

Zimmermann Paul <Paul.Zimmermann at inria.fr> writes:

  thank you for the feedback. Yes the new curve is not everywhere optimal, but
  the important thing is that it is much more regular, which is critical
  for algorithms assuming that when we cut both numerator and divisor (for
  a fixed-size quotient) the time will decrease (or at least not increase).
The new code is typically faster and more monotonous in dividend size.
But there are ranges of non-monotonousness, see for example
http://gmplib.org/devel/244844.png, and ranges of slowdown, such as

I added lots of diagrams to http://gmplib.org/devel/ in order to
evaluate strategies.


More information about the gmp-devel mailing list