Every Intuition Behind Fourier Transform

Let me start with a good news! Fast Fourier Transform is not another formula. In fact, FFT is not a formula. So, what’s FFT all about? It efficiently crunches the amount of computation required for the Discrete Fourier Transform (DFT) formula we crafted earlier, doing it in a speedy Nlog⁑(N)N\log(N) instead of the sluggish N2N^2.

Now, let’s dive into EFFICIENTLY transforming a polynomial from Coefficient Representation to Point-Value representation and we will naturally stumble upon FFT.

Coefficient to Point-Value Representation

Switching from coefficients to points is simple. Take this polynomial:

P(x)=3x3+2x2βˆ’4xβˆ’1P(x) = 3x^3 + 2x^2 -4x -1

In coefficient form: 3,2,-4,-1.

To show it in point-value form, we need at least 4 points (for an n degree polynomial, we need n+1). So, let’s choose 1,2,3,4:

For each point, it involves 3 multiplications and 3 additions. In total: 12 multiplications, 12 additions.

note: we also need to calculate the powers of x, but we can re-use the same points for every polynomial, and pre-compute these powers. So I did not account them in here.

The complexity for naive evaluation is roughly d^2, where d is the degree of the polynomial.

That’s not fast, we will try to improve this.

Even and Odd functions

We can be smarter by picking numbers strategically based on the concept of even and odd functions.

Take an even polynomial:

P(x)=x2P(x) = x^2

For even functions, f(βˆ’x)=f(x)f(-x) = f(x), letting us evaluate more points without extra work.

For odd functions, f(βˆ’x)=βˆ’f(x)f(-x) = -f(x), offering the same efficiency.

To handle any polynomial, we split it into even and odd parts:

P(x)=3x3+2x2βˆ’4xβˆ’1P(x) = 3x^3 + 2x^2 -4x -1 E(x)=2x2βˆ’1E(x) = 2x^2 -1 O(x)=3x3βˆ’4xO(x) = 3x^3 - 4x

Combining E(x) and O(x) brings back our original P(x)! And this comes with some neat properties:

P(x)=E(x)+O(x)P(βˆ’x)=E(βˆ’x)+O(βˆ’x)P(βˆ’x)=E(x)βˆ’O(x)P(x) = E(x) + O(x) \newline P(-x) = E(-x) + O(-x) \newline P(-x) = E(x) - O(x)

To sum it up: Instead of crunching numbers for 4 points (1,2,3,4) as we did before, now we can simply evaluate our Even and Odd polynomials for 2 points (1, 2).

E(1)=2.1βˆ’1=1E(2)=2.4βˆ’1=7O(1)=3.1βˆ’4.1=βˆ’1O(2)=3.8βˆ’4.2=16E(1) = 2.1 - 1 = 1 \newline E(2) = 2.4 - 1 = 7 \newline O(1) = 3.1 - 4.1 = -1 \newline O(2) = 3.8 - 4.2 = 16

And then calculate P(x) as follows:

P(1)=1+(βˆ’1)=0P(βˆ’1)=1βˆ’(βˆ’1)=2P(2)=7+16=23P(βˆ’2)=7βˆ’16=9P(1) = 1 + (-1) = 0 \newline P(-1) = 1 - (-1) = 2 \newline P(2) = 7 + 16 = 23 \newline P(-2) = 7 - 16 = 9

A quick warning:

Our complexity now is: (N/2)N=N2/2(N/2)N = N^2 / 2

It is 2 times better, but in the end, it is still N^2.

We can do even better.

OUTCOME: by using positive-negative symmetry, we can halve the required evaluations.

Divide and Conquer

Right now, we can reduce the amount of points needed to evaluate the polynomial by half. Unfortunately, this reduction can only be applied once. How great would it be if we could employ the same approach for our even and odd functions?

Let’s revisit the example:

P(x)=3x3+2x2βˆ’4xβˆ’1E(x)=2x2βˆ’1O(x)=3x3βˆ’4xP(x) = 3x^3 + 2x^2 - 4x - 1 \newline E(x) = 2x^2 - 1 \newline O(x) = 3x^3 - 4x

