Content deleted Content added
m use section header for references |
m section headers |
||
Line 1:
'''Rader's algorithm''' (1968) 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.)
==Algorithm==
Recall that the DFT is defined by the formula
Line 21 ⟶ 23:
:<math>a_q = x_{g^q}</math>
:<math>b_q = e^{-\frac{2\pi i}{n} g^{-q} }.</math>
===Evaluating the Convolution===
Since ''n''–1 is composite, this convolution can be performed directly via the [[convolution theorem]] and more conventional FFT algorithms. However, that may not be efficient if ''n''–1 itself has large prime factors, requiring recursive use of Rader's algorithm. Instead, one can compute a length-(''n''–1) cyclic convolution exactly by zero-padding it to a length of at least 2(''n''–1)–1, say to a [[power of two]], which can then be evaluated in O(''n'' log ''n'') time without the recursive application of Rader's algorithm.
| |||