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 \in [B^{-2}, 1) with one of its top two limbs nonzero, set (q, n + 2) to an approximation of 1/\sqrt{a} \in (1, B] with absolute error at most 4 B^{-n}/\sqrt{a}.

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

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

with u formed as a band of the product, u^2 from its top limbs and Tw by a middle product; the neglected term (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-10-20).