An in-place, in-order prime factor FFT algorithm
C.S. Burrus, Peter Eschenbacher · IEEE Transactions on Acoustics Speech and Signal Processing · 1981
This paper presents a Fortran program that calculates the discrete Fourier transform using a prime factor algorithm. A very simple indexing scheme is employed that results in a flexible, modular algorithm that efficiently calculates the DFT in-place. A modification of this algorithm gives the output both in-place and in-order at a slight cost in flexibility. A comparison shows it to be faster than both the Cooley-Tukey algorithm and the Winograd nested algorithm.