FLINT3.7.0-dev
/

_flint_mpn_divrem_basecase_preinv1, _flint_mpn_div_basecase_preinv1, _flint_mpn_divapprox_basecase_preinv1, _flint_mpn_divrem_preinv1, _flint_mpn_divapprox_preinv1, _flint_mpn_divrem_n_divconquer_preinv1, _flint_mpn_divapprox_n_divconquer_preinv1, _flint_mpn_tdiv_qr_divconquer, _flint_mpn_tdiv_q_divconquer

Synopsis#include <flint/mpn_extras.h>
mp_limb_t _flint_mpn_divrem_basecase_preinv1(mp_ptr qp, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_limb_t dinv)source
mp_limb_t _flint_mpn_div_basecase_preinv1(mp_ptr qp, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_limb_t dinv)source
mp_limb_t _flint_mpn_divapprox_basecase_preinv1(mp_ptr qp, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_limb_t dinv)source
mp_limb_t _flint_mpn_divrem_preinv1(mp_ptr qp, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_limb_t dinv, mp_ptr tp)source
mp_limb_t _flint_mpn_divapprox_preinv1(mp_ptr qp, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_limb_t dinv, mp_ptr tp)source
mp_limb_t _flint_mpn_divrem_n_divconquer_preinv1(mp_ptr qp, mp_ptr np, mp_srcptr dp, mp_size_t n, mp_limb_t dinv, mp_ptr tp)source
mp_limb_t _flint_mpn_divapprox_n_divconquer_preinv1(mp_ptr qp, mp_ptr np, mp_srcptr dp, mp_size_t n, mp_limb_t dinv, mp_ptr tp)source
void _flint_mpn_tdiv_qr_divconquer(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_q_divconquer(mp_ptr Q, mp_srcptr A, mp_size_t An, mp_srcptr B, mp_size_t Bn)source

Division with a normalised divisor and the 3/2 inverse dinv = flint_mpn_preinv1 of its top two limbs, ported from GMP's internal mpn_sbpi1_*, mpn_dcpi1_*, mpn_tdiv_qr and mpn_div_q functions, with FLINT's multiplication in the divide and conquer steps [BurZie1998].

The schoolbook functions require \mathit{dn} \ge 3 and \mathit{nn} \ge \mathit{dn}. _flint_mpn_divrem_basecase_preinv1 divides (\mathit{np}, \mathit{nn}) in place by (\mathit{dp}, \mathit{dn}): the remainder is left in (\mathit{np}, \mathit{dn}), the low \mathit{nn} - \mathit{dn} limbs of the quotient are written to qp and its top limb is returned. _flint_mpn_div_basecase_preinv1 computes the same quotient but develops the last \mathit{dn} - 2 quotient limbs with a truncated divisor (correcting the result when needed), and _flint_mpn_divapprox_basecase_preinv1 computes an approximate quotient (correct or one too large) the same way; both destroy (\mathit{np}, \mathit{nn}).

_flint_mpn_divrem_preinv1 and _flint_mpn_divapprox_preinv1 are the analogues for \mathit{dn} \ge 2 with divide and conquer steps above FLINT_MPN_DIV_DC_CUTOFF and FLINT_MPN_DIVAPPR_DC_CUTOFF limbs (ports of mpn_dcpi1_div_qr and mpn_dcpi1_divappr_q); tp must have room for \mathit{dn} limbs. The balanced 2n/n steps (n \ge 6, tp of n limbs) are _flint_mpn_divrem_n_divconquer_preinv1 and _flint_mpn_divapprox_n_divconquer_preinv1. The latter is not correct up to one unit: each level of its recursion can make the quotient a few units too large (never too small; at most 8 units in tests with n \le 200), so it is used with a guard limb.

_flint_mpn_tdiv_qr_divconquer and _flint_mpn_tdiv_q_divconquer are Euclidean divisions for any divisor with \mathit{bn} \ge 2 (r may be NULL). When the quotient is about as long as the divisor or longer, a normalised copy is divided as above. For short quotients (m limbs), the top 2m limbs of a are divided by the top m limbs of b and the quotient (at most two too large) is corrected using its product with the ignored divisor limbs. Quotients of m \le \mathit{bn} + 2 limbs from FLINT_MPN_DIVAPPROX_SHORT_CUTOFF limbs use a short division in the style of Mulders [Mul2000; HZ2011]: the quotient with one guard limb is computed from the top m + 1 limbs of a and b only, recursively, the correction for the rest of the divisor being needed only above the current precision, i.e. as a high product.

The cutoffs are machine dependent and measured by src/mpn_extras/tune/tune-div.c for flint-mparam.h; the divide and conquer cutoffs must be at least 6.

References#

  • [BurZie1998] C. Burnikel and J. Ziegler. Fast recursive division. Max-Planck-Institut für Informatik, Research Report MPI-I-98-1-022, 1998.
  • [Mul2000] Thom Mulders : On Short Multiplications and Divisions, AAECC vol. 11 (2000) 69–88
  • [HZ2011] D. Harvey and P. Zimmermann, "Short division of long integers" (2011), Proceedings of the 20th Symposium on Computer Arithmetic (ARITH-20), July 25-27, 2011, pages 7-14. https://web.maths.unsw.edu.au/~davidharvey/research/shortdiv.pdf
Cite this page

The FLINT team, “_flint_mpn_divrem_basecase_preinv1, _flint_mpn_div_basecase_preinv1, _flint_mpn_divapprox_basecase_preinv1, _flint_mpn_divrem_preinv1, _flint_mpn_divapprox_preinv1, _flint_mpn_divrem_n_divconquer_preinv1, _flint_mpn_divapprox_n_divconquer_preinv1, _flint_mpn_tdiv_qr_divconquer, _flint_mpn_tdiv_q_divconquer (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/_flint_mpn_divrem_basecase_preinv1.html (generated 2026-10-20).