Anomaly in mpn_sqrtrem and mpn_rottrem

Torbjörn Granlund tg at
Thu Jun 11 08:01:44 UTC 2015

nisse at (Niels Möller) writes:

  As far as I see, a plain Newton iteration on won't produce an x' inverse
  with 4n bits of accuracy. One would need aither two iterations, or some
  other trick, maybe mixing in some interpolation of x' - x.
I don't think one should struggle in order to get n -> 2n bits in a
Newtonian iteration.  It is enough to achieve n -> 2n-k for some
constant k.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list