Too Long; Didn't Read
The Fast Fourier transform (FFT) is a key building block in many algorithms, including multiplication of large numbers and multiplication of polynomials. Fourier transforms also have important applications in signal processing, quantum mechanics, and other areas, and help make significant parts of the global economy happen. We'll talk about two different operations: multi-point polynomial evaluation (evaluating a degree) and its inverse, polynomial interpolation (given the evaluations of a degree <N polynomial at N different points)