FLINT3.7.0-dev
/

_gr_poly_divrem, gr_poly_divrem, _gr_poly_divrem_basecase_preinv1, _gr_poly_divrem_basecase_noinv, _gr_poly_divrem_basecase, gr_poly_divrem_basecase, _gr_poly_divrem_divconquer_preinv1, _gr_poly_divrem_divconquer_noinv, _gr_poly_divrem_divconquer, gr_poly_divrem_divconquer, _gr_poly_divrem_newton, gr_poly_divrem_newton

Synopsis#include <flint/gr_poly.h>
int _gr_poly_divrem(gr_ptr Q, gr_ptr R, gr_srcptr A, slong lenA, gr_srcptr B, slong lenB, gr_ctx_t ctx)source
int gr_poly_divrem(gr_poly_t Q, gr_poly_t R, const gr_poly_t A, const gr_poly_t B, gr_ctx_t ctx)source
int _gr_poly_divrem_basecase_preinv1(gr_ptr Q, gr_ptr R, gr_srcptr A, slong lenA, gr_srcptr B, slong lenB, gr_srcptr invB, gr_ctx_t ctx)source
int _gr_poly_divrem_basecase_noinv(gr_ptr Q, gr_ptr R, gr_srcptr A, slong lenA, gr_srcptr B, slong lenB, gr_ctx_t ctx)source
int _gr_poly_divrem_basecase(gr_ptr Q, gr_ptr R, gr_srcptr A, slong lenA, gr_srcptr B, slong lenB, gr_ctx_t ctx)source
int gr_poly_divrem_basecase(gr_poly_t Q, gr_poly_t R, const gr_poly_t A, const gr_poly_t B, gr_ctx_t ctx)source
int _gr_poly_divrem_divconquer_preinv1(gr_ptr Q, gr_ptr R, gr_srcptr A, slong lenA, gr_srcptr B, slong lenB, gr_srcptr invB, slong cutoff, gr_ctx_t ctx)source
int _gr_poly_divrem_divconquer_noinv(gr_ptr Q, gr_ptr R, gr_srcptr A, slong lenA, gr_srcptr B, slong lenB, slong cutoff, gr_ctx_t ctx)source
int _gr_poly_divrem_divconquer(gr_ptr Q, gr_ptr R, gr_srcptr A, slong lenA, gr_srcptr B, slong lenB, slong cutoff, gr_ctx_t ctx)source
int gr_poly_divrem_divconquer(gr_poly_t Q, gr_poly_t R, const gr_poly_t A, const gr_poly_t B, slong cutoff, gr_ctx_t ctx)source
int _gr_poly_divrem_newton(gr_ptr Q, gr_ptr R, gr_srcptr A, slong lenA, gr_srcptr B, slong lenB, gr_ctx_t ctx)source
int gr_poly_divrem_newton(gr_poly_t Q, gr_poly_t R, const gr_poly_t A, const gr_poly_t B, gr_ctx_t ctx)source

Set Q and R to the quotient and remainder of A by B. The non-underscore functions return GR_DOMAIN if B is zero and GR_UNABLE if the leading coefficient of B is not provably nonzero. gr_poly_divrem calls the ring method GR_METHOD_POLY_DIVREM.

The basecase versions perform long division. The divconquer versions divide blocks of 2 \mathit{lenB} - 1 coefficients of the dividend by B recursively, with two divisions by the upper half of B and products by its lower half, and use long division for divisors shorter than cutoff. The newton versions use Newton division. The preinv1 versions take a precomputed inverse invB of the leading coefficient, the noinv versions divide by the leading coefficient with gr_div at each step, and the plain versions try to invert the leading coefficient and fall back to the noinv algorithm.

The default method _gr_poly_divrem_generic uses long division when \mathit{lenB} = 1 or \mathit{lenA} - \mathit{lenB} = 1, and over finite rings also when the divisor or the quotient has at most 10 coefficients; otherwise it uses Newton division, falling back to long or divide-and-conquer division without inversion when the leading coefficient is not invertible. Rings with fast arithmetic override the method: nmod, fmpz_mod, mpn_mod, fq, fq_nmod, fq_zech, arb and acb call the division of their own polynomial modules.

The underscore functions assume:

  • \mathit{lenA} \ge \mathit{lenB} \ge 1 and a nonzero leading coefficient of B;
  • Q has room for \mathit{lenA} - \mathit{lenB} + 1 and R for \mathit{lenB} - 1 coefficients;
  • Q is not aliased with A or B, and R is not aliased with B;
  • R may be aliased with A, in which case all \mathit{lenA} coefficients are used as scratch space and only the low \mathit{lenB} - 1 are meaningful on output.

Guides#

Cite this page

The FLINT team, “_gr_poly_divrem, gr_poly_divrem, _gr_poly_divrem_basecase_preinv1, _gr_poly_divrem_basecase_noinv, _gr_poly_divrem_basecase, gr_poly_divrem_basecase, _gr_poly_divrem_divconquer_preinv1, _gr_poly_divrem_divconquer_noinv, _gr_poly_divrem_divconquer, gr_poly_divrem_divconquer, _gr_poly_divrem_newton, gr_poly_divrem_newton (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_divrem.html (generated 2026-10-20).