How does Fourier Transform Multiply Numbers?

There is not a direct relationship between Fourier Transform and the multiplication of numbers. Let me guide you through it:

The complexity of multiplication is $N^2$ (N is the generalization of digit amount, and we do N^2 multiplications to multiply two N-digit numbers).

Now, the good part, multiplication in polynomial point-value form (be patient, I’ll explain what this is in detail shortly) takes only $N$ computations instead of $N^2$ .

If we somehow can represent our number in polynomial form, and turn it into point-value form, then we should be able to do the multiplication in complexity of $N$ instead of $N^2$ .

Faster Multiplication with Polynomials (coefficient and point-value form)

As stated before, the complexity of multiplication is $N^2$ . However, the complexity of multiplication for polynomials, in point-value form, is $N$ .

WOW!

But what is point-value form?

Recap on point-value/coefficient form (start)

If you feel like you don’t need this recap, feel free to skip till you see Recap on point-value/coefficient form (end).

An example polynomial: $3x^2 + 2x + 5$

Coefficient form (the most popular one): we just denote the coefficients. For our example above, the coefficient form would be:

3, 2, 5

How to construct a polynomial from coefficient form? It is pretty straightforward:

3x^2 + 2x^1 + 5x^0 = 3x^2 + 2x + 5

Point-value form is a bit more different. The above polynomial example is degree 2 (the highest power of x). If we give 3 points on this polynomial, there won’t be any other degree 2 polynomial that passes from these 3 points. In short, if there is n+1 points, there can be only one polynomial of degree n that satisfies these points. The points will be x and y pairs in this case.

(1, 10), (2,21), (3,38)

You can check it for yourself; when you plug 1, the polynomial spits out 10. And so on…

Recap on point-value/coefficient form (end)

Here is a showcase of multiplying two polynomials in point-value form:

1st polynomial: $x^2 + 1$
2nd polynomial: $2x^2 + 2$
3rd polynomial (what should we get by multiplying the above two): $2x^4 + 4x^2 + 2$

The resulting polynomial is of degree 4. So, we will need at least 5 points to be able to represent that polynomial in point-value form.

Let’s pick 5 points each from our 1st and 2nd polynomial.

5 points for polynomial: $x^2 + 1$ $x^{2} + 1$ :
- (0, 1), (1, 2), (2, 5), (3, 10), (4, 17)
5 points for polynomial $2x^2 + 2$ $2 x^{2} + 2$ :
- (0, 2), (1, 4), (2, 10), (3, 20), (4, 34)

Let’s multiply the y values of the points that share the same x value.

(0,1).(0,2) = (0,2)

(1, 2).(1,4) = (1,8)

(2,5).(2,10) = (2, 50)

(3,10).(3,20) = (3,200)

(4,17).(4,34) = (4,578)

If you plug these points we just calculated, into the 3rd polynomial, you’ll see they will satisfy the equation.

How will this be useful for the regular multiplication?

Here is the recipe:

Have 2 numbers to multiply
Treat these numbers as the coefficient representation of a polynomial
Compute the point-value form of these 2 polynomials
Multiply these 2 polynomials in point-value form
Convert the resulting polynomial back into coefficient form
Here is the result of your multiplication!

A demo for the above recipe:

I will use the same example from our multiplication in point-value form, so that it would be easier to follow:

11 and 22
$x^2 + 1$ for 11,
$2x^2 + 2$ for 22
(0, 1), (1, 2), (2, 5), (3, 10), (4, 17) for 11, (0, 2), (1, 4), (2, 10), (3, 20), (4, 34) for 22
Point-value form: (0, 2), (1, 8), (2, 50), (3, 200), (4, 578)
Coefficient form: $2x^4 + 4x^2 + 2$
242 = 11 x 22 indeed!

Our astute readers may realize that we may have reduced the complexity of multiplication to $N$ from $N^2$ , but now we have another problem. The complexity of computing the point-value form from the coefficient form is $N^2$ .

Here is where the magic happens. DFT can convert from coefficient form to point-value form (and vice versa). And if we follow a specific algorithm (FFT) to compute DFT, we can do this computation in $N\log(N)$ . Effectively, we will be able to multiply two numbers in $N\log(N)$ .

