FLINT3.7.0-dev
/

radix_mulmid

Synopsis#include <flint/radix.h>
void radix_mulmid(nn_ptr res, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong lo, slong hi, const radix_t radix)source

Windowed product: for \mathit{an}, \mathit{bn} \ge 1 and 0 \le \mathit{lo} < \mathit{hi} \le \mathit{an} + \mathit{bn}, sets (\mathit{res}, \mathit{hi} - \mathit{lo}) to the limbs [\mathit{lo}, \mathit{hi}) of the product, computed without the carries from the limbs below \mathit{lo}. res must not overlap the inputs.

Viewing a and b as polynomials A, Y \in \mathbb{Z}[T] evaluated at T = B, the function computes the slice Z_{lo:hi} = \sum_{k=lo}^{hi-1} ([T^k] AY)\, T^{k-lo} of the polynomial product and writes Z_{lo:hi}(B) \bmod B^{hi-lo}: carries from lower terms are omitted and carries beyond the top are discarded. In particular:

  • for \mathit{lo} = 0 this is the low product ab \bmod B^{hi};
  • for \mathit{hi} = \mathit{an} + \mathit{bn} this is an approximate high product r with ab \ge r B^{lo} \ge ab - \min(\mathit{an}, \mathit{bn}, \mathit{lo}) B^{lo+1};
  • for \mathit{lo} = 0 and \mathit{hi} = \mathit{an} + \mathit{bn} it is the full product.

The classical algorithm is used if either operand or the window is shorter than 80 limbs, and otherwise if the number of limb products the window needs (counted by _radix_mulmid_pairs_below) is less than RADIX_MULMID_FFT_CUTOFF_RATIO \cdot L; the FFT (or Kronecker substitution without fft_small) is used otherwise. The cost of the FFT depends essentially on the length L of the convolution it computes, while the classical algorithm benefits from short windows: a high product needs about half as many limb products as the full product. With fft_small, L is _radix_mulmid_fft_length(\mathit{an}, \mathit{bn}, \mathit{lo}, \mathit{hi}), which is smaller than \mathit{an} + \mathit{bn} for windows that do not need all limbs or that are computed as transposed products; without it, L = \mathit{an} + \mathit{bn}.

Cite this page

The FLINT team, “radix_mulmid (radix.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/radix/radix_mulmid.html (generated 2026-10-20).