Citations
All sources used in building this tutorial — textbooks, online references, and competitive programming resources.
Comprehensive treatments of algorithms, FFT, and polynomial methods.
Cormen, Leiserson, Rivest, Stein
Chapter 30 — Polynomials and the FFT
The definitive algorithms textbook. Chapter 30 ("Polynomials and the FFT") provides a rigorous mathematical derivation of the DFT, the FFT algorithm, and polynomial multiplication. Includes proofs of correctness and complexity analysis.
Antti Laaksonen
Chapter 24 — Polynomial Multiplication
A freely available competitive programming reference. Chapter 24 covers polynomial multiplication via FFT and NTT, with concise implementation-focused explanations targeted at competitive programmers.
High-quality articles and documentation for deeper understanding.
CP-Algorithms contributors
A comprehensive walkthrough of FFT for competitive programming. Covers recursive and iterative Cooley-Tukey implementations, NTT with mod 998244353, and practical tips for precision and performance.
Nayuki Minase
Clean, minimal, and correct FFT implementations in C, C++, Java, JavaScript, Python, and more. Valuable as a correctness reference when debugging your own implementation.
Wikipedia contributors
Covers the history of the FFT (Cooley & Tukey, 1965), the mathematical derivation of the divide-and-conquer recursion, and a description of the butterfly diagram. Good for understanding the algorithm's origins.
Problem sets, templates, and libraries to level up your FFT skills.
jakobkogler (Codeforces)
A highly cited Codeforces blog post that motivates FFT through polynomial multiplication, covers precision issues with floating-point FFT, and introduces NTT as a remedy. Includes multiple worked examples.
matthew99 (Codeforces)
Step-by-step derivation of FFT from the DFT definition, with emphasis on the iterative implementation and bit-reversal permutation. Also covers NTT and gives template code for competitive programming.
KTH Royal Institute of Technology
content/numerical/FastFourierTransform.h
The template library used by KTH's ICPC teams, widely regarded as one of the best-maintained CP code libraries. The FFT and NTT implementations are battle-tested across hundreds of contest problems.
Help improve this lab by suggesting high-quality references and resources for the community.