Content deleted Content added
m section headers |
moved comment on generality to top |
||
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.)
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]].▼
==Algorithm==
Line 32 ⟶ 34:
If Rader's algorithm is performed by using FFTs of size ''n''–1 to compute the convolution, rather than by zero padding as mentioned above, the efficiency depends strongly upon ''n'' and the number of times that Rader's algorithm must be applied recursively. The worst case would be if ''n''–1 were 2''n''<sub>2</sub> where ''n''<sub>2</sub> is prime, with ''n''<sub>2</sub>–1 = 2''n''<sub>3</sub> where ''n''<sub>3</sub> is prime, and so on. In such cases, supposing that the chain of primes extended all the way down to some bounded value, the recursive application of Rader's algorithm would actually require O(''n''<sup>2</sup>) time. Such ''n''<sub>j</sub> are called [[Sophie Germain prime|Sophie Germain primes]], and such a sequence of them is called a [[Cunningham chain]]. The lengths of Cunningham chains, however, are observed to grow more slowly than log<sub>2</sub>(''n''), so Rader's algorithm applied in this way is probably not [[Big O notation|Ω]](''n''<sup>2</sup>), though it is possibly worse than O(''n'' log ''n'') for the worst cases. Fortunately, a guarantee of O(''n'' log ''n'') complexity can be achieved by zero padding.
▲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]].
==References==
| |||