speed enhancement

Torbjorn Granlund tg at gmplib.org
Wed Sep 29 09:44:18 CEST 2010

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

  the reason is simple: with remp=NULL mpn_rootrem computes an extra limb of
  the k-th root, which in most cases is enough to deduce if the remainder is
  zero or not (however it seems the code does not cover the corner case).
Are you implying we might have a bug here, if we elsewhere assume it
computes floor(A^(1/B))?

  > I haven't looked at the code recently, but I suspect mpn_rootrem is
  > cleverer about the intermediate values during the Newton iteration,
  > allowing it to omit a correction step at the end?
  > In mpn_sqrtrem, instead of using a full multiply for the fonal
  > adjustment, perhaps we could get away with a short multiply, or even
  > just a O(n) column multiply?
  yes, see my previous mail.
Which mail?  (Subject+date please.)


More information about the gmp-devel mailing list