Content deleted Content added
weakened speculation |
noted generalization to other transforms |
||
Line 27:
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 with a similar property, such as a [[number-theoretic transform]] or the [[discrete Hartley transform]].
----
| |||