On the number of multiplications necessary to compute a length-2<sup>n</sup>DFT

1986/02/01 by Michael T. Heideman, C.S. Burrus · 4 citations
Computer Science · #Coding theory and cryptography #Cryptography and Residue Arithmetic #Numerical Methods and Algorithms

paper · doi:10.1109/tassp.1986.1164785

openalex publication_date 1986/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

The number of multiplications necessary and sufficient to compute a length-2nDFT is determined. The method of derivation is shown to apply to the multiplicative complexity results of Winograd for a length-pnDFT, for p an odd prime number. The multiplicative complexity of the one-dimensional DFT is summarized for many possible lengths.

Citations

• An algorithm for the machine calculation of complex Fourier series
• A new principle for fast Fourier transformation

Cited by

• A Modified Split-Radix FFT With Fewer Arithmetic Operations
• Algorithms meeting the lower bounds on the multiplicative complexity of length-2/sup n/ DFTs and their connection with practical algorithms
• Generating and Searching Families of FFT Algorithms
• Fast Fourier transform [wikipedia]