But we cannot further divide E(x)E(x) into its own even and odd parts because the terms inside E(x)E(x) are all even. The same story for O(x)O(x)… We have to find another way.

Another way

If you think about it, we actually don’t care about the terms being even and odd. We care about positive-negative symmetry. That is why the even and odd functions were useful for us in the first place.

With this mindset, let’s inspect the signs of 1+x+x2+x3+x4+x5+x6+x71 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7:

Current situation:

What we are searching for is, creating the same pattern + - + - for both E(x)E(x) and O(x)O(x). Then we will be able to further divide E(x)E(x) and O(x)O(x) to their components by taking advantage of the positive-negative symmetry.


Let’s think outside of the box. Right now, we are free to create non-sense by pure imagination. Assume that, somehow, we have these signs for

1+x+x2+x3+x4+x5+x6+x71 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7:

Then, we have:

Wohoo! In an imaginary world, we solved our previous problem. We can further divide E(x)E(x) and O(x)O(x) to their positive and negative parts (as we previously split P(x)P(x) into its own even(positive) and odd(negative) parts).

We just need to find the ? (if such a value exists in the first place).

Finding ?

Thinking outside of the box is not easy. One good approach is to focus on what we already know and deduce more abstract generalizations from it.

Again, I present you: 1+x+x2+x3+x4+x5+x6+x71 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7:

Any negative xx value will produce the below signs, right?

+ - + - + - + -

Why so? Why do negative numbers create such a pattern?

The above questions might sound stupid, and you might be rolling your eyes. But to find the essence of knowledge, we sometimes need to ask such questions.

To have the pattern + - + - + - + -, we need to flip the sign each time when we multiply with xx, right? Each time we increment the power of xx, we want the sign to flip.

And that’s why any negative number would do for our needs.

Let’s try to apply the same steps to the pattern:

+ + - - + + - -

We need to flip the sign each time when we multiply with x2x^2, right? And flipping the bit means, basically multiplying with βˆ’1-1. Each time we increment the power of xx by 2, we want the sign to flip.

So, we need to solve this equation:

x2=βˆ’1x^2 = -1

And the solution to ? in our imaginary world, is an imaginary number, i!

See how those StUPid questions helped us? I hope your attitude towards such basic questions has changed now.

We now have 2 different pairs with 1:

To eliminate potential confusion in the future, we should be able to distinguish them.

So, let’s say:

Using i as a root to create symmetry

Coming back to where we left off:

P(x)=3x3+2x2βˆ’4xβˆ’1E(x)=2x2βˆ’1O(x)=3x3βˆ’4xP(x) = 3x^3 + 2x^2 - 4x - 1 \newline E(x) = 2x^2 - 1 \newline O(x) = 3x^3 - 4x

Now we can divide E(x)E(x) into its own even and odd parts. I know even and odd does not make sense. Think of them as more even and more odd if you will! Let me demonstrate on E(x)E(x):

So, we have:

E(x)=2x2βˆ’1=EE(x)+EO(x)E(x) = 2x^2 - 1 = EE(x) + EO(x)


EE(x)EE(x) is a constant function (the input xx does not have any effect on it). So, we can say EE(x)=EE(y)EE(x) = EE(y).

As previously, the odd part EO(x)EO(x) will flip the sign between inputs. However, instead of the pair 1 and -1, we have 1 and i as a pair for EO(x)EO(x).

So, instead of evaluating EO(x)EO(x) for both 11 and ii, we can just evaluate it for 11, and we can let the positive-negative symmetry do the rest of the job for us.

See it yourself: EO(1)=βˆ’EO(i)EO(1) = -EO(i).

And EE(1)=EE(i)EE(1) = EE(i) (remember, constant function).

E(1)=EE(1)+EO(1)E(i)=EE(1)βˆ’EO(1)E(1) = EE(1) + EO(1) \newline E(i) = EE(1) - EO(1)

Note: -i and -1 are also forming a pair in x2x^2 space, just as 1 and i.

OUTCOME: by utilizing i, we can create positive-negative symmetry in x2x^2 space.

Odd functions

Let’s continue with: O(x)=3x3βˆ’4x=OE(x)+OO(x)O(x) = 3x^3 - 4x \newline = OE(x) + OO(x):

