Editing Rader's FFT algorithm (section)

{{Short description|Discrete Fourier transform for prime sizes}}
'''Rader's algorithm''' (1968),<ref>C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," ''Proc. IEEE'' 56, 1107–1108 (1968).</ref> named for Charles M. Rader of [[MIT Lincoln Laboratory]], is a [[fast Fourier transform]] (FFT) algorithm that computes the [[discrete Fourier transform]] (DFT) of [[prime number|prime]] sizes by re-expressing the DFT as a cyclic [[convolution]] (the other algorithm for FFTs of prime sizes, [[Bluestein's FFT algorithm|Bluestein's algorithm]], also works by rewriting the DFT as a convolution).

Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a [[number-theoretic transform]] or the [[discrete Hartley transform]].

The algorithm can be modified to gain a factor of two savings for the case of DFTs of real data, using a slightly modified re-indexing/permutation to obtain two half-size cyclic convolutions of real data;<ref>S. Chu and C. Burrus, "A prime factor FTT <nowiki>[</nowiki>''sic''<nowiki>]</nowiki> algorithm using distributed arithmetic," '' IEEE Transactions on Acoustics, Speech, and Signal Processing'' '''30''' (2), 217&ndash;227 (1982).</ref> an alternative adaptation for DFTs of real data uses the [[discrete Hartley transform]].<ref name=Frigo05>Matteo Frigo and [[Steven G. Johnson]], "[http://fftw.org/fftw-paper-ieee.pdf The Design and Implementation of FFTW3]," ''Proceedings of the IEEE'' '''93''' (2), 216–231 (2005).</ref>

Winograd extended Rader's algorithm to include prime-power DFT sizes <math>p^m</math>,<ref>S. Winograd, "On Computing the Discrete Fourier Transform", ''Proc. National Academy of Sciences USA'', '''73'''(4), 1005&ndash;1006 (1976).</ref><ref>S. Winograd, "On Computing the Discrete Fourier Transform", ''Mathematics of Computation'', '''32'''(141), 175&ndash;199 (1978).</ref> and today Rader's algorithm is sometimes described as a special case of [[Fast Fourier transform#Other FFT algorithms|Winograd's FFT algorithm]], also called the ''multiplicative Fourier transform algorithm'' (Tolimieri et al., 1997),<ref>R. Tolimieri, M. An, and C.Lu, ''Algorithms for Discrete Fourier Transform and Convolution'', Springer-Verlag, 2nd ed., 1997.</ref> which applies to an even larger class of sizes.  However, for [[composite number|composite]] sizes such as prime powers, the [[Cooley–Tukey FFT algorithm]] is much simpler and more practical to implement, so Rader's algorithm is typically only used for large-prime [[Base case (recursion)|base case]]s of Cooley–Tukey's [[Recursion (computer science)|recursive]] decomposition of the DFT.<ref name=Frigo05/>