FLINT3.7.0-dev
/

_fmpz_poly_mul_toom_karatsuba, fmpz_poly_mul_toom_karatsuba, _fmpz_poly_mulmid_toom_karatsuba, fmpz_poly_mulmid_toom_karatsuba

Synopsis#include <flint/fmpz_poly.h>
void _fmpz_poly_mul_toom_karatsuba(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2)source
void fmpz_poly_mul_toom_karatsuba(fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2)source
void _fmpz_poly_mulmid_toom_karatsuba(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2, slong nlo, slong nhi)source
void fmpz_poly_mulmid_toom_karatsuba(fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong nlo, slong nhi)source

Karatsuba multiplication with the Toom–Cook functions _fmpz_poly_mul_toom_scalar_nmax and _fmpz_poly_mulmid_toom_scalar_nmax as base cases, for short polynomials with large coefficients. Full products use Karatsuba with the longer operand cut into pieces of the length of the shorter one; low products use Mulders' short product [Mul2000], high products a low product of the reversed operands, and other windows the Karatsuba middle product of Hanrot, Quercia and Zimmermann [HQZ2004], so that a middle-product-shaped window costs about half a full product.

The base case is used up to a product length that grows with the coefficient size: 5 below 2500 bits, 11 below 4000 bits, 15 below 6000 bits and FMPZ_POLY_TOOM_SCALAR_N_MAX above. The underscore versions take the lengths in either order, require positive lengths and 0 \le \mathit{nlo} < \mathit{nhi} \le \mathit{len1} + \mathit{len2} - 1, and do not allow res to overlap the inputs. The non-underscore versions clamp the window to the product and allow aliasing.

References#

  • [Mul2000] Thom Mulders : On Short Multiplications and Divisions, AAECC vol. 11 (2000) 69–88
  • [HQZ2004] G. Hanrot, M. Quercia and P. Zimmermann, "The middle product algorithm I. Speeding up the division and square root of power series", Applicable Algebra in Engineering, Communication and Computing 14:6 (2004), 415–438
Cite this page

The FLINT team, “_fmpz_poly_mul_toom_karatsuba, fmpz_poly_mul_toom_karatsuba, _fmpz_poly_mulmid_toom_karatsuba, fmpz_poly_mulmid_toom_karatsuba (fmpz_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_poly/_fmpz_poly_mul_toom_karatsuba.html (generated 2026-10-20).