Rader's FFT algorithm: Difference between revisions

Revision as of 21:27, 6 June 2003

Revision as of 21:28, 6 June 2003

Line 24:

This algorithm, then, requires O(''n'') additions plus O(''n'' log ''n'') time for the convolution. In practice, the O(''n'') additions can often be performed in O(1) additions by absorbing the additions into the convolution: if the convolution is performed by a pair of FFTs, then the sum of ''x''_''k'' is given by the DC (0th) output of the FFT of ''a''_''q'', and ''x''₀ can be added to all the outputs by adding it to the DC term of the convolution prior to to the inverse FFT. Still, this algorithm requires intrinsically more operations than FFTs of nearby composite sizes, and typically takes 3-10 times as long in practice.

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''₂ where ''n''₂ is prime, with ''n''₂-1 = 2''n''₃ where ''n''₃ is prime, and so on. In thissuch a case, the application of Rader's algorithm would actually require O(''n''²) time. Such ''n''_j are called [[Sophie Germain prime|Sophie Germain primes]], and the sequence of them is called a [[Cunningham chain]]. The length of Cunningham chains, however, grows more slowly than log(''n''), so Rader's algorithm applied in this way is not O(''n''²), but it is probably worse than O(''n'' log ''n''). Fortunately, a guarantee of O(''n'' log ''n'') complexity can be achieved by using zero padding (at least for cases when ''n''-1 has large prime factors).

----