Interactive Tutorial

Fast Fourier
Transform Lab

An interactive competitive programming tutorial for the Fast Fourier Transform.

Start LearningView TracePractice
x0x1x2x3x4x5x6x70N/2N−1k

Overview

The Problem

Multiplying Polynomials

Given two polynomials, find their product — a fundamental operation in signal processing, convolution, and competitive programming.

A(x)=1 + 2x + 3x²

B(x)=4 + 5x

C(x)=A(x) · B(x)=4 + 13x + 22x² + 15x³

Each output coefficient is a sum of products:

C[k] = Σ A[i] · B[k-i]

Naive approach requires O(n²) operations

Explore the lab

Everything you need to master the Fast Fourier Transform.

Learn

Interactive visualizations and a written article walking through DFT, the Cooley-Tukey algorithm, and NTT.

Open

Trace

Step through recursive and iterative FFT with live variable inspection and highlighted code.

Open

Practice

Built-in Python/C++ editor, Codeforces problem links, and a live naive-vs-FFT benchmark.

Open

Resources

Competition-ready code templates, key formulas, and common implementation pitfalls.

Open

Assignment mapping

Find the right section for each part of the tutorial.

  • Tutorial

    Read and understand the core concepts.

    LearnOpen

  • Examples

    Walk through examples and traces.

    TraceOpen

  • Practice Problems

    Solve problems and test your skills.

    PracticeOpen

  • Citations

    Cite the tutorial and references.

    CitationsOpen