FLINT3.7.0-dev
/

_mp_real_rsqrt_newton_basecase, _mp_real_rsqrt_newton

Synopsis#include <flint/mp_real.h>
void _mp_real_rsqrt_newton_basecase(nn_ptr q, nn_srcptr a, slong an, slong n)source
void _mp_real_rsqrt_newton(nn_ptr q, nn_srcptr a, slong an, slong n)source

For a∈[B−2,1)a \in [B^{-2}, 1) with one of its top two limbs nonzero, set (q,n+2)(q, n + 2) to an approximation of 1/a∈(1,B]1/\sqrt{a} \in (1, B] with absolute error at most 4B−n/a4 B^{-n}/\sqrt{a}.

The basecase combines flint_mpn_sqrtrem and flint_mpn_tdiv_qr. The main function performs third-order steps from T≈a−1/2T \approx a^{-1/2} at about n/3n/3 limbs:

u=1−aT2,w=u2+3u28,q=T+Tw,u = 1 - aT^2, \qquad w = \frac{u}{2} + \frac{3u^2}{8}, \qquad q = T + Tw,

with uu formed as a band of the product, u2u^2 from its top limbs and TwTw by a middle product; the neglected term (5/16)u3T(5/16)u^3 T is below the rounding. flint_mpn_sqrtrem takes its reciprocal square root from this function in its Newton regime.

Cite this page

The FLINT team, “_mp_real_rsqrt_newton_basecase, _mp_real_rsqrt_newton (mp_real.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mp_real/_mp_real_rsqrt_newton_basecase.html (generated 2026-11-02).