4 ms·

Multiplication using FFTs was one of the most mind-blowing things I encountered in my professional career. It involved realizing that third-grade multiplication

Multiplication using FFTs was one of the most mind-blowing things I encountered in my professional career. It involved realizing that third-grade multiplication is in fact polynomial convolution, and in the frequency domain that just becomes coefficient-wise multiplication. The Karatsuba method is almost as cool and more practical for smallish numbers.

lordnacho 8y ago
Can you explain the connection with FFT? Or provide some useful links? Sounds really interesting.
- sumnole 8y ago
  If you have CLRS 3rd edition, check out chapter 30
- tprice7 8y ago
  I gave a quasi-explanation in response to lamename's comment. If you want some search queries, learn what convolution is, then observe the connection between discrete convolution and polynomial multiplication, then learn about the convolution theorem.
  - lordnacho 8y ago
    This bringing back control theory for me. Thanks.
- dreamcompiler 8y ago
  If you know what an FFT is you know that it's very often used for signal processing. You probably also know that convolution in the time domain is the same as multiplication in the frequency domain, and vice-versa. So now imagine a multiplication of two numbers, say 12345 * 67890. Imagine each number is a signal where the digits are samples. Multiplying like you were taught in third grade is effectively convolving one signal by the other.[0] Do this with pen and paper to see it clearly. So if we call normal third-grade multiplication "time domain convolution," we can imagine converting both signals (both numbers) into the "frequency" domain with two applications of the FFT, then multiplying their frequency domain samples component-wise (which is much faster than convolution) and then taking an inverse FFT of the result. That's the algorithm in a nutshell. It would buy you nothing on the numbers above because they're much too small. But for numbers with thousands of digits, it's a big speedup from O[n^2] to roughly O[nlogn]. [0] I'm oversimplifying. It's actually polynomial convolution and you have to do carries. That's slightly harder than signal convolution, but the idea is the same.

lordnacho 8y ago

Can you explain the connection with FFT? Or provide some useful links? Sounds really interesting.

sumnole 8y ago
If you have CLRS 3rd edition, check out chapter 30
tprice7 8y ago
I gave a quasi-explanation in response to lamename's comment. If you want some search queries, learn what convolution is, then observe the connection between discrete convolution and polynomial multiplication, then learn about the convolution theorem.
- lordnacho 8y ago
  This bringing back control theory for me. Thanks.
dreamcompiler 8y ago
If you know what an FFT is you know that it's very often used for signal processing. You probably also know that convolution in the time domain is the same as multiplication in the frequency domain, and vice-versa. So now imagine a multiplication of two numbers, say 12345 * 67890. Imagine each number is a signal where the digits are samples. Multiplying like you were taught in third grade is effectively convolving one signal by the other.[0] Do this with pen and paper to see it clearly. So if we call normal third-grade multiplication "time domain convolution," we can imagine converting both signals (both numbers) into the "frequency" domain with two applications of the FFT, then multiplying their frequency domain samples component-wise (which is much faster than convolution) and then taking an inverse FFT of the result. That's the algorithm in a nutshell. It would buy you nothing on the numbers above because they're much too small. But for numbers with thousands of digits, it's a big speedup from O[n^2] to roughly O[nlogn]. [0] I'm oversimplifying. It's actually polynomial convolution and you have to do carries. That's slightly harder than signal convolution, but the idea is the same.