0.1 Algorithms  (Page 3/5)

Symmetries in the complex exponential function are again used to expose common computation among each part of the equation; hence

which, when recursively applied to the sub-transforms, results in the following recurrence relation for real arithmetic operations:

The exact solution $T\left(n\right)=4n{log}_{2}n-6n+8$ for $n\ge 2$ was the best arithmetic complexity of all known FFT algorithms for over 30 years, until VanBuskirk was able to break the record in 2004  [link] , as described in "Tangent" .

Van Buskirk's arithmetic complexity breakthrough was based on a variant of the split-radix algorithm known as the “conjugate-pair” algorithm  [link] or the “ $-1$ exponent” split-radix algorithm  [link] , [link] . In 1989 the conjugate-pair algorithm was published with the claim that it had broken the record set by Yavne in 1968for the lowest number of arithmetic operations for computing the DFT  [link] . Unfortunately the reduction in the number of arithmetic operations was due to an error in the author's analysis, and thealgorithm was subsequently proven to have an arithmetic count equal to the original split-radixalgorithm  [link] , [link] , [link] . Despite initial claims about the arithmetic savings beingdiscredited, the conjugate-pair algorithm has been used to reduce twiddle factor loads in software implementations of the FFT and fast Hartleytransform (FHT)  [link] , and the algorithm was also recently used as the basis for analgorithm that does reduce the arithmetic operation count, as described in "Tangent" .

The difference between the conjugate-pair algorithm and the split-radix algorithm is in the decomposition of odd elements. In the standardsplit-radix algorithm, the odd elements are decomposed into two parts: $x_{4n_4+1}$ and $x_{4n_4+3}$ (see [link] ), while in the conjugate-pair algorithm, the last sub-sequence is cyclically shiftedby $-4$ , where negative indices wrap around (i.e., $x_{-1}=x_{N-1}$ ). The result of this cyclic shift is that twiddle factors are nowconjugate pairs. Formally, the conjugate-pair algorithm is defined as:

As with the ordinary split-radix algorithm, a DIT decomposition of the conjugate-pair algorithm can be expressed as a system of equations:

where $k=0,\cdots ,N/4-1$ . As can be seen, the trigonometric coefficients are conjugates – a feature that can be exploited to reduce twiddle factorloads.

Tangent

In 2004, some thirty years after Yavne set the record for the lowest arithmetic operation count, Van Buskirk posted software to Usenet that hadasymptotically reduced the arithmetic operation count by about 6%. Three papers were subsequently published  [link] , [link] , [link] with differing explanations on how to achieve the lowest arithmetic operation count initially demonstrated by Van Buskirk.

Although all three papers describe algorithms that achieve the lowest arithmetic operation count in the same way, and thus can be considered to bedifferent views of the same algorithm, all three papers refer to the algorithms by different names. Lundy and Van Buskirk  [link] refer to their algorithm as “scaled odd tail FFT”, Bernstein  [link] describes an algorithm named “tangent FFT”, while Johnson and Frigo  [link] refer to the algorithm by various names. Many works have cited Johnson and Frigo for the algorithm  [link] . Of these names, “tangent FFT” is used in this work because it is the mostdescriptive; scaling the twiddle factors into tangent form was the linchpin of Van Buskirk's breakthrough in arithmetic complexity.