FLINT3.7.0-dev

_flint_mpn_tdiv_qr_small

Synopsis#include <flint/mpn_extras.h>
void _flint_mpn_tdiv_qr_small(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)source

Euclidean division for 1≤bn≤1 \le \mathit{bn} \le FLINT_MPN_DIV_SMALL_BN (7), with the conventions of flint_mpn_tdiv_qr (rr may be NULL; no normalisation of bb is needed). There is one code path per divisor length, in which the normalised divisor and the partial remainder are kept in registers and the dividend is normalised on the fly; each quotient limb takes a 3/2 division (2/1 for bn=1\mathit{bn} = 1) and, for bn≥3\mathit{bn} \ge 3, the subtraction of a 1×(bn−2)1 \times (\mathit{bn} - 2) product, as in GMP's mpn_sbpi1_div_qr but without function calls or memory traffic. The cost is linear in an\mathit{an}; beyond about 3bn3\mathit{bn} limbs the schoolbook division is faster for bn≥4\mathit{bn} \ge 4.

Cite this page

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