FLINT3.7.0-dev
/

_fmpz_poly_divrem_divconquer_recursive, _fmpz_poly_divremlow_divconquer_recursive, _fmpz_poly_div_divconquer_recursive

Synopsis#include <flint/fmpz_poly.h>
int _fmpz_poly_divrem_divconquer_recursive(fmpz * Q, fmpz * BQ, fmpz * W, const fmpz * A, const fmpz * B, slong lenB, int exact)source
int _fmpz_poly_divremlow_divconquer_recursive(fmpz * Q, fmpz * QB, const fmpz * A, const fmpz * B, slong lenB, int exact)source
int _fmpz_poly_div_divconquer_recursive(fmpz * Q, fmpz * temp, const fmpz * A, const fmpz * B, slong lenB, int exact)source

The recursive steps of divide-and-conquer division for the balanced case len⁡(A)=2lenB−1\operatorname{len}(A) = 2 \mathit{lenB} - 1: they compute the quotient (Q, lenB), and divrem also the product (BQ, 2 lenB - 1) using the temporary (W, 2 lenB - 1); divremlow computes only the low lenB−1\mathit{lenB} - 1 coefficients of BQBQ correctly (the array must still have room for 2lenB−12 \mathit{lenB} - 1); div uses a temporary (temp, 2 lenB - 1) and does not compute BQBQ [Mul2000]. The low lenB−1\mathit{lenB} - 1 coefficients of AA are not read. They require lenB>0\mathit{lenB} > 0 and do not allow aliasing; exact is as for _fmpz_poly_divrem.

References#

  • [Mul2000] Thom Mulders : On Short Multiplications and Divisions, AAECC vol. 11 (2000) 69–88
Cite this page

The FLINT team, “_fmpz_poly_divrem_divconquer_recursive, _fmpz_poly_divremlow_divconquer_recursive, _fmpz_poly_div_divconquer_recursive (fmpz_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_poly/_fmpz_poly_divrem_divconquer_recursive.html (generated 2026-11-02).