Rader's FFT algorithm

Rader's algorithm (1968), named for Charles M. Rader of <a href="/facts/MIT_Lincoln_Laboratory/ea2JwxzT">MIT Lincoln Laboratory</a>, is a <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> (FFT) algorithm that computes the <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a> (DFT) of <a href="/facts/Prime_number/L20FLkgn">prime</a> sizes by re-expressing the DFT as a cyclic <a href="/facts/Convolution/PVPrdz9J">convolution</a> (the other algorithm for FFTs of prime sizes, <a href="/facts/Bluestein%27s_FFT_algorithm/1HDuWH4X">Bluestein's algorithm</a>, 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 <a href="/facts/Number-theoretic_transform/ntR67BjE">number-theoretic transform</a> or the <a href="/facts/Discrete_Hartley_transform/lctBpTSj">discrete Hartley transform</a>.
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; an alternative adaptation for DFTs of real data uses the <a href="/facts/Discrete_Hartley_transform/lctBpTSj">discrete Hartley transform</a>.
Winograd extended Rader's algorithm to include prime-power DFT sizes 
 
 
 
 
 p
 
 m
 
 
 
 
 {\displaystyle p^{m}}
 
, and today Rader's algorithm is sometimes described as a special case of <a href="/facts/Fast_Fourier_transform/caT7UUCh">Winograd's FFT algorithm</a>, also called the multiplicative Fourier transform algorithm (Tolimieri et al., 1997), which applies to an even larger class of sizes. However, for <a href="/facts/Composite_number/SPtW9ftC">composite</a> sizes such as prime powers, the <a href="/facts/Cooley%E2%80%93Tukey_FFT_algorithm/03VB7JrC">Cooley–Tukey FFT algorithm</a> is much simpler and more practical to implement, so Rader's algorithm is typically only used for large-prime <a href="/facts/Base_case_(recursion)/CxSKxJoW">base cases</a> of Cooley–Tukey's <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursive</a> decomposition of the DFT.

Rader's FFT algorithm open-in-new

Rader's FFT algorithm