Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using Fourier Transforms to Multiply Numbers

blog.robertelder.org

Post reply on HN
Print view View original

11–20 of 44 posts

Re: Using Fourier Transforms to Multiply Numbers

#11

Post by dreamcompiler »

Konnstann wrote: post #5
janders wrote: post #4

Earlier quoted context omitted.

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 Four…

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

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

#13

Post by gjm11 »

meuk wrote: post #2

Intuitive 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 the coefficients of the product of two polynomials.

Re: Using Fourier Transforms to Multiply Numbers

#14

Post by giornogiovanna »

Hernanpm wrote: post #12

This is well know in competitive programming usually it's the second best alternative after karatsuba.

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?

Re: Using Fourier Transforms to Multiply Numbers

#15

Post by bcaa7f3a8bbc »

giornogiovanna wrote: post #14
Hernanpm wrote: post #12

This is well know in competitive programming usually it's the second best alternative after karatsuba.

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.

Re: Using Fourier Transforms to Multiply Numbers

#16

Post by jacobolus »

Konnstann wrote: post #5
janders wrote: post #4

Earlier quoted context omitted.

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 Four…

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

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.

Re: Using Fourier Transforms to Multiply Numbers

#17

Post by meuk »

gjm11 wrote: post #13
meuk wrote: post #2

Intuitive 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…

Ouch, good point! I was at work and a bit too eager to have the first post, I think ;)

Re: Using Fourier Transforms to Multiply Numbers

#18

Post by tzs »

A very interesting look at large integer multiplication, including the FFT method, that finds some interesting underlying connections mathematically between them all is given in the paper "Multidigit Multiplication for Mathematicians" by Daniel J. Bernstein [1].

He ties them all to exploiting certain ring homomorphisms, either to compute r s with the help of f(s) f(s) or to compute f(r) f(s) with the help of r s. Karatsuba, Toom, FFT, Schönhage–Strassen...all are using ring homomorphisms to go between what you want to be doing and something that is easier.

Also see his later "Fast multiplication and its applications" [2].

[1] https://cr.yp.to/papers/m3.pdf

[2] https://cr.yp.to/lineartime/multapps-20080515.pdf

Re: Using Fourier Transforms to Multiply Numbers

#19

Post by mturmon »

gjm11 wrote: post #13
meuk wrote: post #2

Intuitive 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…

Thanks for that alternate way of thinking about it. As an engineer, half of my intuition about the FFT comes from the notion of the "frequency domain", and the other half from "change of basis".

The explanation you gave, of FFT as an alternative representation of a polynomial through its value at selected points, gives that nice intuition about pointwise multiplication, without appealing (directly) to the "convolution-turns-into-multiplication" catchphrase.

Re: Using Fourier Transforms to Multiply Numbers

#20

Post by earthicus »

I 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 * odd = even, odd * odd = odd, etc...

But a moment's reflection reveals there is nothing special about being a multiple of two. We can just as well consider multiples of three and divide the universe into three groups: if a number is a multiple of three (i.e. n=3k+0) we call it 3-even, or if n=3k+1 then it's 3-odd, or if n=3k+2 then it's 3...blern! Again this is interesting because we have a mini-algebraic structure, this time with three elements. For example, a 3-odd times a 3-blern is (3k+1) * (3j+2) = 3(k3j+k2+j)+2 which is a 3-blern.

Similarly we have multiples of four: 4-even, 4-odd, 4-blern, 4-pop. Making up these names is of course absurd, so we instead invent a notation: modular arithmetic. Traditional even and odd are arithmetic modulo 2 (mod 2 for short); 3-even 3-odd 3-blern are arithmetic mod 3, etc. The mini-algebras are the cyclic groups or the multiplicative groups of integers modulo n.

The key word there being cyclic: we've identified periodic structures in the integers with different 'wavelengths' or periods, which is how long it takes for the even/odd/blern cycle to repeat:

  (mod 2) 0 1 .. 2 3 .. 4 5 .. 6 7 .. 8 9 .. 10 11 ..
  (mod 3) 0 1 2 .. 3 4 5 .. 6 7 8 .. 9 10 11 ..
  (mod 4) 0 1 2 3 .. 4 5 6 7 .. 8 9 10 11 ..
----------

Back to the topic of discussion. Typically we represent a number 'locally' with coordinates given wrt a base system, but it seems we might describe a number instead nonlocally, using these cyclic groups. That is, instead of saying 1 * 10^0 + 1 * 10^1 + 0 * 10^2 ... (11) i would say

  2-odd:   11 = 2 * 5 + 1
  3-blern: 11 = 3 * 3 + 2
  4-pop:   11 = 4 * 2 + 3
  5-odd:   11 = 5 * 2 + 1
So we're doing a kind of spectral decomposition: examining the number modulo 2, then mod 3, mod 4 etc. The key observation is, if two numbers are represented this way, how do I compute their product? Well its very easy, because i know what happens when i multiply, say, an an odd times a blern.. I get a blern! Multiplication becomes a pointwise operation. My question is this... is this an equivalent encoding to the one being done by the complex roots of unity in the FFT?
Post reply on HN