FLINT3.7.0-dev
/

flint_mpn_mulmid_classical, flint_mpn_mulmid_via_mul, flint_mpn_mulmid_via_mullow_n, flint_mpn_mulmid_via_mulhigh_n, flint_mpn_mulmid_via_n_padded, flint_mpn_mulmid_fft_small

Synopsis#include <flint/mpn_extras.h>
void flint_mpn_mulmid_classical(mp_ptr z, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_size_t zlo, mp_size_t zhi)source
void flint_mpn_mulmid_via_mul(mp_ptr z, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_size_t zlo, mp_size_t zhi)source
void flint_mpn_mulmid_via_mullow_n(mp_ptr z, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_size_t zlo, mp_size_t zhi)source
void flint_mpn_mulmid_via_mulhigh_n(mp_ptr z, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_size_t zlo, mp_size_t zhi)source
void flint_mpn_mulmid_via_n_padded(mp_ptr z, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_size_t zlo, mp_size_t zhi)source
void flint_mpn_mulmid_fft_small(mp_ptr z, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn, mp_size_t zlo, mp_size_t zhi)source

The methods behind flint_mpn_mulmid, with its interface and contract: row-wise schoolbook multiplication in time O((\mathit{zhi} - \mathit{zlo}) \min(\mathit{an}, \mathit{bn})); a full product (flint_mpn_mul); a balanced low product (flint_mpn_mullow_n); a balanced high product (flint_mpn_mulhigh_n); GMP's balanced middle product (flint_mpn_mulmid_n); and the small-prime FFT, which only reconstructs the coefficients that reach the window. Each accepts any shape (padding internally) but is economical only in its own regime. flint_mpn_mulmid_via_n_padded exists only if FLINT_HAVE_NATIVE_mpn_mulmid_n is set, and flint_mpn_mulmid_fft_small only with fft_small.

flint_mpn_mulmid computes full products with flint_mpn_mul. Otherwise it truncates both operands to \mathit{zhi} limbs and uses: for \min(\mathit{an}, \mathit{bn}, \mathit{zhi} - \mathit{zlo}) < 48, the low product if \mathit{zlo} = 0, \mathit{zhi} \ge 8 and both operands have at least 7 \mathit{zhi}/8 limbs, and the schoolbook method otherwise; else fft_small if both operands reach the fft_small multiplication threshold; else the low product when the window starts in the bottom eighth of the product, the high product when it ends in the top eighth (both if the operands are about as long as the window); else GMP's middle product for the shape 2m \times m with window [m, 2m) (within 12.5%); and a full product otherwise.

flint_mpn_mulmid_fft_small (_mpn_ctx_mpn_mul_range) computes a window shorter than the longer operand as a transposed product, whose cost is that of a product of the shorter operand and the window, when its transform is strictly shorter than that of the window of the full product (not for squarings); the result is the same, bit for bit. For the window [n, 2n) of a 2n \times n product this is a transform of about 2n instead of 3n limbs' worth of coefficients. See Middle products by transposed small-prime FFTs.

Cite this page

The FLINT team, “flint_mpn_mulmid_classical, flint_mpn_mulmid_via_mul, flint_mpn_mulmid_via_mullow_n, flint_mpn_mulmid_via_mulhigh_n, flint_mpn_mulmid_via_n_padded, flint_mpn_mulmid_fft_small (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/flint_mpn_mulmid_classical.html (generated 2026-10-20).