Introduction

The Fast Fourier Transform, or FFT, is an efficient way to compute the Discrete Fourier Transform without doing all N^2 pairwise work directly. The key trick is to split the input into smaller transforms, reuse repeated complex factors, and combine the partial results recursively or iteratively.

Start from the Discrete Fourier Transform

For an input sequence x[0], x[1], ..., x[N-1], the Discrete Fourier Transform is:

X[k] = sum over n of x[n] * exp(-2pi i k n / N)

If you compute that formula directly for every k, the work is O(N^2). The FFT reduces that to O(N log N) by exploiting symmetry.

Split Even and Odd Indices

The classic radix-2 Cooley-Tukey FFT assumes N is a power of two. It separates the input into:

• the even-indexed values
• the odd-indexed values

Suppose:

• 'E[k] is the DFT of the even-indexed half'
• 'O[k] is the DFT of the odd-indexed half'

Then the full transform can be rebuilt with:

• 'X[k] = E[k] + W[k] * O[k]'
• 'X[k + N/2] = E[k] - W[k] * O[k]'

where W[k] = exp(-2pi i k / N) is the twiddle factor.

That means one size-N transform becomes two size-N/2 transforms plus a linear-time combination step.

A Recursive Python Implementation

The following implementation shows the algorithm directly.

1import cmath
2
3
4def fft(x):
5    n = len(x)
6    if n == 1:
7        return x
8
9    even = fft(x[0::2])
10    odd = fft(x[1::2])
11
12    result = [0] * n
13    for k in range(n // 2):
14        twiddle = cmath.exp(-2j * cmath.pi * k / n) * odd[k]
15        result[k] = even[k] + twiddle
16        result[k + n // 2] = even[k] - twiddle
17
18    return result
19
20
21samples = [0, 1, 0, -1]
22print(fft(samples))

This code is compact and mathematically faithful. It is good for learning, though production libraries use more optimized iterative implementations.

What the Combination Step Is Doing

The combination step is sometimes called the butterfly operation. For each k, you combine one even-frequency contribution and one odd-frequency contribution.

That is why FFT diagrams are full of crossing butterfly shapes: each stage mixes paired values using additions, subtractions, and twiddle-factor multiplications.

The structure repeats across log2(N) stages, which is where the O(N log N) cost comes from.

Small Worked Intuition

Take N = 4 and input [x0, x1, x2, x3].

Split into:

• even part [x0, x2]
• odd part [x1, x3]

Compute two size-2 transforms, then combine them with twiddle factors. Instead of recomputing every complex exponential from scratch for every output, you reuse the smaller transforms and only pay the extra combination cost once per stage.

That reuse is the whole reason FFT is fast.

Practical Notes

The radix-2 form shown above assumes the input length is a power of two. If it is not, common options are:

• pad with zeros to the next power of two
• use a mixed-radix FFT implementation
• use a library routine that handles general sizes efficiently

In practice, most application code should call a tested library such as NumPy rather than implementing FFT manually.

1import numpy as np
2
3samples = np.array([0, 1, 0, -1], dtype=float)
4print(np.fft.fft(samples))

That is the right choice for numerical work. Writing the algorithm yourself is mainly valuable for learning and debugging.

Common Pitfalls

• Treating FFT as a different transform instead of an efficient way to compute the DFT.
• Forgetting that the simple radix-2 version expects a power-of-two input size.
• Misplacing the sign in the complex exponential and computing the inverse convention by accident.
• Ignoring complex numbers and trying to force everything into real arithmetic too early.
• Reimplementing FFT in performance-critical code when a mature library already exists.

Summary

• The FFT computes the DFT faster by splitting the problem into smaller transforms.
• The classic radix-2 FFT separates even and odd indices recursively.
• Twiddle factors combine the half-sized transforms through butterfly operations.
• The runtime drops from O(N^2) to O(N log N).
• For real applications, use a trusted library; implement it yourself mainly to understand how it works.