mpn_sqrtrem{1,2} - patch for pure C implem

paul zimmermann Paul.Zimmermann at
Fri Jun 9 11:41:24 UTC 2017

       Dear Marco,

> Finally we can totally skip the first approximation and directly compute
> i' = T1[h(a)] + l(a) * T2[h(a)]
> using a piece-wise linear function.

yes, we noticed with Niels that we can replace most of the arithmetic in the
first Newton iteration by another table lookup.

Not sure l(a) is better than using the upper (say) 16 bits of a, in case you
want a 16-bit approximation i'.

To compute T1 and T2 you have two choices:

1) either try to minimize the maximal error after the first Newton iteration
   (i.e., on i')

2) or try to minimize the maximal error after k iterations. See the article
   by Jean-Michel Muller and Peter Kornerup:


More information about the gmp-devel mailing list