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.
No takes yet. Share an insight, caveat, or question.
Heideman et al. (1986) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: