On the number of multiplications necessary to compute a length-2 exp n DFT
The number of multiplications necessary and sufficient to compute a length-2 exp n DFT is determined. The method of derivation is shown to apply to the multiplicative complexity results of Winograd (1980, 1981) for a length-p exp n DFT, for p an odd prime number. The multiplicative complexity of the one-dimensional DFT is summarized for many possible lengths.
Heideman, M. T.↗