0.2 Implementation details  (Page 2/9)

However it is worth noting that when considered from a historical perspective, the performance does seem impressive – as shown in [link] . The runtimes in [link] are approximate; the Cooley-Tukey figure is roughly extrapolated from the floating point operations per second (FLOPS) count of a size 2048complex transform given in their 1965 paper [link] ; and the speed of the reference implementation is derived from the runtime of a size 64complex FFT (again, based on the FLOPS count). Furthermore, the precision differs between the results; Danielson and Lanczos computed theDFT to 3–5 significant figures (possibly with the aid of slide rules or adding machines), while the other results were computed with the host machines' implementation ofsingle precision floating point arithmetic.

The runtime performance of the FFT has improved by about seven orders of magnitude in 70 years, and this can largely be attributed to the computingmachines of the day being generally faster. The following sections and chapters will show that the performance can be further improved by over two orders ofmagnitude if the algorithm is enhanced with optimizations that are amenable to the underlying machine.

Split-radix

As was the case with the radix-2 FFT in the previous section, the split-radix FFT neatly maps from the system of linear functions to the pseudocode of [link] , and then to the C implementation included in Appendix 1 .

[link] explicitly handles the base case for $N=2$ , to accommodate not only size 2 transforms, but also size 4 and size 8 transforms (and all larger transforms that are ultimately composed of these smaller transforms). A size 4 transform is divided into two size 1 sub-transforms and one size 2 transform,which cannot be further divided by the split-radix algorithm, and so it must be handled as a base case. Likewise with the size 8 transform that divides into one size 4 sub-transform and two size 2 sub-transforms: the size 2 sub-transforms cannot be further decomposed with the split-radix algorithm.

Also note that two twiddle factors, viz. ${\omega }_N^k$ and ${\omega }_N^{3}k$ , are required for the split-radix decomposition; this is an advantage compared to the radix-2 decomposition which would require fourtwiddle factors for the same size 4 transform.

Conjugate-pair

From a pseudocode perspective, there is little difference between the ordinary split-radix algorithm and the conjugate-pair algorithm (see [link] ). In line 10, the $x_{4n_4+3}$ terms have been shifted cyclically by $-4$ to $x_{4n_4-1}$ , and in lines 12-15, the coefficient of $Z_k^{\text{'}}$ has been shifted cyclically from ${\omega }_N^{3k}$ to ${\omega }_N^{-k}$ .