For OE(x)OE(x), we cannot use our calculation for OE(1)OE(1) to derive OE(i)OE(i). You see why? Because the power of xx is only 1. And we need x2x^2 in order to make 1 and i a positive-negative pair. This is a problem… Our optimization is hindered.

For OO(x)OO(x), can we use our calculation for OO(1)OO(1) to derive OO(i)OO(i)? Well, yes and no. 3x33x^3 includes x2x^2 but there is a remainder xx.

OO(x)=3x2(x)OO(x) = 3x^2(x)

Check it yourself, we cannot say OO(1)=βˆ’OO(i)OO(1) = -OO(i).

Damn, it worked great with the Even variant…

Manipulating Odd variant

Oh yes! That’s the solution: it worked great with the Even variant.

If we somehow make Odd variants look like the Even variants, our problems should be solved.

Let’s redefine the Odd variants by factoring an xx out of them, hence, making the powers of xx even.

P(x)=E(x)+xO(x)P(x) = E(x) + xO(x) P(x)=3x3+2x2βˆ’4xβˆ’1E(x)=2x2βˆ’1O(x)=3x2βˆ’4P(x) = 3x^3 + 2x^2 - 4x - 1 \newline E(x) = 2x^2 - 1 \newline O(x) = 3x^2 - 4

And for the next level:

Notice that each recursion, we increment the power of xx that we will factor out.

In this case:

Good news! Now all of them are constant functions, which means, we can rewrite them like this:

OUTCOME: by factoring out the powers of xx from odd functions (w.r.t the recursion level), we achieve consistency across steps, which is crucial for creating an algorithm.

Big Picture Reminder

Let me remind you the big picture.

We initially needed 4 points to evaluate P(x)P(x). Then we used even and odd functions, requiring only 2 points for evaluation (the other 2 points will require no computation to be evaluated).

Now, we don’t even need 2 points; we can reduce them to 1 point, with the other point derived without any computation. In fact, we can evaluate ALL possible polynomials (no matter the degree) with a single point with this approach!

Let’s do some examples to make everything crystal clear.

An Example Run

Our polynomial is:

P(x)=3x3+2x2βˆ’4xβˆ’1P(x) = 3x^3 + 2x^2 -4x -1

For each approach, we need to evaluate P(x)P(x) for 4 points: x1x_1, x2x_2, x3x_3, and x4x_4.

1st approach (naive):

In this approach, we can plug any 4 points into P(x)P(x), resulting in (n+1)(n)(n+1)(n) multiplications and (n+1)(nβˆ’1)(n+1)(n-1) additions.

Possible points to evaluate:

This is not efficient…

We went over that already. No need to recompute all the values for 1,2,3,41,2,3,4 for P(x)P(x). Let’s proceed to the next approach.

2nd approach (Even and Odd):

Remembering our polynomial: P(x)=3x3+2x2βˆ’4xβˆ’1P(x) = 3x^3 + 2x^2 -4x -1

We will leverage Even and Odd functions to duplicate computation across positive-negative pairs, doing only half of the computation.

We cannot use the previous points: 1,2,3,4 for this approach, because we need negative-positive pairs:

Recall: computing E(x)E(x) gives us the evaluation for E(βˆ’x)E(-x), and the same goes for O(x)O(x). Plug 1,21,2 into E(x)E(x) and O(x)O(x), and derive the evaluations for βˆ’1-1 and βˆ’2-2 without computation.

Denoting even and odd functions for P(x)P(x), and summarizing optimizations:

E(x)=2x2βˆ’1O(x)=3x2βˆ’4E(x) = 2x^2 -1 \newline O(x) = 3x^2 -4 P(x)=E(x)+xO(x)P(βˆ’x)=E(x)βˆ’xO(x)P(x) = E(x) + xO(x) \newline P(-x) = E(x) - xO(x)

Plugging our 4 points:

We get:

Considering x1x_1 and x2x_2 are positive-negative pairs, and the same goes for x3x_3 and x4x_4, we can now take advantage of the optimization:

