IV. Fourier Transform and Multiplication

Every Intuition Behind Fourier Transform

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 N2N^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 NN computations instead of N2N^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 NN instead of N2N^2.

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

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


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: 3x2+2x+53x^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,53, 2, 5

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

3x2+2x1+5x0=3x2+2x+53x^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)(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:

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.

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

(0,1).(0,2)=(0,2)(0,1).(0,2) = (0,2) (1,2).(1,4)=(1,8)(1, 2).(1,4) = (1,8) (2,5).(2,10)=(2,50)(2,5).(2,10) = (2, 50) (3,10).(3,20)=(3,200)(3,10).(3,20) = (3,200) (4,17).(4,34)=(4,578)(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:

  1. Have 2 numbers to multiply
  2. Treat these numbers as the coefficient representation of a polynomial
  3. Compute the point-value form of these 2 polynomials
  4. Multiply these 2 polynomials in point-value form
  5. Convert the resulting polynomial back into coefficient form
  6. 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:

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

Our astute readers may realize that we may have reduced the complexity of multiplication to NN from N2N^2, but now we have another problem. The complexity of computing the point-value form from the coefficient form is N2N^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 Nlog⁑(N)N\log(N). Effectively, we will be able to multiply two numbers in Nlog⁑(N)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:

βˆ‘n=0Nβˆ’1gneβˆ’ikn2Ο€/N\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)=a0+a1x+a2x2+a3x3+…+aNβˆ’1xNβˆ’1A(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.


Let’s define:

Ο‰N=eβˆ’i2Ο€/N\omega_N = e^{-i2\pi / N}

So, we can rewrite our DFT formula as:


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

Ο‰Nk=x\omega_N^k = x

And voila!


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

A(x)=a0x0+a1x1+a2x2+a3x3+…+aNβˆ’1xNβˆ’1A(x) = a_0x^0 + a_1x^1 + a_2x^2 + a_3x^3 + \ldots + a_{N-1}x^{N-1}


A(x)=βˆ‘n=0Nβˆ’1anxnA(x) = \sum_{n=0}^{N-1}a_nx^n

Now, you probably have the question about this equation:

x=eβˆ’ik2Ο€/Nx = 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:

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 2x4+4x2+22x^4 + 4x^2 + 2 by multiplying x2+1x^2 + 1 and 2x2+22x^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.

Next Article