FLINT3.7.0-dev
/

flint_mpn_bdiv_qr_1, flint_mpn_bdiv_qr_classical, _flint_mpn_bdiv_qr_classical_preinv, flint_mpn_bdiv_qr_karp_markstein

Synopsis#include <flint/mpn_extras.h>
void flint_mpn_bdiv_qr_1(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_limb_t b, mp_size_t n)source
void flint_mpn_bdiv_qr_classical(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_size_t n)source
void _flint_mpn_bdiv_qr_classical_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 n)source
void flint_mpn_bdiv_qr_karp_markstein(mp_ptr q, mp_ptr r, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_size_t n)source

The algorithms behind flint_mpn_bdiv_qr, with its interface: a one-limb divisor; the block algorithm running from the bottom up in blocks of \mathit{bn} limbs, each costing one low and one high \mathit{bn} \times \mathit{bn} product (used by the dispatcher when \mathit{bn} < n/2; the preinv version takes b^{-1} \bmod B^{\mathit{bn}}); and the Karp–Markstein form, which uses a half-precision inverse from flint_mpn_binv and one refinement step [KM1997].

References#

  • [KM1997] A. H. Karp and P. Markstein, "High-precision division and square root", ACM Transactions on Mathematical Software 23:4 (1997), 561–589
Cite this page

The FLINT team, “flint_mpn_bdiv_qr_1, flint_mpn_bdiv_qr_classical, _flint_mpn_bdiv_qr_classical_preinv, flint_mpn_bdiv_qr_karp_markstein (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/flint_mpn_bdiv_qr_1.html (generated 2026-10-20).