Here . Splitting into even and odd pairs gives
whose two-point inverse discrete Fourier transforms are and . The butterfly therefore yields