_flint_mpn_divrem_basecase_preinv1, _flint_mpn_div_basecase_preinv1, _flint_mpn_divapprox_basecase_preinv1, _flint_mpn_divrem_preinv1, _flint_mpn_divapprox_preinv1, _flint_mpn_divrem_n_divconquer_preinv1, _flint_mpn_divapprox_n_divconquer_preinv1, _flint_mpn_tdiv_qr_divconquer, _flint_mpn_tdiv_q_divconquer

The schoolbook functions require $\mathit{dn} \ge 3$ and $\mathit{nn} \ge \mathit{dn}$. _flint_mpn_divrem_basecase_preinv1 divides $(\mathit{np}, \mathit{nn})$ in place by $(\mathit{dp}, \mathit{dn})$: the remainder is left in $(\mathit{np}, \mathit{dn})$, the low $\mathit{nn} - \mathit{dn}$ limbs of the quotient are written to qp and its top limb is returned. _flint_mpn_div_basecase_preinv1 computes the same quotient but develops the last $\mathit{dn} - 2$ quotient limbs with a truncated divisor (correcting the result when needed), and _flint_mpn_divapprox_basecase_preinv1 computes an approximate quotient (correct or one too large) the same way; both destroy $(\mathit{np}, \mathit{nn})$.

_flint_mpn_divrem_preinv1 and _flint_mpn_divapprox_preinv1 are the analogues for $\mathit{dn} \ge 2$ with divide and conquer steps above FLINT_MPN_DIV_DC_CUTOFF and FLINT_MPN_DIVAPPR_DC_CUTOFF limbs (ports of mpn_dcpi1_div_qr and mpn_dcpi1_divappr_q); tp must have room for $\mathit{dn}$ limbs. The balanced $2n/n$ steps ($n \ge 6$, tp of $n$ limbs) are _flint_mpn_divrem_n_divconquer_preinv1 and _flint_mpn_divapprox_n_divconquer_preinv1. The latter is not correct up to one unit: each level of its recursion can make the quotient a few units too large (never too small; at most 8 units in tests with $n \le 200$), so it is used with a guard limb.

_flint_mpn_tdiv_qr_divconquer and _flint_mpn_tdiv_q_divconquer are Euclidean divisions for any divisor with $\mathit{bn} \ge 2$ ($r$ may be NULL). When the quotient is about as long as the divisor or longer, a normalised copy is divided as above. For short quotients ($m$ limbs), the top $2m$ limbs of $a$ are divided by the top $m$ limbs of $b$ and the quotient (at most two too large) is corrected using its product with the ignored divisor limbs. Quotients of $m \le \mathit{bn} + 2$ limbs from FLINT_MPN_DIVAPPROX_SHORT_CUTOFF limbs use a short division in the style of Mulders [Mul2000; HZ2011]: the quotient with one guard limb is computed from the top $m + 1$ limbs of $a$ and $b$ only, recursively, the correction for the rest of the divisor being needed only above the current precision, i.e. as a high product.

The cutoffs are machine dependent and measured by src/mpn_extras/tune/tune-div.c for flint-mparam.h; the divide and conquer cutoffs must be at least 6.

@misc{flint-doc-mpn-extras-flint-mpn-divrem-basecase-preinv1,
  author       = {{The FLINT team}},
  title        = {{\_flint\_mpn\_divrem\_basecase\_preinv1, \_flint\_mpn\_div\_basecase\_preinv1, \_flint\_mpn\_divapprox\_basecase\_preinv1, \_flint\_mpn\_divrem\_preinv1, \_flint\_mpn\_divapprox\_preinv1, \_flint\_mpn\_divrem\_n\_divconquer\_preinv1, \_flint\_mpn\_divapprox\_n\_divconquer\_preinv1, \_flint\_mpn\_tdiv\_qr\_divconquer, \_flint\_mpn\_tdiv\_q\_divconquer (mpn\_extras.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/mpn_extras/_flint_mpn_divrem_basecase_preinv1.html},
  note         = {Generated 2026-11-02}
}