FLINT3.7.0-dev
/

_mp_real_inv_newton_basecase, _mp_real_inv_newton

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

For a \in [1/B, 1) with a_{a_n - 1} \ne 0, set (q, n + 2) to an approximation of 1/a \in (1, B] with absolute error at most 4 B^{-n}/a.

The basecase takes the truncated reciprocal of the top \min(a_n, n + 1) limbs of a by _flint_mpn_inv_basecase. The main function runs a Newton iteration on middle products, each step of second order, T' = T + T(1 - aT), or third order, T' = T(1 - e + e^2) with e = aT - 1; the third-order step is used for 24 \le n \le 80 and n \ge 1000. See Integer division and Newton iteration.

Cite this page

The FLINT team, “_mp_real_inv_newton_basecase, _mp_real_inv_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_inv_newton_basecase.html (generated 2026-10-20).