FLINT3.7.0-dev
/

_mpn_mod_poly_divrem_q1_preinv1, _mpn_mod_poly_divrem_q1_preinv1_fmma, _mpn_mod_poly_divrem_q1_preinv1_fmma_precond, _mpn_mod_poly_divrem_q1_preinv1_karatsuba_precond

Synopsis#include <flint/mpn_mod.h>
int _mpn_mod_poly_divrem_q1_preinv1(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nn_srcptr invL, gr_ctx_t ctx)source
int _mpn_mod_poly_divrem_q1_preinv1_fmma(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nn_srcptr invL, gr_ctx_t ctx)source
int _mpn_mod_poly_divrem_q1_preinv1_fmma_precond(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nn_srcptr invL, gr_ctx_t ctx)source
int _mpn_mod_poly_divrem_q1_preinv1_karatsuba_precond(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nn_srcptr invL, gr_ctx_t ctx)source

Division with remainder in the case lenA=lenB+1\mathit{lenA} = \mathit{lenB} + 1, where the quotient q1x+q0q_1 x + q_0 has two coefficients, given the inverse invL of the leading coefficient of BB. Require lenB≥2\mathit{lenB} \ge 2.

Each coefficient of the remainder is ai−q1bi−1−q0bia_i - q_1 b_{i-1} - q_0 b_i. The fmma version computes it with one flint_mpn_fmmamod_preinvn; the fmma_precond version precomputes q0q_0 and q1q_1 for the matrix method of preconditioned multiplication; the karatsuba_precond version shares one product between two consecutive coefficients through (q0+q1)(bi−1+bi)(q_0 + q_1)(b_{i-1} + b_i), saving a quarter of the multiplications (Euclid's algorithm). _mpn_mod_poly_divrem_q1_preinv1 chooses the fmma version for lenB<10\mathit{lenB} < 10 or moduli of at most 576 bits, the Karatsuba version for long divisors or large moduli, and the fmma_precond version in between.

Cite this page

The FLINT team, “_mpn_mod_poly_divrem_q1_preinv1, _mpn_mod_poly_divrem_q1_preinv1_fmma, _mpn_mod_poly_divrem_q1_preinv1_fmma_precond, _mpn_mod_poly_divrem_q1_preinv1_karatsuba_precond (mpn_mod.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_mod/_mpn_mod_poly_divrem_q1_preinv1.html (generated 2026-11-02).