Anomaly in mpn_sqrtrem and mpn_rottrem

Torbjörn Granlund tg at gmplib.org
Fri Jun 12 07:04:29 UTC 2015


nisse at lysator.liu.se (Niels Möller) writes:

  Hmm. Or maybe this is stupid. I could stop insisting on using a full
  size inverse (so that A / x or E / x can be computed as a *single*
  mulhi), and instead work with a half-size inverse, so that the quotient
  is computed in two steps. Then inverse computation using a plain
  Newton-step per iteration should work fine.
  
We indeed do that already when performing division for its own sake;
compute an inverse which is not longer than half the quotient size.

We might want to look into the plain division-free sqrt(A) = A*sqrt(1/A)
approach before implementing a tricky division sqrt(A).


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


More information about the gmp-devel mailing list