The Truncated Fourier Transform for Mixed Radices
Robin Larrieu · 2017
The standard version of the Fast Fourier Transform (FFT) is applied to problems of size n=2k. For this reason, FFT-based evaluation interpolation schemes often reduce a problem of size l to a problem of size n , where n is the smallest power of two with l ≤ n. However, this method presents "jumps" in the complexity at powers of two; and on the other hand, n-l values are computed that are actually unnecessary for the interpolation. To mitigate this problem, a truncated variant of the FFT was designed to avoid the computation of these unnecessary values. In the initial formulation [10], it is assumed that n is a power of two, but some use cases (for example in finite fields) may require more general values of n. This paper presents a generalization of the Truncated Fourier Transform (TFT) for arbitrary orders. This allows to benefit from the advantages of the TFT in the general case.