The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?

Caption notes

This FFT introduction starts with polynomial multiplication. Evaluating both polynomials at enough distinct shared points and multiplying the corresponding values gives the product polynomial’s values at those points. The video then explains how to choose points to make evaluation faster. In the power-of-two case it discusses, splitting the terms by even and odd degree and squaring the roots of unity gives the smaller set of roots needed at the next recursive step.