nfloat_sqrt, nfloat_rsqrt

The square root is the truncated integer square root of the mantissa padded to 2n words, with an exactness flag (flint_mpn_sqrtrem). At one word on 64-bit machines it is computed in registers: a double-precision root (within 2^{12} of the exact root), one correction from the exact residual evaluated in double precision, and a final exact residual, which gives the floor and the exactness flag. At two words the root is first approximated at three words from the two-word reciprocal square root below and one Newton step with the exact residual, which certifies the truncation unless the guard word is within 3 units of 0 or 2^{64}.

The reciprocal square root refines a double-precision approximation by one Newton step at 128 bits (one word), or a two-word starting value by one Newton step with the residual evaluated exactly from the six-word product of the mantissa and the square of the starting value (two words). For n \ge 3 words, a fixed-point Newton iteration with an added third-order term yields the result with one guard word and an error of about one unit in the guard word. With directed rounding the truncation is certified from these error bounds, and in the rare uncertain cases the exact result \lfloor \sqrt{\lfloor z \rfloor} \rfloor is computed for z = 2^{3nw}/(4a) or 2^{3nw}/(2a), in terms of the n-word mantissa a and the word size w.

@misc{flint-doc-nfloat-nfloat-sqrt,
  author       = {{The FLINT team}},
  title        = {{nfloat\_sqrt, nfloat\_rsqrt (nfloat.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/nfloat/nfloat_sqrt.html},
  note         = {Generated 2026-10-20}
}