So, we only compute E(x1)E(x_1), E(x3)E(x_3), O(x1)O(x_1), and O(x3)O(x_3). No need to compute E(x2)E(x_2), E(x4)E(x_4), O(x2)O(x_2), and O(x4)O(x_4). This saves us half the computations!

3rd approach (Divide and Conquer)

One might call this approach recursive even and odd.

Remembering our polynomial: P(x)=3x3+2x2βˆ’4xβˆ’1P(x) = 3x^3 + 2x^2 -4x -1

We cannot use the previous points: 1,-1,2,-2 for this approach, because we need negative-positive pairs also in x2x^2 space:

We have: P(x)=E(x)+xO(x)P(x) = E(x) + xO(x)

E(x)=2x2βˆ’1O(x)=3x2βˆ’4E(x) = 2x^2 -1 \newline O(x) = 3x^2 -4

We have to evaluate P(x)P(x) for 4 points:

Considering x1x_1 and x2x_2 are positive-negative pairs (in x1x^1 space), and the same goes for x3x_3 and x4x_4, we can now take advantage of the optimization:

So, we only compute E(x1)E(x_1), E(x3)E(x_3), O(x1)O(x_1), and O(x3)O(x_3). No need to compute E(x2)E(x_2), E(x4)E(x_4), O(x2)O(x_2), and O(x4)O(x_4), saving us half the computations!


E(x)=EE+x2EOO(x)=OE+x2OOE(x) = EE + x^2EO \newline O(x) = OE + x^2OO


We can expand our equations to this:

Considering x1x_1 and x3x_3 are positive-negative pairs (in x2x^2 space), we can now take advantage of an additional optimization (replace every x32x_3^2 with x12x_1^2):

So, let’s replace x3x_3 with x1x_1 for those:

We should compute only x12EOx_1^2EO and x12OOx_1^2OO. No need to compute x32EOx_3^2EO and x32OOx_3^2OO.

Generalizing the solution: Roots of Unity

You might have noticed that: 1,-1,i,-i, these are all solutions to the 4th root of 1. And this is no coincidence. We needed 4 points, and the most clever points to choose from, were the the 4th roots of 1.

If we are to generalize this, by using the roots of 1, we can have 2, 4, 8, 16, … as many roots as we like. And these roots will satisfy the properties we require.

These points (roots) do have a special name: Roots of Unity. These are just equally spaced points on the unit circle.

Powers of i, -i, -1, and 1 are periodic, fitting the circular nature. Their powers repeat as they move along the edge of the circle, creating periodicity.

Who would have thought that circles and periods could assist us in evaluating polynomials!

Look at our root of unity formula:

Ο‰=e2Ο€in\omega = e^{\frac{2\pi i}{n}}

Looks familiar, doesn’t it?

Now, let’s recall our DFT formula for polynomials (the same as waves but with changed letters for clarity):

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

And recall:

Ο‰Nk=x=eβˆ’ik2Ο€/N\omega_N^k = x = e^{-ik2\pi/N}

Replace x:

P(Ο‰Nk)=βˆ‘n=0Nβˆ’1anΟ‰NknP(\omega_N^k) = \sum_{n=0}^{N-1}a_n\omega_N^{kn}

See the resemblance? It is the same formula!

That’s it! This is how we efficiently transform from coefficient form to point-value form. For the reverse direction, apply the inverse DFT (which we discovered).

Here is a video with an FFT example. I’ll provide one myself below with more explanations.

Wrapping Everything Back Together

Our formula is equal to:

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

To compute this formula more efficiently, we pick roots of unity for the x values (as given below):

P(Ο‰Nk)=βˆ‘n=0Nβˆ’1anΟ‰NknP(\omega_N^k) = \sum_{n=0}^{N-1}a_n\omega_N^{kn}

Now, for a degree 3 polynomial, we pick the smallest power of 2 greater than 3:

3<223 < 2^2

This equation tells us we need at least 4 points. So, we will do 4 evaluations (for each root of unity) for each root of unity:

