Previously I wrote about the Karatsuba Method of multiplication. While learning about it, I also learned that mathematicians have been able to use the Fast Fourier Transform to multiply extremely large numbers EVEN FASTER.
As a former electrical engineering major, I was like how the heck do they do that?
Turns out there are two gaps of knowledge. First, you have to understand the convolution operation and how that can be treated like a multiplication function. Then, connect the dot that a FFT is a faster way to perform a convolution, reducing the operation from O(N²) to O(N log(N)).
In this article, I’ll explain the first gap. What is convolution and how to use it to multiply numbers. I learned a lot from this YouTube video. Highly recommended if you are interested in math.
What is Convolution
Convolution is a math operation that lets you combine two things to get a third thing. Thing one can be a math function, a radio, electrical, or audio signal, a 2D image, etc. Thing two might be another math function to…
