0.2 Implementation details  (Page 4/9)

[link] is almost a 1:1 mapping of the system of linear equations , except that the base cases of $N=1,2,4$ are handled explicitly. In [link] , the case of $N=4$ is handled with two size 2 base cases, which are combined into a size 4 FFT.

Putting it all together

The simple implementations covered in this section were benchmarked for sizes of transforms $2^2$ through to $2^{18}$ running on a Macbook Air 4,2 and the results are plotted in [link] . The speed of each transform is measured in Cooley-Tukey gigaflops (CTGs), where a higher measurement indicates afaster transform. CTGs are an inverse time measurement. See Benchmark methods for a full explanation of the benchmarking methods.

It can be seen from [link] that although the conjugate-pair and split-radix algorithms have exactly the same FLOP count, the conjugate-pair algorithm is substantially faster. The differencein speed can be attributed to the fact that the conjugate-pair algorithm requires only one twiddle factor per size 4 sub-transform, whereas the ordinary split-radix algorithm requires two.

Though the tangent FFT requires the same number of twiddle factors but uses fewer FLOPs compared to the conjugate-pair algorithm, its performance isworse than the radix-2 FFT for most sizes of transform, and this can be attributed to the cost of computing the scaling factors.

A simple analysis with a profiling tool reveals that each implementations' runtime is dominated by the time taken to compute the coefficients. Even in thecase of the conjugate-pair algorithm, over $55\%$ of the runtime is spent calculating the complex exponential function. Eliminating this performancebottleneck is the topic of the next section.

Precomputed coefficients

The speed of [link] – [link] may be dramatically improved if the coefficients are precomputed and stored in alookup table (LUT).

When computing an FFT of size $N$ , [link] requires $N/2$ different twiddle factors that correspond to $N/2$ samples of a half rotation around the complex plane. Rather than storing $N/2$ complex numbers, the symmetries of the sine and cosine waves that compose ${\omega }_N^k$ may be exploited to reduce the storage to $N/4$ real numbers – a $75\%$ reduction in memory – by storing only one quadrant of a sine or cosine wave from which thereal and imaginary parts of any twiddle factor can be constructed. Such a scheme has advantages in hardware implementations where LUT memory is acostly resource  [link] , but for modern microprocessor implementations of the FFT, it is more advantageous to have a less complexindexing scheme and better memory locality, rather than a smaller LUT.

As already mentioned, each transform of size $N$ that is computed with [link] requires $N/2$ twiddle factors from ${\omega }_N^0$ through to ${\omega }_N^{N/2}$ , but the two sub-transforms of [link] require twiddle factors ranging from ${\omega }_{N/2}^0$ through to ${\omega }_{N/2}^{N/4}$ . The twiddle factors of the sub-transforms can be obtained by downsampling the parent transform's twiddle factors by a factor of 2, andbecause the downsampling factors are all powers of 2, simple shift operations can be used to index any twiddle factor anywhere in the transform from oneLUT.