How Fourier transform can convert between coefficient and point-value form?

It is amazing that with this very same formula we used for wave decomposition:

\sum_{n=0}^{N-1} g_ne^{-ikn2\pi/N}

we are able to convert between coefficient and point-value form of polynomials. In this form, it’s not easy to see why this formula will be able to convert from coefficient and point-value form. I’ll help you.

First, a formal definition of a polynomial:

A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \ldots + a_{N-1}x^{N-1}

In this definition, A(x) is the polynomial, whose coefficients are given by a.

Recall the DFT formula, when we were inspecting waves, g was representing the time-domain. We are not dealing with waves in here; let’s rename the g into a.

\sum_{n=0}^{N-1}a_ne^{-ikn2\pi/N}

Let’s define:

\omega_N = e^{-i2\pi / N}

So, we can rewrite our DFT formula as:

\sum_{n=0}^{N-1}a_n\omega_N^{kn}

We are very close! As the last step, let’s make one more abstraction:

\omega_N^k = x

And voila!

\sum_{n=0}^{N-1}a_nx^n

This formula is actually equal to the definition of a polynomial we gave above! Recall:

A(x) = a_0x^0 + a_1x^1 + a_2x^2 + a_3x^3 + \ldots + a_{N-1}x^{N-1}

So:

A(x) = \sum_{n=0}^{N-1}a_nx^n

Now, you probably have the question about this equation:

x = e^{-ik2\pi/N}

Why decomposing a wave and transitioning between coefficient and point-value forms are similar?

At first glance, decomposing a wave and transitioning between coefficient to point-value form, seem to be very unrelated. But if they share the exact same formula, they should be sharing a very common intuition behind all these.

I have a great answer on why decomposing a wave and transitioning between coefficient to point-value form are nearly identical.

Recall these transformations from point-value form to coefficient form from above:

Point-value: (0, 2), (1, 8), (2, 50), (3, 200), (4, 578)
Coefficient: $2x^4 + 4x^2 + 2$

What we are doing is, inputting some points from the polynomial, and outputting the formula of the polynomial.

We can say the same for decomposing waves. We are inputting some data points from the wave, and getting back the formula of the wave (amplitudes and phases of the sine waves in it).

Of course, the above explanation is an oversimplification that misses some details. But it really is the intuition behind all these:

By using the data points from a complex function, deducing what the actual complex function is.

If you want to see a working example where we get $2x^4 + 4x^2 + 2$ by multiplying $x^2 + 1$ and $2x^2 + 2$ , try to run this Python code (taken from here):

import numpy
from numpy.fft import fft, ifft


def poly_mul(p1, p2):
    """Multiply two polynomials.

    p1 and p2 are arrays of coefficients in degree-increasing order.
    """
    deg1 = p1.shape[0] - 1
    deg2 = p1.shape[0] - 1
    # Would be 2*(deg1 + deg2) + 1, but the next-power-of-2 handles the +1
    total_num_pts = 2 * (deg1 + deg2)
    next_power_of_2 = 1 << (total_num_pts - 1).bit_length()

    ff_p1 = fft(numpy.pad(p1, (0, next_power_of_2 - p1.shape[0])))
    ff_p2 = fft(numpy.pad(p2, (0, next_power_of_2 - p2.shape[0])))
    product = ff_p1 * ff_p2
    inverted = ifft(product)
    rounded = numpy.round(numpy.real(inverted)).astype(numpy.int32)
    return numpy.trim_zeros(rounded, trim='b')


p1 = numpy.array([1, 0, 1])
p2 = numpy.array([2, 0, 2])
print(poly_mul(p1, p2))

This is just a sneak peak. We will dive into details of FFT, and derive it ourselves in the next post!

For Math Nerds

To some people, the above explanations might have already rung a bell: convolution. Convolution is basically the combination of two functions to create a third function. However, I won’t dive into that. This post has already become too long. I’m just showing the curious readers the way.

IV. Fourier Transform and Multiplication