radix_mulmid

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}$.

@misc{flint-doc-radix-radix-mulmid,
  author       = {{The FLINT team}},
  title        = {{radix\_mulmid (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.html},
  note         = {Generated 2026-11-02}
}