_flint_mpn_tdiv_qr, _flint_mpn_tdiv_qr_newton, _flint_mpn_tdiv_qr_unbalanced, _flint_mpn_tdiv_qr_preinv, _flint_mpn_tdiv_qr_preinvn
#include <flint/mpn_extras.h>void _flint_mpn_tdiv_qr(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)sourcevoid _flint_mpn_tdiv_qr_newton(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)sourcevoid _flint_mpn_tdiv_qr_unbalanced(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)sourcevoid _flint_mpn_tdiv_qr_preinv(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_srcptr binv, mp_size_t binvn)sourcevoid _flint_mpn_tdiv_qr_preinvn(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)sourceThe dispatcher behind flint_mpn_tdiv_qr and the individual algorithms for large operands, with its interface; in all of them r may be NULL. The Newton version views a and b as fixed-point numbers and computes m + 2 fraction limbs of a/b, where m = \mathit{an} - \mathit{bn} + 1; since the error is below 4 B^{-2} at the integer scale, the integer part is certified whenever the first fraction limb lies in [2, B-2], and the remainder then follows from a low product; otherwise the candidate quotient is corrected by O(1) steps using a full product. The unbalanced version (requires \mathit{an} > 2\mathit{bn} and \mathit{bn} \ge 3) divides blockwise, sharing one approximate inverse of b between the 2\mathit{bn} \times \mathit{bn} blocks. The preinv version requires (\mathit{binv}, \mathit{binvn} + 2) to be the output of _mp_real_inv_newton(binv, b, bn, binvn) with \mathit{binvn} \ge m + 2 and \mathit{an} \ge m + 2. The preinvn version uses flint_mpn_preinvn and flint_mpn_divrem_preinvn.
The FLINT team, “_flint_mpn_tdiv_qr, _flint_mpn_tdiv_qr_newton, _flint_mpn_tdiv_qr_unbalanced, _flint_mpn_tdiv_qr_preinv, _flint_mpn_tdiv_qr_preinvn (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.html (generated 2026-10-20).
@misc{flint-doc-mpn-extras-flint-mpn-tdiv-qr,
author = {{The FLINT team}},
title = {{\_flint\_mpn\_tdiv\_qr, \_flint\_mpn\_tdiv\_qr\_newton, \_flint\_mpn\_tdiv\_qr\_unbalanced, \_flint\_mpn\_tdiv\_qr\_preinv, \_flint\_mpn\_tdiv\_qr\_preinvn (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_tdiv_qr.html},
note = {Generated 2026-10-20}
}