_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
#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)sourceint _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)sourceint _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)sourceint _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)sourceDivision with remainder in the case \mathit{lenA} = \mathit{lenB} + 1, where the quotient q_1 x + q_0 has two coefficients, given the inverse invL of the leading coefficient of B. Require \mathit{lenB} \ge 2.
Each coefficient of the remainder is a_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 q_0 and q_1 for the matrix method of preconditioned multiplication; the karatsuba_precond version shares one product between two consecutive coefficients through (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 \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.
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-10-20).
@misc{flint-doc-mpn-mod-mpn-mod-poly-divrem-q1-preinv1,
author = {{The FLINT team}},
title = {{\_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)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/mpn_mod/_mpn_mod_poly_divrem_q1_preinv1.html},
note = {Generated 2026-10-20}
}