Comparison of Four Fast Fourier Transform Algorithms

Abstract
Comparisons of four FFT (Fast Fourier Transform) algorithms (Brenner's, Cooley's, Fisher's, and Singleton's) have been made on the basis of program execution time, storage, and accuracy. Major modifications have been made in the generation of the trigonometric values in the Cooley and Fisher algorithms, with significant improvements in accuracy. Entry of constants in all algorithms has been changed: the constants are approximated by the best binary representation for the UNIVAC 1108 computer. Three waveform examples are used in the comparisons, namely, linear FM, random numbers, and a unit ramp. Also, the sizes of the FFT's considered are limited to powers of 2, from 16 through 8192. The results indicate that Singleton's and Brenner's algorithms have the shortest execution times and occupy the least amount of computer storage, whereas Cooley's and Fisher's algorithms are the most accurate. For example, for an FFT of size 1024 on the linear FM waveform, the maximum relative errors for the four algorithms are 0.17 x 10 to the -6th power, 0.63 x 10 to the -7th power, 0.64 x 10 to the -7th power, 0.41 x 10 to the -5th power, respectively. Thus, there is no single best algorithm for all three criteria considered; rather, each algorithm has its own area of most effective applicability.