On the number of multiplications necessary to compute a length-2nDFT
Michael T. Heideman, C.S. Burrus · IEEE Transactions on Acoustics Speech and Signal Processing · 1986
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.