radix_mulmid_classical, radix_mulmid_fft_small, radix_mulmid_KS, radix_mulmid_naive
#include <flint/radix.h>void radix_mulmid_classical(nn_ptr res, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong lo, slong hi, const radix_t radix)sourcevoid radix_mulmid_fft_small(nn_ptr res, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong lo, slong hi, const radix_t radix)sourcevoid radix_mulmid_KS(nn_ptr res, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong lo, slong hi, const radix_t radix)sourcevoid radix_mulmid_naive(nn_ptr res, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong lo, slong hi, const radix_t radix)sourceThe algorithms behind radix_mulmid, with its interface: the schoolbook algorithm with delayed reduction of the column sums, efficient when an operand or the window is short; multiplication of the limb sequences as polynomials with the small-prime FFT of fft_small (only available if FLINT is built with it), reconstructing only the coefficients that reach the window and propagating carries in radix B; Kronecker substitution into one product in the binary radix \beta (each limb padded to two words); and an unoptimised reference implementation through fmpz_poly.
radix_mulmid_fft_small first drops the limbs of each operand above \mathit{hi} and the low limbs that meet the other operand only below \mathit{lo} (they contribute only carries from below the window, which are omitted anyway). If the remaining window is shorter than the longer operand, it is computed as a transposed product of the reversed shorter operand and the longer one, at the cost of a product of the shorter operand and the window, provided this transform is strictly shorter than that of the window of the full product (not for squarings). The middle products of the Newton iterations of the division and inversion code (an operand of about 2n limbs, a window of about n limbs) are the typical case. The carries are propagated from \mathit{lo} in both cases, so the result is the same. See Transposed FFT.
Guides#
- Where FLINT uses fft_small (
fft_small)
The FLINT team, “radix_mulmid_classical, radix_mulmid_fft_small, radix_mulmid_KS, radix_mulmid_naive (radix.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/radix/radix_mulmid_classical.html (generated 2026-10-20).
@misc{flint-doc-radix-radix-mulmid-classical,
author = {{The FLINT team}},
title = {{radix\_mulmid\_classical, radix\_mulmid\_fft\_small, radix\_mulmid\_KS, radix\_mulmid\_naive (radix.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/radix/radix_mulmid_classical.html},
note = {Generated 2026-10-20}
}