The Fast Fourier Transform Most Ingenious Algorithm Ever?
In this video, we take a look at one of the most beautiful algorithms ever created: the Fast Fourier Transform (FFT). This is a tricky algorithm to understand so we take a look at it in a context that we are all familiar with: polynomial multiplication. You will see how the core ideas of the FFT can be « discovered » through asking the right questions. The key insights that are presented in this video is that polynomial multiplication can be improved significantly by multiplying polynomials in a special value representation. The challenge that presents itself is the problem of converting a polynomial from a standard coefficient representation to value representation.
We see that the FFT is an incredibly efficient recursive algorithm that performs this task, and we also discover that a slightly tweaked FFT (Inverse FFT) can also solve the reverse problem of interpolation. If this video doesn’t blow your mind, I don’t know what will.
0:00 Introduction 2:19 Polynomial Multiplication 3:36 Polynomial Representation 6:06 Value Representation Advantages 7:07 Polynomial Multiplication Flowchart 8:04 Polynomial Evaluation 13:49 Which Evaluation Points? 16:30 Why Nth Roots of Unity? 18:28 FFT Implementation 22:47 Interpolation and Inverse FFT 26:49 Recap