A modified split-radix FFT with reduced arithmetic complexity
Steven G. Johnson, Matteo Frigo · 2005
Recent results by Van Buskirk et al. have broken the record set by Yavne in 1968 for the lowest arithmetic complexity (exact count of real additions and multiplications) to compute a power-of-two discrete Fourier transform. Here, we present a simple recursive modification of the split-radix algorithm that computes the DFT with asymptotically about 6 % fewer operations than Yavne, matching the count achieved by Van Buskirk’s program-generation framework. We also discuss the application of our algorithm to real-data and real-symmetric (discrete cosine) transforms, where we are again able to achieve lower arithmetic complexity than previously published algorithms.