Multiplication and Fast Fourier Transforms

Overview

Kent Quanrud develops divide-and-conquer algorithms for integer multiplication, showing how Karatsuba reduces four half-size products to three and improves the running time from O(n²) to O(n^1.585). He then builds the radix-2 Fast Fourier Transform from complex roots of unity and even/odd coefficient splitting, applies it to polynomial multiplication in O(n log n), and closes with Strassen’s seven-product matrix multiplication algorithm and the open goal of reaching O(n²).

Key takeaways

Karatsuba replaces four half-size integer multiplications with three by recovering the combined cross term from (x₁ + x₂)(y₁ + y₂); its O(n^1.585) running time improves on O(n²).
The radix-2 FFT evaluates a polynomial at roots of unity in O(n log n) by splitting coefficients into even and odd indices and exploiting the fact that squaring 2n-th roots yields n-th roots.
Polynomial multiplication becomes pairwise multiplication in the Fourier domain: transform both coefficient arrays, multiply corresponding values, then apply the inverse transform to recover coefficients.
The discrete Fourier transform is reversible: under the lecture’s normalization convention, applying the reversed transform recovers the original coefficients scaled by n.
Strassen’s seven-product block decomposition gives matrix multiplication time O(n^2.807), rather than the O(n³) cost of the standard eight-product block expansion.
All three algorithms gain speed by reducing recursive multiplications through algebraic structure, rather than by making each individual multiplication intrinsically faster.

Chapters

0:00 Why Grade-School Multiplication Takes O(n²)

The standard digit-by-digit method combines each of n input digits with each of n other digits, producing O(n²) work.
The lecture frames the challenge against the intuition that this familiar method must be optimal.
Andrey Kolmogorov is introduced in connection with the historical belief that multiplication required quadratic time.

6:00 Split Each Integer into High and Low Halves

For an n-bit integer, divide the representation into two roughly n/2-bit parts.
Write x = x₁·2^(n/2) + x₂ and y = y₁·2^(n/2) + y₂.
This representation turns the product into high-order, low-order, and cross terms that can be computed recursively.

11:00 Four Recursive Products Still Cost O(n²)

Expanding the split product directly requires x₁y₁, x₁y₂, x₂y₁, and x₂y₂: four multiplications on half-size inputs.
The recurrence is T(n) = 4T(n/2) + O(n), where the extra work handles additions and shifts.
At each recursion level, total work stays proportional to n; across log₂ n levels, the total remains O(n²).

15:00 Karatsuba’s Three-Multiplication Identity

Compute (x₁ + x₂)(y₁ + y₂) to obtain x₁y₁ + x₁y₂ + x₂y₁ + x₂y₂ in one recursive multiplication.
Reuse x₁y₁ and x₂y₂ from the high- and low-order products, then subtract them from the combined product to recover both cross terms together.
Anatoly Karatsuba’s key reduction is three recursive products instead of four.

23:00 Karatsuba’s Recurrence Gives O(n^1.585)

The resulting recurrence is T(n) = 3T(n/2) + O(n).
The recursion tree has about 3^i subproblems of size n/2^i at level i, giving a geometric growth toward the leaves.
The dominant exponent is log₂ 3 ≈ 1.585, so Karatsuba beats the quadratic O(n²) method.

32:00 Complex Numbers and Euler’s Formula

A complex number has the form a + bi, with i² = −1; multiplication follows ordinary distribution with that identity.
Euler’s formula, e^(iθ) = cos θ + i sin θ, maps angles to points on the unit circle.
The circular interpretation of complex exponentials provides the periodic structure used by the Fourier transform.

36:40 Roots of Unity as Equally Spaced Circle Points

An nth root of unity is a complex number whose nth power equals 1.
The values e^(2πik/n), for k = 0 through n−1, give the n equally spaced roots around the unit circle.
For example, i is a fourth root of unity because i⁴ = 1; these roots’ symmetry enables recursive evaluation.

41:40 The Discrete Fourier Transform Evaluates a Polynomial

Treat n complex inputs a₀ through aₙ₋₁ as coefficients of p(z) = Σ aⱼzʲ.
The discrete Fourier transform returns p evaluated at the n roots of unity.
The inverse transform recovers the coefficients from those values, with the lecture’s convention introducing a scale factor of n.

45:30 Use Fourier Values to Multiply Polynomials

Directly computing polynomial-product coefficients uses convolution: each output coefficient sums products whose degrees add to its degree.
For p and q, evaluate both at the roots of unity; at each point, (pq)(ω) = p(ω)q(ω), so the transformed values combine pairwise.
Applying the inverse transform recovers the product coefficients; padding to enough evaluation points prevents the product’s higher degree from being lost.

56:00 Radix-2 FFT Splits Even and Odd Coefficients

Instead of splitting the coefficient array into first and second halves, separate even-indexed coefficients from odd-indexed coefficients.
The even terms depend on powers of ω², which range over the n roots of unity when ω ranges over the 2n roots.
Factor one ω out of the odd terms, apply the same smaller transform, and combine the two recursive results.

1:07:00 The FFT Recurrence Runs in O(n log n)

The radix-2 algorithm makes two recursive transforms on n/2 coefficients and uses O(n) work to combine their results.
Its recurrence, T(n) = 2T(n/2) + O(n), solves to O(n log n).
The speedup depends on the symmetry of roots of unity, not on a general ability to evaluate every polynomial at arbitrary points this quickly.

1:08:30 Naive Block Matrix Multiplication Uses Eight Products

An n×n matrix product computes n² row-column dot products, each with n terms, for O(n³) work.
Partition each matrix into four blocks and apply the usual product rule at the block level.
The direct block expansion requires eight multiplications of matrices of size n/2, plus O(n²) additions.

1:11:30 Strassen Reduces the Block Products from Eight to Seven

Volker Strassen’s 1969 algorithm combines block sums and differences so seven recursive matrix products suffice.
The recurrence becomes T(n) = 7T(n/2) + O(n²), improving on the eight-product decomposition.
The method relies on algebraic reuse among block expressions, much as Karatsuba reuses partial products.

1:13:30 Strassen’s Subcubic Exponent and Faster Matrix Multiplication

The seven-product recurrence yields O(n^(log₂ 7)) time, with log₂ 7 ≈ 2.807, below the classical cubic bound.
Further research has improved the matrix-multiplication exponent through increasingly elaborate algorithms.
The lecture identifies O(n²) as the natural lower target and an unresolved conjectural goal.

1:15:30 A Shared Lesson: Representation Creates Faster Algorithms

Karatsuba, the FFT, and Strassen each expose structure hidden by a direct computation.
Karatsuba reduces recursive products; the FFT exploits roots-of-unity symmetry; Strassen reduces block-matrix products.
Choosing the right representation can make even basic operations such as multiplication admit unexpectedly faster algorithms.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.