4 ms·

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

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.

jakeinspace 7y ago
FFT requires (matrix) multiplication, but I assume it's only being used with relatively small chunks of the input numbers, which would be billions of digits long. This algorithm is not optimal for multiplying 3x4.
tprice7 7y ago
I haven't studied the Schönhage–Strassen algorithm closely so take this with a grain of salt. But I think I can give you at least a vague, simplified sense of how the FFT is relevant. 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.
adrianratnapala 7y ago
Discrete fourier transforms have always been a way of doing fast polynomial multiplication -- which is also called convolution. That is we can do (a0 + a1^z + a2*z^2...) * (b0 + b1^z + b2*z^2...) As 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) Now this is well established if we are literally doing a convolution of two sequences of complex numbers. But this is different from integer quite multiplication because: 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.
- deleted 7y ago
  [deleted]
  - deleted 7y ago
    [deleted]

jakeinspace 7y ago

FFT requires (matrix) multiplication, but I assume it's only being used with relatively small chunks of the input numbers, which would be billions of digits long. This algorithm is not optimal for multiplying 3x4.

tprice7 7y ago

I haven't studied the Schönhage–Strassen algorithm closely so take this with a grain of salt. But I think I can give you at least a vague, simplified sense of how the FFT is relevant. 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.

adrianratnapala 7y ago

Discrete fourier transforms have always been a way of doing fast polynomial multiplication -- which is also called convolution. That is we can do (a0 + a1^z + a2*z^2...) * (b0 + b1^z + b2*z^2...) As 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) Now this is well established if we are literally doing a convolution of two sequences of complex numbers. But this is different from integer quite multiplication because: 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.

deleted 7y ago
[deleted]
- deleted 7y ago
  [deleted]