Using Fourier Transforms to Multiply Numbers
blog.robertelder.org
Using Fourier Transforms to Multiply Numbers
1–10 of 44 posts
Re: Using Fourier Transforms to Multiply Numbers
#2Intuitive explanation: if you interpret a time series as the coefficients of a polynomial, the Fourier transform is just polynomial multiplication (this makes sense because polynomial multiplication is just convolution). Now we can write base b numbers as polynomials with single-digit coefficients, evaluated at x = b. Then after multiplying two such numbers/polynomials the coefficients are too large. The only thing remaining is too carry the overflows in the digits to the next digit (much like the school algorithm for adding numbers).
Re: Using Fourier Transforms to Multiply Numbers
#3I don’t think I’ve ever come across an algorithms book that discusses FFT that doesn’t discuss fast polynomial multiplication when introducing the algorithm.
That’s literally what the FFT does, fast polynomial multiplication.
Re: Using Fourier Transforms to Multiply Numbers
#4I don’t think I’ve ever come across an algorithms book that discusses FFT that doesn’t discuss fast polynomial multiplication when introducing the algorithm. That’s literally what the FFT does, fast polynomial multiplication.
So interesting thing that. While I was introduced to the FFT in the same manner, (an algorithm for fast polynomial multiplication in a class by the CS department) my Electrical-Engineering-backgrounded colleagues are completely unaware of this use of the FFT. They use it as a change of basis to directly observe and manipulate frequency. The EEs I work with are much more familiar with the relationship between the Fourier transform of a function and what the original function looks like.
Re: Using Fourier Transforms to Multiply Numbers
#5I don’t think I’ve ever come across an algorithms book that discusses FFT that doesn’t discuss fast polynomial multiplication when introducing the algorithm. That’s literally what the FFT does, fast polynomial multiplication.
So interesting thing that. While I was introduced to the FFT in the same manner, (an algorithm for fast polynomial multiplication in a class by the CS department) my Electrical-Engineering-backgrounded colleagues are completely unaware of this use of the FFT. They use it as a change of basis to directly observe and manipulate frequency. The EEs I work with are much more familiar with the relationship between the Four…
Bioengineer, I've basically also just used Fourier and the FFT for signal analysis, never heard of it being used for multiplication.
Re: Using Fourier Transforms to Multiply Numbers
#6I don’t think I’ve ever come across an algorithms book that discusses FFT that doesn’t discuss fast polynomial multiplication when introducing the algorithm. That’s literally what the FFT does, fast polynomial multiplication.
Hmm, I'd bring convolution to this salad. I think in polynomial product when thinking about convolving.
Re: Using Fourier Transforms to Multiply Numbers
#7I wrote a much more in-depth analysis of Schonhage-Strassen and why exactly it's an O(N log N log log N) algorithm here: https://psun.me/post/fft2/
It's pretty interesting--it's actually a recursive multiplication algorithm with log log N levels of recursion and N log N work at each level. And it actually uses another fast multiplication algorithm within it, the Karatsuba algorithm.
Re: Using Fourier Transforms to Multiply Numbers
#8For anyone who's interested in a more long-form, intuitive explanation of the fourier transform and how you can use it to multiply polynomials, I'd highly recommend Erik Demaine's lecture on the topic: https://www.youtube.com/watch?v=iTMn0Kt18tg.
Re: Using Fourier Transforms to Multiply Numbers
#9I don’t think I’ve ever come across an algorithms book that discusses FFT that doesn’t discuss fast polynomial multiplication when introducing the algorithm. That’s literally what the FFT does, fast polynomial multiplication.
I'm guessing most people aren't introduced to FFT in an algorithms course though, they're introduced to it as the computational way to calculate an FT.
Re: Using Fourier Transforms to Multiply Numbers
#10Earlier quoted context omitted.
So interesting thing that. While I was introduced to the FFT in the same manner, (an algorithm for fast polynomial multiplication in a class by the CS department) my Electrical-Engineering-backgrounded colleagues are completely unaware of this use of the FFT. They use it as a change of basis to directly observe and manipulate frequency. The EEs I work with are much more familiar with the relationship between the Four…
Bioengineer, I've basically also just used Fourier and the FFT for signal analysis, never heard of it being used for multiplication.
Combinatorialist here; I mainly think of fourier transforms as an efficient way to shuffle cards.
https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.p...