AntInLoop

Fast Fourier Transform

By @antinloop ยท Published 2025-10-02

The Fast Fourier Transform (FFT): A Digital Superpower

The Fast Fourier Transform (FFT) is one of the most important algorithms in computer science and engineering. It's a remarkably efficient method for computing the Discrete Fourier Transform (DFT), reducing its complexity from a sluggish $O(N^2)$ to a blazingly fast $O(N \log N)$. This speedup unlocks applications in signal processing, image compression, data analysis, and even enables multiplying enormous numbers faster than we learned in school.

At its core, FFT provides a way to switch between two different representations of a sequence of numbers, just like how we can represent light as either a wave or a particle. The magic is that some problems that are hard in one representation become trivial in the other.

-----

The Motivation: Polynomial Multiplication

Let's start with a familiar problem: multiplying two polynomials. A polynomial is defined by its coefficients. For example, $A(x) = 2x^2 + 3x + 1$ has coefficients $[1, 3, 2]$.

$A(x) = a_0 + a_1x + a_2x^2 + ...$

$B(x) = b_0 + b_1x + b_2x^2 + ...$

The "schoolbook" method of multiplying these takes $O(N^2)$ time. If the polynomials have thousands of terms, this becomes very slow.

However, there's another way to represent a polynomial: the point-value form. A polynomial of degree $N-1$ is uniquely defined by its value at $N$ distinct points. For example, we can represent $A(x) = 3x+1$ by its values at $x=0$ and $x=1$, which are $A(0)=1$ and $A(1)=4$.

Now, here's the trick: if we have two polynomials, $A(x)$ and $B(x)$, in point-value form, we can find their product $C(x) = A(x) \cdot B(x)$ in just $O(N)$ time\! We simply multiply their values at each point:

If $A \Rightarrow \{(x_0, y_{A0}), (x_1, y_{A1}), \dots\}$

And $B \Rightarrow \{(x_0, y_{B0}), (x_1, y_{B1}), \dots\}$

Then $C \Rightarrow \{(x_0, y_{A0} \cdot y_{B0}), (x_1, y_{A1} \cdot y_{B1}), \dots\}$

This gives us a new three-step plan for fast multiplication:

1. Evaluation: Convert polynomials $A(x)$ and $B(x)$ from coefficient form to point-value form.

2. Pointwise Multiplication: Create the point-value form of $C(x)$ in $O(N)$ time.

3. Interpolation: Convert $C(x)$ back from point-value form to coefficient form.

Steps 1 and 3 seem hard. How do we choose the points, and how can we do this conversion quickly? This is precisely the problem that the FFT solves.

-----

The Discrete Fourier Transform (DFT) and Roots of Unity

The DFT is the mathematical tool for the "Evaluation" step. It evaluates a polynomial at a specific set of $N$ points: the $N$-th roots of unity.

These are the complex numbers that solve the equation $z^N = 1$. They are given by:

$\omega_N^k = e^{2\pi i k / N} = \cos\left(\frac{2\pi k}{N}\right) + i \sin\left(\frac{2\pi k}{N}\right)$ for $k=0, 1, ..., N-1$.

When plotted on the complex plane, these points are perfectly spaced around the unit circle.

These points aren't chosen randomly; they have special properties that make both the evaluation (DFT) and interpolation (Inverse DFT) very efficient. The DFT of a coefficient vector $[a_0, a_1, ..., a_{N-1}]$ is its value at these points. A naive calculation of this is still $O(N^2)$.

The "Fast" in FFT: Divide and Conquer

The FFT algorithm (specifically, the Cooley-Tukey algorithm) computes the DFT in $O(N \log N)$ time using divide and conquer.

Let's take a polynomial $A(x)$ with $N$ coefficients, where $N$ is a power of 2. We can split it into two smaller polynomials based on its even and odd indexed coefficients:

$A_{even}(y) = a_0 + a_2y + a_4y^2 + ...$

$A_{odd}(y) = a_1 + a_3y + a_5y^2 + ...$

We can then cleverly write $A(x)$ in terms of these subproblems:

$A(x) = A_{even}(x^2) + x \cdot A_{odd}(x^2)$

Here's the key insight: when we evaluate $A(x)$ at the roots of unity $\omega_N^k$, we find that we can reuse computations. The values needed for the first half of the points are almost identical to the values needed for the second half. This is called the butterfly operation:

$A(\omega_N^k) = A_{even}(\omega_{N/2}^k) + \omega_N^k \cdot A_{odd}(\omega_{N/2}^k)$

$A(\omega_N^{k+N/2}) = A_{even}(\omega_{N/2}^k) - \omega_N^k \cdot A_{odd}(\omega_{N/2}^k)$

Notice we only need to compute the subproblems $A_{even}$ and $A_{odd}$ once for each pair of points. This structure reduces a problem of size $N$ into two problems of size $N/2$, giving us the classic $T(N) = 2T(N/2) + O(N)$ recurrence, which solves to $O(N \log N)$.

The Inverse FFT (for interpolation) is almost identical to the forward FFT. We just need to use the conjugate of the roots of unity and scale the final result by $1/N$.

-----

C++ Implementation

Here is a complete, iterative C++ implementation of FFT, which is faster in practice than the recursive version. This code can be used for fast polynomial multiplication.

#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
#include <algorithm>

// Use a type alias for complex numbers for readability
using cd = std::complex<double>;
const double PI = acos(-1);

// This function performs the bit-reversal permutation
void bit_reverse(std::vector<cd>& a) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
        if (i < j)
            std::swap(a[i], a[j]);
    }
}

// The core FFT function
// 'invert' flag determines if it's forward (FFT) or inverse (IFFT)
void fft(std::vector<cd>& a, bool invert) {
    int n = a.size();

    // The iterative FFT starts with the coefficients in bit-reversed order
    bit_reverse(a);

    // Bottom-up iteration
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i + j];
                cd v = a[i + j + len / 2] * w;
                // The butterfly operation
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }

    // If it's an inverse FFT, scale the result by 1/n
    if (invert) {
        for (cd& x : a) {
            x /= n;
        }
    }
}

// A helper function to multiply two polynomials (represented by coefficient vectors)
std::vector<long long> multiply(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    
    // 1. Pad with zeros to the next power of 2
    int n = 1;
    while (n < a.size() + b.size()) 
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    // 2. Perform forward FFT on both
    fft(fa, false);
    fft(fb, false);

    // 3. Perform pointwise multiplication
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];

    // 4. Perform inverse FFT on the result
    fft(fa, true);

    // 5. Convert back to integer coefficients
    std::vector<long long> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
        
    return result;
}

int main() {
    // Example: Multiply A(x) = 1 + 2x and B(x) = 3 + 4x
    // Expected result: C(x) = 3 + 10x + 8x^2
    // Coefficients: A = {1, 2}, B = {3, 4}
    std::vector<int> a = {1, 2};
    std::vector<int> b = {3, 4};

    std::vector<long long> result = multiply(a, b);

    std::cout << "Resulting polynomial coefficients: ";
    for (long long c : result) {
        // We might have trailing zeros due to padding
        if (c == 0 && result.back() == 0) continue; 
        std::cout << c << " ";
    }
    std::cout << std::endl; // Output: 3 10 8

    return 0;
}

Conclusion

The Fast Fourier Transform is a testament to algorithmic elegance. By changing the representation of a problem from coefficients to points, it turns a difficult $O(N^2)$ multiplication into a simple $O(N)$ task. The FFT provides the efficient engine for switching between these worlds, making it a cornerstone of modern computing. It's a beautiful example of how a deep mathematical insight can lead to profound practical results.