_gr_poly_mullow_toom_serial, gr_poly_mullow_toom_serial
#include <flint/gr_poly.h>int _gr_poly_mullow_toom_serial(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, slong trunc, slong num_points, slong splitting_degree, gr_ctx_t ctx)sourceint gr_poly_mullow_toom_serial(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, slong n, slong num_points, slong splitting_degree, gr_ctx_t ctx)sourceToom-Cook multiplication of arbitrary order with low memory use: the inputs are split into blocks of m coefficients, viewed as polynomials in t = x^m, and the product is computed by evaluation at r points and interpolation. Exactly one of num_points (r) and splitting_degree (m) must be nonzero; the other is chosen automatically.
For balanced operands, r = 2k - 1 points correspond to splitting both inputs into k blocks; r = 3 (or m = \lceil \max(\mathit{len1}, \mathit{len2}) / 2 \rceil) gives Karatsuba multiplication with evaluation at 0, 1, \infty. Even r is mainly useful for unbalanced products. The points are 0, 1, -1, 2, -2, \ldots, \infty, and evaluation and interpolation multiply by the Vandermonde matrix and its inverse. In characteristic zero the inverse is computed with a common denominator that is removed at the end by an exact division; in small positive characteristic, where the Vandermonde matrix is singular, GR_UNABLE is returned.
The evaluations are done one point at a time and the output is accumulated incrementally, using 4m temporary elements for polynomials and 2r^2 elements or integers for the matrices. This suits huge products under memory constraints, unlike a usual Toom-Cook implementation that keeps many temporary buffers to save scalar operations. The underscore version requires positive lengths and does not allow aliasing.
The FLINT team, “_gr_poly_mullow_toom_serial, gr_poly_mullow_toom_serial (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_mullow_toom_serial.html (generated 2026-10-20).
@misc{flint-doc-gr-poly-gr-poly-mullow-toom-serial,
author = {{The FLINT team}},
title = {{\_gr\_poly\_mullow\_toom\_serial, gr\_poly\_mullow\_toom\_serial (gr\_poly.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/gr_poly/_gr_poly_mullow_toom_serial.html},
note = {Generated 2026-10-20}
}