 Following work by Shmuel Winograd (1978), a tight Θ("N") lower bound is known for the number of real multiplications required by an FFT.It can be shown that only formula_17 irrational real multiplications are required to compute a DFT of power-of-two length formula_18.Moreover, explicit algorithms that achieve this count are known (Heideman & Burrus, 1986; Duhamel, 1990).