From Generating Functions to the Fast Fourier Transform How roots of unity, divide-and-conquer, and butterfly computation turn the DFT into the FFT. September 12, 2026