_flint_mpn_poly_mul_classical, _flint_mpn_poly_mul_karatsuba
#include <flint/mpn_extras.h>void _flint_mpn_poly_mul_classical(nn_ptr res, nn_srcptr f, slong flen, nn_srcptr g, slong glen, slong nlimbs, slong slimbs, int sgn)sourcevoid _flint_mpn_poly_mul_karatsuba(nn_ptr res, nn_srcptr f, slong flen, nn_srcptr g, slong glen, slong nlimbs, slong slimbs, slong cutoff, int norm, int sgn)sourceSet (\mathit{res}, (\mathit{flen} + \mathit{glen} - 1)\, \mathit{slimbs}) to the full product of (f, \mathit{flen}\, \mathit{nlimbs}) and (g, \mathit{glen}\, \mathit{nlimbs}), viewed as polynomials with nlimbs-limb coefficients (unsigned for sgn = 0, two's complement for sgn = 1), by the classical algorithm respectively Karatsuba's. The output coefficients are computed modulo B^{\mathit{slimbs}}, where slimbs is one of 2\,\mathit{nlimbs} - 1, 2\,\mathit{nlimbs}, 2\,\mathit{nlimbs} + 1. Squaring is detected when f == g and flen == glen.
The results are exact provided that all coefficients of the product fit in slimbs limbs. For Karatsuba this must also hold for all intermediate coefficients (the products of sums of the parts, which grow by up to two bits per level of recursion), and norm must bound the number of leading unused bits (excluding the sign bit when sgn is 1) in the top limb of the input coefficients. When norm reaches zero in the recursion, the coefficients of the sums are extended to \mathit{nlimbs} + 1 limbs, so slimbs must then be at least 2\,\mathit{nlimbs} + 1. The recursion switches to the classical algorithm when the shorter length is below cutoff; the classical instances are resolved once per level, so that the base cases are called directly. Unbalanced lengths are handled by splitting the longer operand into pieces of the length of the shorter one at every level.
The FLINT team, “_flint_mpn_poly_mul_classical, _flint_mpn_poly_mul_karatsuba (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/_flint_mpn_poly_mul_classical.html (generated 2026-10-20).
@misc{flint-doc-mpn-extras-flint-mpn-poly-mul-classical,
author = {{The FLINT team}},
title = {{\_flint\_mpn\_poly\_mul\_classical, \_flint\_mpn\_poly\_mul\_karatsuba (mpn\_extras.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/mpn_extras/_flint_mpn_poly_mul_classical.html},
note = {Generated 2026-10-20}
}