Could someone explain how one can use the FFT in an algorithm for multiplication?
I guess I would understand if I understood what FFT actually does 'under the hood', but I assumed fft itself required multiplication.
I guess I would understand if I understood what FFT actually does 'under the hood', but I assumed fft itself required multiplication.
Multiplying polynomials is the same as convolving their coefficients, which is the same as multiplying the Fourier transforms of their coefficients (this is the convolution theorem), which can be done efficiently with the FFT. Now a base-10 number like 971 can be represented as the polynomial 9x^2 + 7x + 1 evaluated at x = 10. So multiplying base-10 numbers (or base-whatever for that matter) can sort of be seen as a special case of multiplying polynomials (plus a step afterward for carrying the digits), which can be done with the FFT.
(a0 + a1^z + a2*z^2...) * (b0 + b1^z + b2*z^2...)
fa = DFT([a0, a1, a2...]) # O(N log N)
fa = DFT([b0, b1, b2...]) # O(N log N)
fab = element-by-element multiply fa by fb # O(N)
return InverseDFT(fab) # O(N log N)
1. Polynomial multiplication doesn't have carries.
2. It does inexact arithmetic on complex-numbers, we want exact results on integer digits.
I am guessing (2) is solved by getting modulo-arithmetic do the same algebraic gymnastics that make the FFT work.
Also I didn't think any of this was new -- I vaguely remember reading about fast convolutions using discrete algebras in old textbooks from the '70s. Maybe the hard thing was to do it in a way that leaves enough information left over to do the carries.