FLINT3.7.0-dev

_flint_mpn_tdiv_qr, _flint_mpn_tdiv_qr_newton, _flint_mpn_tdiv_qr_unbalanced, _flint_mpn_tdiv_qr_preinv, _flint_mpn_tdiv_qr_preinvn

Synopsis#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)source
void _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)source
void _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)source
void _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)source
void _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)source

The 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.

Cite this page

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).