If anyone's interested in writing and testing their code for this - https://www.spoj.com/problems/MUL/
Using Fourier Transforms to Multiply Numbers
31–40 of 44 posts
Re: Using Fourier Transforms to Multiply Numbers
#32I don’t think I’ve ever come across an algorithms book that discusses FFT that doesn’t discuss fast polynomial multiplication when introducing the algorithm. That’s literally what the FFT does, fast polynomial multiplication.
I'm guessing most people aren't introduced to FFT in an algorithms course though, they're introduced to it as the computational way to calculate an FT.
You're probably right -- and even when I saw it elsewhere it was still within the CS department.
For instance we glanced over it during my Digital Image Processing course. The professor did introduce it as a form of fast polynomial multiplication but we didn't dive too deep into Cooley-Turkey because frequency analysis was the focus of the work.
Re: Using Fourier Transforms to Multiply Numbers
#33Earlier quoted context omitted.
That is exceedingly cool. Is there anything available about this online? Sound clips, source code, etc.?
Most were typed up, but the source files were on a floppy disk somewhere in my closet. I can scan them in/upload them when I get a chance.
floppy disks what are those Kappa
Re: Using Fourier Transforms to Multiply Numbers
#34This property has helped make matrix profile computations feasible for motif discovery.
https://www.cs.ucr.edu/~eamonn/MatrixProfile.html
Re: Using Fourier Transforms to Multiply Numbers
#35Man, is there anything Fourier Transforms can't do? For a music project in college, I created a book of Hammond Organ presets by taking slices of samples from actual instruments and running FTs on them, then finding the best approximation in Hammond drawbar notation. The fact that it worked so well was such a satisfying experience that I managed to make 100+ combinations.
Wow so you made an organ sound like a bunch of other instruments? You can't just post this and not share the sounds...
Re: Using Fourier Transforms to Multiply Numbers
#36I don’t think I’ve ever come across an algorithms book that discusses FFT that doesn’t discuss fast polynomial multiplication when introducing the algorithm. That’s literally what the FFT does, fast polynomial multiplication.
If you come at it from an engineering approach (e.g., electrical engineer), it doesn't look like that at all. In fact, the focus is on filters and spectral analysis. It looked something like this when I was at Georgia Tech: First, you learn about the convolution operation that, given any input function x(t), get the output of any linear time-invariant circuit as y(t). The convolution integral is nasty, professors mak…
I've worked with filters and spectral analysis and you would often do this in CS in Digital Image Processing.
The point isn't what you use the FFT for but what the FFT does. The FFT does fast polynomial multiplication.
Re: Using Fourier Transforms to Multiply Numbers
#37Man, is there anything Fourier Transforms can't do? For a music project in college, I created a book of Hammond Organ presets by taking slices of samples from actual instruments and running FTs on them, then finding the best approximation in Hammond drawbar notation. The fact that it worked so well was such a satisfying experience that I managed to make 100+ combinations.
I sort of did the reverse for a song once, I used FFT to analyze a recording of a drawbar organ I wanted to mimic, then turned that into a ZynAddSubFX additive synthesis preset.
Re: Using Fourier Transforms to Multiply Numbers
#38Earlier quoted context omitted.
If you come at it from an engineering approach (e.g., electrical engineer), it doesn't look like that at all. In fact, the focus is on filters and spectral analysis. It looked something like this when I was at Georgia Tech: First, you learn about the convolution operation that, given any input function x(t), get the output of any linear time-invariant circuit as y(t). The convolution integral is nasty, professors mak…
I've worked with filters and spectral analysis and you would often do this in CS in Digital Image Processing. The point isn't what you use the FFT for but what the FFT does. The FFT does fast polynomial multiplication.
Yes that's true. But if you come at it looking at it as a sampled continuous signal and spectrum, you don't think of the FFT as fast polynomial multiplication. Neither viewpoint is wrong. Just different lenses for looking at different problems.
Re: Using Fourier Transforms to Multiply Numbers
#39Earlier quoted context omitted.
I've worked with filters and spectral analysis and you would often do this in CS in Digital Image Processing. The point isn't what you use the FFT for but what the FFT does. The FFT does fast polynomial multiplication.
Yes that's true. But if you come at it looking at it as a sampled continuous signal and spectrum, you don't think of the FFT as fast polynomial multiplication. Neither viewpoint is wrong. Just different lenses for looking at different problems.
I think I still think of it that way. In EE you are convolving a filter with a signal in the time domain, which you can think of as a polynomial. Doing the fft, then a vector multiply +ifft accomplishes the same thing, but using the fft.
Re: Using Fourier Transforms to Multiply Numbers
#40I have to admit that i've never gotten around to sitting down and thinking through why fast fft multiplication works, so I have a question that maybe someone here could answer. Some background: If a number is a multiple of two (i.e. n= 2k+0), we call it even, or if n=2k+1 then it's odd. This is interesting because evenness and oddness form an algebraic structure - an amoeba of an algebra with only two elements: even…
You're essentially describing a residue number system, except the different moduli need to be coprime for things to be well-defined. FFT multiplication is basically a residue number system product on polynomials. Evaluating a polynomial p(x) at a point w_i is the same as computing p(x) modulo (x - w_i), where w_i here is one of the nth roots of unity. So the FFT computes p(x) mod (x - w_0), p(x) mod (x - w_1), ..., m…
Thank you!