The site's twelfth Number Theory entry, and the other half of a forward
reference Karatsuba Multiplication left
open in its own closing paragraph: "the fastest practical algorithms multiply via Fast Fourier
Transform-based convolution." Karatsuba speeds up multiplying two numbers by splitting each into
halves and reusing the sum of the halves — still O(n1.585). The
Fast Fourier Transform (FFT) attacks a more general version of the same
underlying problem — multiplying (convolving) two coefficient sequences directly — in
O(n log n), and is exactly the technique real bignum libraries reach for once a
number outgrows the range where even Karatsuba's split-in-half trick is the fastest option.
Multiplying two n-coefficient polynomials the schoolbook way (every coefficient of
one against every coefficient of the other) costs O(n²) multiplications, the
same quadratic wall Karatsuba climbs over for plain integers. The FFT climbs over it for
convolution itself: evaluate both polynomials at n cleverly chosen points,
multiply the values pointwise in O(n), then interpolate back to coefficients —
and the specific choice of points (the complex n-th roots of unity) is what makes
both the evaluation and the interpolation themselves computable in O(n log n) instead
of the O(n²) a naive choice of points would cost.
Enter two small polynomials as comma-separated coefficients, constant term
first (so 1,2,3 means 1 + 2x + 3x²), up to 4 coefficients
each, then press Build. Step through all four phases: a forward FFT of A,
a forward FFT of B (each its own recursion tree — split by index parity, recurse, then
"butterfly"-combine the two halves), a pointwise multiplication of the two point-value arrays,
and an inverse FFT of the product that recovers the final coefficients. The two checkboxes
reproduce real, checked bugs in the inverse step — see Pitfalls.
A polynomial of degree less than n is fully determined either way: by its
n coefficients, or by its value at any n distinct points. That gives a
second route to multiplying two polynomials A and B: evaluate both at
the same n points, multiply the values pointwise, then interpolate the product back
to coefficients — the pointwise step is O(n), but evaluating or interpolating a
degree-n polynomial at n arbitrary points still costs
O(n²) in general, so nothing has been won yet.
The FFT wins by choosing the n points deliberately: the complex n-th
roots of unity, ωnk = e2πik/n for
k = 0..n-1. Split a polynomial's coefficients by index parity,
P(x) = Peven(x²) + x·Podd(x²), where
Peven and Podd are half-size polynomials built from
the even- and odd-indexed coefficients. Squaring an n-th root of unity gives an
(n/2)-th root of unity, and every (n/2)-th root arises from exactly two
of the n starting points (ωnk and
ωnk+n/2 square to the same value, since
ωnk+n/2 = -ωnk) — so
evaluating P at all n roots reduces to evaluating
Peven and Podd at only n/2 points
each, then combining each pair with one multiplication (the "butterfly"):
P(ωk) = Peven(ω2k) +
ωk·Podd(ω2k) and
P(ωk+n/2) = Peven(ω2k) -
ωk·Podd(ω2k). That's the recurrence
T(n) = 2T(n/2) + O(n), which solves to O(n log n) — the exact
recursion tree the demo above steps through, twice (once for A, once for B). Interpolating back is
the identical structure run in reverse: the inverse transform uses the same roots' complex
conjugates (ω-1 in place of ω) and divides the
final result by n once at the end, recovering the coefficients from the pointwise
product of the two forward transforms — the convolution theorem, that pointwise-multiplying
two sequences' transforms is the transform of their convolution.
This is the exact algorithm the demo above steps through (numbers padded with zeros to the
next power of two n, since the recursive even/odd split needs a power-of-two length
at every level):
function nextPow2(n) { let p = 1; while (p < n) p *= 2; return p; }
function cadd(a, b) { return { re: a.re + b.re, im: a.im + b.im }; }
function csub(a, b) { return { re: a.re - b.re, im: a.im - b.im }; }
function cmul(a, b) { return { re: a.re*b.re - a.im*b.im, im: a.re*b.im + a.im*b.re }; }
function fft(a, invert) { // a: array of {re, im}, length a power of two
const n = a.length;
if (n === 1) return [a[0]];
const evens = fft(a.filter((_, i) => i % 2 === 0), invert);
const odds = fft(a.filter((_, i) => i % 2 === 1), invert);
const result = new Array(n);
for (let k = 0; k < n / 2; k++) {
const angle = (invert ? 1 : -1) * 2 * Math.PI * k / n; // conjugate direction -- see Pitfalls
const w = { re: Math.cos(angle), im: Math.sin(angle) };
const t = cmul(w, odds[k]);
result[k] = cadd(evens[k], t);
result[k + n / 2] = csub(evens[k], t);
}
return result;
}
function multiply(aCoeffs, bCoeffs) {
const resultLen = aCoeffs.length + bCoeffs.length - 1;
const n = nextPow2(resultLen);
const A = aCoeffs.map(v => ({ re: v, im: 0 })); while (A.length < n) A.push({ re: 0, im: 0 });
const B = bCoeffs.map(v => ({ re: v, im: 0 })); while (B.length < n) B.push({ re: 0, im: 0 });
const FA = fft(A, false), FB = fft(B, false);
const FC = FA.map((v, i) => cmul(v, FB[i]));
const inv = fft(FC, true);
return inv.slice(0, resultLen).map(v => Math.round(v.re / n)); // divide by n -- see Pitfalls
}Verified against direct convolution exhaustively (every pair of polynomials with 1–3 coefficients each, values -2 to 2, 24,025 combinations, 0 mismatches) and against 8,000 randomized trials spanning every combination of polynomial lengths from 1 to 4 on each side with coefficients -9 to 9, 0 mismatches in both sweeps.
Skipping the division by n after the inverse transform is a checked bug,
and the damage is exact. The first checkbox above reproduces it: every returned
coefficient comes out exactly n× too large, where n is the padded
transform length — not an approximation, confirmed across several different polynomial
shapes and sizes (each one's output matched the true convolution multiplied by that run's own
n, with zero exceptions). On this page's own default, (1+2x+3x²)(4+5x+6x²)
padded to n=8, the correct product is [4, 13, 28, 27, 18]
(4 + 13x + 28x² + 27x³ + 18x⁴); with the division skipped it reports
[32, 104, 224, 216, 144] — every entry exactly 8× too large.
Reusing the forward transform's twiddle direction in the inverse step, instead of
conjugating it, is a checked bug too — and it doesn't just scale the answer, it scrambles
it. The second checkbox computes the "inverse" using the same angle = -2πk/n
the forward pass uses, rather than flipping its sign. Applying the forward transform twice in a
row to any sequence is a known identity: it returns n times that sequence
circularly reversed (index 0 stays put, index k swaps with index
n-k) — and dividing by n still happens in this buggy path, so what
comes out is exactly that reversal, not a scaled reversal. Checked directly on this page's own
default: the correct (zero-padded) product is [4, 13, 28, 27, 18, 0, 0, 0]; the
buggy path returns [4, 0, 0, 0, 18, 27, 28, 13] — position 0 unchanged, position
4 unchanged (its own mirror), and positions 1–3 swapped with 7–5 exactly as the
reversal identity predicts. Across 2,000 randomized trials this disagreed with the correct product
99.9–100% of the time (varies slightly by random seed) — the rare exceptions are cases
where the true zero-padded convolution already happens to be its own circular reversal, mostly
when negative and positive random coefficients cancel out the higher terms to zero by chance, not
a weakness in the check.
O(n log n) complex multiplications, where n is the padded
length (the next power of two at least as large as the combined coefficient count minus one),
against schoolbook convolution's O(n²). That asymptotic win doesn't show up
immediately: on this page's own default (3 coefficients each side, padded to n=8),
the reference implementation above performs 44 complex multiplications (measured
directly from the algorithm, not estimated) against schoolbook's 3×3 =
9 real multiplications — the FFT is worse here, the same small-size
"modest saving" story Karatsuba's own page tells at its own default. Measured across growing
equal-length inputs, the crossover is real and lands between 16 and 32 coefficients per side:
| coefficients per side | FFT complex multiplications | schoolbook real multiplications |
|---|---|---|
| 4 | 44 | 16 |
| 8 | 112 | 64 |
| 16 | 272 | 256 |
| 32 | 640 | 1,024 |
| 64 | 1,472 | 4,096 |
| 128 | 3,328 | 16,384 |
| 256 | 7,424 | 65,536 |
Worth being precise about what's being compared: a complex multiplication itself costs more
than a single real one — four real multiplications done naively, or three using the
identical split-the-work trick Karatsuba's own
page uses to cut a multiplication count from four to three, since
(a+bi)(c+di) = (ac-bd) + (ad+bc)i needs only ac, bd, and
(a+b)(c+d) to recover all three real quantities. So the real wall-clock crossover
sits somewhat to the right of the raw table above, not exactly at 16–32 — but the
asymptotic story is unaffected, and the gap only widens: by 256 coefficients per side, schoolbook
needs almost 9× as many multiplications, not accounting for that per-multiplication
constant at all.
Space: O(n) for the padded coefficient and point-value arrays,
with O(log n) recursion depth, the same shape as Karatsuba's own bound. This is the
technique real bignum libraries (GMP, Python's arbitrary-precision int) reach for
once a number outgrows the range where Karatsuba's O(n1.585) is still the
fastest option — treating the number's digits as polynomial coefficients, multiplying via
this exact evaluate/multiply/interpolate strategy, then resolving carries afterward. Production
implementations use fixed-point number-theoretic transforms over a finite field instead of
floating-point complex numbers, avoiding the rounding this page's own Math.round
depends on, but the recursive structure is identical to what the demo above steps through.
This site's guide, Choosing a Number Theory Algorithm, sets this page and its two siblings aside from the rest of the category — every other Number Theory entry treats a multiplication as a single cheap step, an assumption that stops holding once the numbers run to hundreds of digits. This is the top rung of that four-tier ladder: the one worth its own larger constant factor only once Karatsuba and Toom-Cook have both been outgrown.