Anomaly in mpn_sqrtrem and mpn_rootrem

Torbjörn Granlund tg at
Wed Jul 8 21:57:48 UTC 2015

nisse at (Niels Möller) writes:

  There are divisions also in the newton iteration, right? Then a single
  division in the computation of the initial value is likely a win, if it
  saves two or more iterations in the loop.
There are GMP division operations, but these are not likely going to hit
any hardware division.

  Precomputing an inverse of k makes sense, if there's more than one
  division by k.


I think we should consider using special starting approximations for
important k, and then perhaps this general 5-bit code for the remaining

Surely the most important k is 3 (assuming 2 is always handled by the
sqrt code).  We could provide a 8-bit table here which just performs
masking and indexing.  Some other small k values might deserve such
tables too.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list