FFT butterfly
= FFT butterfly
{c}
{title2=$(a,b)\mapsto(a+wb,a-wb)$}
An <FFT butterfly> combines corresponding outputs of two half-sized transforms using a twiddle factor $w$. Sharing the product $wb$ costs one complex multiplication and two additions. For the unnormalized positive-exponent inverse <discrete Fourier transform> of length $2m$, use $w=e^{2\pi i\ell/(2m)}$ at index $\ell$.