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 \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 \mathit{lenB} - 1 coefficients of BQ correctly (the array must still have room for 2 \mathit{lenB} - 1); div uses a temporary (temp, 2 lenB - 1) and does not compute BQ [Mul2000]. The low \mathit{lenB} - 1 coefficients of A are not read. They require \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-10-20).