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). However, these algorithms require too many additions to be practical, at least on modern computers with hardware multipliers (Duhamel, 1990; Frigo & Johnson, 2005).