Anomaly in mpn_sqrtrem and mpn_rootrem

[Torbjörn Granlund]

nisse at lysator.liu.se (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.

Yes.

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

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.

-- 
Torbjörn
Please encrypt, key id 0xC8601622