P(Ο‰41)=βˆ‘n=03anΟ‰41nP(\omega_4^1) = \sum_{n=0}^{3}a_n\omega_4^{1n} P(Ο‰42)=βˆ‘n=03anΟ‰42nP(\omega_4^2) = \sum_{n=0}^{3}a_n\omega_4^{2n} P(Ο‰43)=βˆ‘n=03anΟ‰43nP(\omega_4^3) = \sum_{n=0}^{3}a_n\omega_4^{3n} P(Ο‰44)=βˆ‘n=03anΟ‰44nP(\omega_4^4) = \sum_{n=0}^{3}a_n\omega_4^{4n}

Noticing the Efficiency

Remembering our polynomial: P(x)=3x3+2x2βˆ’4xβˆ’1P(x) = 3x^3 + 2x^2 -4x -1

We can now evaluate our polynomial at 4 different roots of unity:

P(1)=EE+EO+OE+OOP(1) = EE + EO + OE + OO P(βˆ’1)=EE+EOβˆ’(OE+OO)P(-1) = EE + EO - (OE + OO) P(i)=EEβˆ’EO+i(OEβˆ’OO)P(i) = EE - EO + i(OE - OO) P(βˆ’i)=EEβˆ’EOβˆ’i(OEβˆ’OO)P(-i) = EE - EO - i(OE - OO)

As you can see, we actually only need to compute the following:

And plugging them back in:

P(1)=1βˆ’1=0P(1) = 1 -1 = 0 P(βˆ’1)=1βˆ’(βˆ’1)=2P(-1) = 1 - (-1) = 2 P(i)=βˆ’3+i(βˆ’7)=βˆ’3βˆ’7iP(i) = -3 + i(-7) = -3 -7i P(βˆ’i)=βˆ’3βˆ’i(βˆ’7)=βˆ’3+7iP(-i) = -3 - i(-7) = -3 +7i

The Code

Here is the python code for FFT for the curious audience (feel free to skip this if you don’t like codes):

import numpy as np
from typing import List, Tuple

def FFT(P:List):
	# P - [p_0, p_1, ... , p_(n-1)] coeff representation
	n = len(P)
	if n == 1:
		return P
	w = np.exp(-2j * np.pi / n) # roots of unity
	P_e, P_o = even(P), odd(P)
	f_e, f_o = FFT(P_e), FFT(P_o)
	y = [0] * n
	n //= 2

	for i in range(n):
		p = pow(w,i)*f_o[i]
		y[i], y[i+n] = f_e[i] + p, f_e[i] - p

	return y

def even(p:List)->List:
	return p[::2]

# n > 1 for sure
def odd(p:List)->List:
	return p[1::2]

Explanation of The Code

This code should make a lot of sense. Let me show:

P_e, P_o = even(P), odd(P)
f_e, f_o = FFT(P_e), FFT(P_o)
p = pow(w,i)*f_o[i]
y[i], y[i+n] = f_e[i] + p, f_e[i] - p

Recall how we represented P(x)P(x) and P(βˆ’x)P(-x)?

For E(x)E(x) and E(βˆ’x)E(-x) we had to go 1 level deeper, and had to use x2x^2

The above code is doing exactly that with the relevant roots of unity raised to its power.

A Question

A good question that you can ask to yourself is: Will it work if we use 2, -2, 2i, -2i instead of 1, -1, i, -i?

And the answer is: yes, but with a twist.

You probably remember our last step:

With 2, -1, i, -i:

For 1, -1, i, -i, it is very easy.

And all we needed to do was compute the below:

With 2, -2, 2i, -2i:

And this will work too! However, why on earth would we prefer extra calculations?

This would add an extra step to the code as well. We will have to compute the powers of 2, and multiply each coefficient with the relevant power of 2 in advance before applying the same algorithm to evaluate the polynomial.

What’s next?

That’s really it for the FFT! Congratulations, you probably possess better understanding of FFT than everyone else who haven’t read this post. And I’m not exaggerating. It took me months to come up with all these simplified intuitions.

Yes, you could have looked at some formulas, expand them, and solve some practice problems with pen&paper, but that would only explain HOW it works, not WHY it works. And according to what I’ve seen on internet till now (2024), most people only know the HOW part.

If you want to learn more, in the next post I’ll explain NTT (Number Theoretic Transform), which is same as FFT, but optimized for computers.

Next Article