One interesting application of NTT polynomial multiplication is in fully-homomorphic encryption libraries, such as Microsoft's SEAL [1], where the ciphertexts are polynomials of very high degree. (Disclaimer: I work at MSR using SEAL for machine learning.)
Using Fourier Transforms to Multiply Numbers
21–30 of 44 posts
Re: Using Fourier Transforms to Multiply Numbers
#22Man, 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.
Re: Using Fourier Transforms to Multiply Numbers
#23Earlier quoted context omitted.
Generally Fourier methods are asymptotically better than Karatsuba, but with much higher constants, which makes them kind-of impractical until you get very big numbers. Anyway, do competitive programmers tend to program everything from scratch, or is there another reason they don't just use GMP?
> Anyway, do competitive programmers tend to program everything from scratch, or is there another reason they don't just use GMP? I think directly using algorithms and programs implemented by others would be considered cheating (and these libraries are not presented on the server which checks your answer anyway). In competitive programming, participants compete their own ability and knowledge to implement algorithms.
In ACM ICPC, we could bring printouts of library code and manually transcribe them into the computer. IIRC, FFT was apart of our team's library code, but you wouldn't use GMP since it would require too much typing.
Re: Using Fourier Transforms to Multiply Numbers
#24Man, 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.
That is exceedingly cool. Is there anything available about this online? Sound clips, source code, etc.?
Re: Using Fourier Transforms to Multiply Numbers
#25Man, 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.
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.
Re: Using Fourier Transforms to Multiply Numbers
#26Earlier quoted context omitted.
Generally Fourier methods are asymptotically better than Karatsuba, but with much higher constants, which makes them kind-of impractical until you get very big numbers. Anyway, do competitive programmers tend to program everything from scratch, or is there another reason they don't just use GMP?
> Anyway, do competitive programmers tend to program everything from scratch, or is there another reason they don't just use GMP? I think directly using algorithms and programs implemented by others would be considered cheating (and these libraries are not presented on the server which checks your answer anyway). In competitive programming, participants compete their own ability and knowledge to implement algorithms.
In C++ thanks to complex the implementation is short see https://ideone.com/tbHUN7
Re: Using Fourier Transforms to Multiply Numbers
#27Intuitive explanation: if you interpret a time series as the coefficients of a polynomial, the Fourier transform is just polynomial multiplication (this makes sense because polynomial multiplication is just convolution). Now we can write base b numbers as polynomials with single-digit coefficients, evaluated at x = b. Then after multiplying two such numbers/polynomials the coefficients are too large. The only thing r…
The Fourier transform isn't polynomial multiplication. (It operates on one thing, not two .) What the Fourier transform does is to translate between two representations of a polynomial: (1) its coefficients, (2) its values at a suitable set of points. And then the thing that makes FFT multiplication work is that pointwise multiplication of values is cheaper and simpler than the convolution operation that gives you th…
Every once in a while I pick up "The Scientist and Engineer's Guide to Digital Signal Processing" (freely downloadable: http://www.dspguide.com/) and it's always so satisfying to see the different relations between domains and how you can think about it. Your example is no different.
But since I never get to actually use that stuff in my just, I always forget the details.
Re: Using Fourier Transforms to Multiply Numbers
#28I 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), ..., multiplies each residue individually, and the inverse FFT recovers the result modulo (x - w_0)(x - w_1)...(x - w_{n-1}) = x^n - 1.
Re: Using Fourier Transforms to Multiply Numbers
#29I 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 make you feel the pain a bit. Then introduce the Laplace transform to make the computation much easier. Then go to continuous time, continuous frequency Fourier transform. Talk about frequency domain a bunch, learn filter topologies, etc. Circuits class over.
Now comes a signal processing class where you learn about discrete-time signals. First, talk lots about sampling. Then, get introduced discrete time convolution. Now, learn the z-transform and the discrete time Fourier transform (DTFT) for a discrete-time, continuous frequency signal. Mostly discuss filtering and spectral analysis. Intro to signal processing class over.
Learn about sampling the DTFT in the frequency domain. This is the DFT, which is usually presented as a sum that would require O(n^2) operations to compute. Learn that this corresponds to circular convolution and learn about zero padding for traditional convolution. Finally, get presented with Cooley-Tukey FFT algorithm for base-2. Focus is still signal and spectral analysis. Talk lots about windowing. You may get a mention that convolution corresponds to polynomial multiplication here. Or maybe they talk about grade-school multiplication, its really the same thing as polynomial multiplication with a carry. Senior level signal processing class over.
Re: Using Fourier Transforms to Multiply Numbers
#30Earlier quoted context omitted.
Bioengineer, I've basically also just used Fourier and the FFT for signal analysis, never heard of it being used for multiplication.
Combinatorialist here; I mainly think of fourier transforms as an efficient way to shuffle cards. https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.p...
Neat, I've spent years with the Fourier transform and never have seen this!