Re:Using Fourier Transforms to Multiply Numbers
by janders on Thursday January 10, 2019 @11:49AM
(#18875327)
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.
[ Parent
| on HN ]
Re:Using Fourier Transforms to Multiply Numbers
by Konnstann on Thursday January 10, 2019 @11:59AM
(#18875456)
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
by sdenton4 on Thursday January 10, 2019 @12:22PM
(#18875720)
Combinatorialist here; I mainly think of fourier transforms as an efficient way to shuffle cards.
https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.p...
Re:Using Fourier Transforms to Multiply Numbers
by planteen on Thursday January 10, 2019 @05:54PM
(#18879223)
Neat, I've spent years with the Fourier transform and never have seen this!
Re:Using Fourier Transforms to Multiply Numbers
by dreamcompiler on Thursday January 10, 2019 @12:25PM
(#18875769)
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.
Re:Using Fourier Transforms to Multiply Numbers
by jacobolus on Thursday January 10, 2019 @01:02PM
(#18876210)
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
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.