FLINT3.7.0-dev

flint_mpn_sqrthigh, flint_mpn_sqrthigh_exact, flint_mpn_sqrthigh_exact_half, flint_mpn_sqrthigh_exact_rem, flint_mpn_rsqrthigh, flint_mpn_rsqrthigh_exact

Synopsis#include <flint/mpn_extras.h>
void flint_mpn_sqrthigh(nn_ptr s, nn_srcptr a, slong an, int t, slong n)source
int flint_mpn_sqrthigh_exact(nn_ptr s, nn_srcptr a, slong an, int t, slong n)source
int flint_mpn_sqrthigh_exact_half(nn_ptr s, nn_srcptr a, slong an, int t, slong n)source
int flint_mpn_sqrthigh_exact_rem(nn_ptr s, nn_ptr r, nn_srcptr a, slong an, int t, slong n)source
void flint_mpn_rsqrthigh(nn_ptr y, nn_srcptr a, slong an, int t, slong n)source
int flint_mpn_rsqrthigh_exact(nn_ptr y, nn_srcptr a, slong an, int t, slong n)source

The square root and the reciprocal square root with the contract above (n≥1n \ge 1 for the approximations; the exact variants also accept n=0n = 0, a single limb). flint_mpn_sqrthigh_exact_half returns more precisely 0 (exact), 1 (the root within the first half unit above the floor), 2 (exactly half a unit above: a tie, which needs dropped limbs of aa) or 3 (above that), which decides every rounding mode at n+1n + 1 limbs; it forms the remainder of the integer root (for the floor FF of the radicand XX with the dropped fraction ff, the root exceeds F+1/2F + 1/2 iff X−F2>FX - F^2 > F, or X−F2=FX - F^2 = F and f≥1/4f \ge 1/4), which the plain variant skips; flint_mpn_sqrthigh_exact_rem writes that remainder to r (n+2n + 2 limbs, zero-padded) and returns the inexact flag. flint_mpn_rsqrthigh_exact requires M<1M < 1.

On 64-bit machines, roots of one and two limbs (two and three with the guard limb) come from the register kernels of mpn_extras/fp_small.h: the double precision value refined by one Newton step with the exact residual at 128 bits (_flint_mpn_small_rsqrt_2, within 8 units), the square root as the product with the operand (within 24 units) and a further step at three limbs (within 3 units, resp. 2 for the reciprocal square root). Longer square roots are flint_mpn_sqrtrem of the operand truncated or zero-extended to 2(n+1)2(n+1) limbs below FLINT_MPN_SQRTREM_NEWTON_CUTOFF/4/4 result limbs and the Newton iteration of mp_real beyond. Longer reciprocal square roots use a Newton iteration on short products from the two-limb base (error below 196 units at four limbs, below 1.03 beyond) up to 96 limbs and the iteration of mp_real beyond. The exact variants take flint_mpn_sqrtrem of the exact radicand (for the reciprocal, ⌊B2(n+1)+an/(22−ta)⌋\lfloor B^{2(n+1)+\mathit{an}} / (2^{2-t} a) \rfloor by a division with remainder), the result being exact iff all remainders vanish.

Cite this page

The FLINT team, “flint_mpn_sqrthigh, flint_mpn_sqrthigh_exact, flint_mpn_sqrthigh_exact_half, flint_mpn_sqrthigh_exact_rem, flint_mpn_rsqrthigh, flint_mpn_rsqrthigh_exact (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/flint_mpn_sqrthigh.html (generated 2026-11-20).