FLINT3.7.0-dev

flint_mpn_divhigh, flint_mpn_invhigh, flint_mpn_divhigh_exact

Synopsis#include <flint/mpn_extras.h>
ulong flint_mpn_divhigh(nn_ptr q, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong n)source
ulong flint_mpn_invhigh(nn_ptr q, nn_srcptr b, slong bn, slong n)source
int flint_mpn_divhigh_exact(nn_ptr q, ulong * s, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong n)source

The quotient with the contract above (n≥1n \ge 1); the first two return ss, the third writes it to s and returns the inexact flag. qq must not overlap the operands.

The operands are truncated to n+2n + 2 limbs (an error below 8B−(n+2)8 B^{-(n+2)} on the quotient, i.e. 8/B8/B units). With n=1n = 1 the top two limbs of each operand go through two 3/23/2 divisions on 64-bit machines (the truncation to two limbs costs 8 units); a divisor of one limb is a chain of 2/12/1 divisions, a short one (FLINT_MPN_DIV_SMALL_SHAPE) the register-based division, both exact; longer divisors use the schoolbook approximate division with the 3/23/2 inverse up to 80 result limbs and flint_mpn_divapprox beyond, which give the floor or one more. Beyond 80 limbs, a numerator of at most n/8n/8 limbs (in particular flint_mpn_invhigh) multiplies the approximate reciprocal of the divisor (flint_mpn_invapprox, with the lower Newton cutoffs of the inversion) instead, within two units. The exact variant forms the numerator ABk/2sA B^k / 2^s exactly (extending the divisor instead when k<0k < 0) and divides with remainder.

Cite this page

The FLINT team, “flint_mpn_divhigh, flint_mpn_invhigh, flint_mpn_divhigh_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_divhigh.html (generated 2026-11-20).