FLINT3.7.0-dev
/

_flint_mpn_poly_mulmid_karatsuba

Synopsis#include <flint/mpn_extras.h>
void _flint_mpn_poly_mulmid_karatsuba(nn_ptr res, nn_srcptr f, slong flen, slong nlimbs1, slong norm1, nn_srcptr g, slong glen, slong nlimbs2, slong norm2, slong nlo, slong nhi, slong slimbs, slong cutoff, int sgn)source

Sets (\mathit{res}, (\mathit{nhi} - \mathit{nlo})\, \mathit{slimbs}) to the coefficients [\mathit{nlo}, \mathit{nhi}) of the product of (f, \mathit{flen}\, \mathit{nlimbs1}) and (g, \mathit{glen}\, \mathit{nlimbs2}), with the conventions of _flint_mpn_poly_mul_karatsuba except that the operands may have different numbers of limbs, with headrooms norm1 and norm2. slimbs must be at least \mathit{nlimbs1} + \mathit{nlimbs2} - 1, and at least \mathit{nlimbs1} + \mathit{nlimbs2} + 1 if either operand may get extended in the recursion (when its headroom is smaller than the recursion depth plus one). Squaring is detected when f == g, flen == glen and nlimbs1 == nlimbs2.

The coefficients of the inputs that cannot contribute to the window are discarded first, and the algorithm is chosen according to the shape:

  • a full product if the window is the whole product;
  • Mulders' short product for a low product (\mathit{nlo} = 0): a full product of the low parts, split at about 0.7 n, plus two recursive short products (one when squaring); a high product is computed as the reversal of a low product of the reversed inputs;
  • the Karatsuba middle product of Hanrot, Quercia and Zimmermann [HQZ2004] for windows in which all coefficients of the shorter operand contribute (for example the n coefficients [n-1, 2n-1) of a (2n-1) \times n product), computed in blocks of the length of the shorter operand, with the edges computed classically;
  • otherwise a full product of the trimmed inputs clipped to the window, or classical multiplication for small windows.

The short products are used from about 4 times cutoff. The Karatsuba middle product uses two's complement arithmetic internally (it involves differences of parts of the longer operand), so slimbs must include a sign bit even for unsigned inputs; it consumes one bit of headroom on every branch of the recursion, so when the headroom is smaller than the recursion depth the coefficients are extended early and a larger cutoff is used.

References#

  • [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, “_flint_mpn_poly_mulmid_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_mulmid_karatsuba.html (generated 2026-10-20).