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 \le \mathit{bn} \le FLINT_MPN_DIV_SMALL_BN (7), with the conventions of flint_mpn_tdiv_qr (r may be NULL; no normalisation of b 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 \mathit{bn} = 1) and, for \mathit{bn} \ge 3, the subtraction of a 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 \mathit{an}; beyond about 3\mathit{bn} limbs the schoolbook division is faster for \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-10-20).