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

Not a book, but I truly enjoy this guy’s videos: this video . I usually watch them while eating lunch. He does a truly fantastic job.

As the author mentions, convolutions for signal processing and convolutions for probability are essentially equivalent things in two different contexts. It is interesting that the same concept is behind the multiplication of polynomials. In the discrete case we have the parallel of the vectors representing ... the (discretized) probability density <-> the (discrete) signal intensity <-> the coefficients of the polynomial ... in the respective context. If we look at the discrete case, since the operation of convolution is computationally expensive (O(n^3)), people often rely on the Fast Fourier Transform Algorithm (FFT), that runs in O(n log(n)). An excellent and very enjoyable video on the FFT applied to the polynomial multiplication is this video .

That video did the same for me. I also like the reducible video for Fast Fourier Transforms as well as the Veratasium piece that shares some fun history. Reducible - FFTs the most ingenious algorithm ever this video Veritasium - The Most Important Algorithm of All Time link

If you haven’t seen it yet, you should watch this video: this video It derives the FFT algorithm from polynomial multiplication and it’s fantastic . I rewatch it every 6 months or so.

I almost always prefer text over video, but this video on the same subject is fantastic: this video . I watch it at least once every year. Also, the title of the blog post (and by extension this HN post) is IMO not really correct: it's not about the DFT but specifically about the FFT.