4 ms·

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 departmen

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.

Konnstann 8y ago
Bioengineer, I've basically also just used Fourier and the FFT for signal analysis, never heard of it being used for multiplication.
- sdenton4 8y ago
  Combinatorialist here; I mainly think of fourier transforms as an efficient way to shuffle cards. https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.pdf https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.p...
  - planteen 8y ago
    Neat, I've spent years with the Fourier transform and never have seen this!
- dreamcompiler 8y ago
  Yep. Grade school multiplication of two large numbers is the same thing (except for the carries) as convolution of two signals in the time domain. The numbers are the signals. You already know that piecewise multiplication in the frequency domain is equivalent to (and faster than) convolution of those signals in the time domain. So that's what FFT multiplication is about. It's only useful for VERY large numbers (thousands of digits), which is why most people never encounter it.
- jacobolus 8y ago
  Note that a “signal” in this context is just a trigonometric polynomial over a periodic interval. If you think of your periodic interval as representing angle measure, and the points in the interval as points on the unit circle in the complex plane, then your trigonometric polynomial can alternately be thought of as a Laurent polynomial in the complex plane. https://en.wikipedia.org/wiki/Laurent_polynomial https://en.wikipedia.org/wiki/Laurent_polynomial What the FFT does is convert between the values of your function at n roots of unity in the complex plane -> the coefficients of the Laurent polynomial interpolating those values.

Konnstann 8y ago

Bioengineer, I've basically also just used Fourier and the FFT for signal analysis, never heard of it being used for multiplication.

sdenton4 8y ago
Combinatorialist here; I mainly think of fourier transforms as an efficient way to shuffle cards. https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.pdf https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.p...
- planteen 8y ago
  Neat, I've spent years with the Fourier transform and never have seen this!
dreamcompiler 8y ago
Yep. Grade school multiplication of two large numbers is the same thing (except for the carries) as convolution of two signals in the time domain. The numbers are the signals. You already know that piecewise multiplication in the frequency domain is equivalent to (and faster than) convolution of those signals in the time domain. So that's what FFT multiplication is about. It's only useful for VERY large numbers (thousands of digits), which is why most people never encounter it.
jacobolus 8y ago
Note that a “signal” in this context is just a trigonometric polynomial over a periodic interval. If you think of your periodic interval as representing angle measure, and the points in the interval as points on the unit circle in the complex plane, then your trigonometric polynomial can alternately be thought of as a Laurent polynomial in the complex plane. https://en.wikipedia.org/wiki/Laurent_polynomial https://en.wikipedia.org/wiki/Laurent_polynomial What the FFT does is convert between the values of your function at n roots of unity in the complex plane -> the coefficients of the Laurent polynomial interpolating those values.