Pattern Guide
FFT & Polynomial Multiplication
"Multiply polynomials in O(n log n). Convolution. Count pairs summing to k."
Fast Fourier Transform (FFT) multiplies two polynomials of degree n in O(n log n) instead of O(n²). Convert coefficients to point-value form at roots of unity, multiply pointwise, convert back (IFFT). Applications: polynomial multiplication, large number multiplication, counting pairs/triplets with target sum, string pattern matching with wildcards, convolutions in signal processing. NTT (Number Theoretic Transform) is the modular arithmetic version.
Problems you can solve with this pattern
3 problems · click any to start solving
// Complex FFT using JS complex arithmetic
function fft(a, invert) {
const n = a.length;
// Bit-reversal permutation
for (let i = 1, j = 0; i < n; i++) {
let bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) [a[i], a[j]] = [a[j], a[i]];
}
// Butterfly
for (let len = 2; len <= n; len <<= 1) {
const ang = 2 * Math.PI / len * (invert ? -1 : 1);
const [wr, wi] = [Math.cos(ang), Math.sin(ang)];
for (let i = 0; i < n; i += len) {
let [cr, ci] = [1, 0];
for (let j = 0; j < len / 2; j++) {
const [ur, ui] = a[i + j];
const [vr, vi] = a[i + j + len / 2];
const tr = cr * vr - ci * vi, ti = cr * vi + ci * vr;
a[i + j] = [ur + tr, ui + ti];
a[i + j + len / 2] = [ur - tr, ui - ti];
[cr, ci] = [cr * wr - ci * wi, cr * wi + ci * wr];
}
}
}
if (invert) for (let i = 0; i < n; i++) a[i] = [a[i][0] / n, a[i][1] / n];
}
function polyMul(a, b) {
const result = new Array(a.length + b.length - 1).fill(0);
let n = 1;
while (n < a.length + b.length) n <<= 1;
const fa = Array.from({length: n}, (_, i) => [a[i] || 0, 0]);
const fb = Array.from({length: n}, (_, i) => [b[i] || 0, 0]);
fft(fa, false); fft(fb, false);
for (let i = 0; i < n; i++) {
const [ar, ai] = fa[i], [br, bi] = fb[i];
fa[i] = [ar * br - ai * bi, ar * bi + ai * br];
}
fft(fa, true);
for (let i = 0; i < result.length; i++) result[i] = Math.round(fa[i][0]);
return result;
}FFT uses divide and conquer: split polynomial into even/odd-indexed coefficients, evaluate recursively at paired roots of unity (ω and -ω cancel nicely), combine in O(n). Iterative butterfly FFT avoids recursion overhead. For competitive programming: (1) use long double precision for large n, (2) prefer NTT (mod p) to avoid floating point errors, (3) "convolution trick" maps counting problems to polynomial multiplication.
// Complex FFT using JS complex arithmetic
function fft(a, invert) {
const n = a.length;
// Bit-reversal permutation
for (let i = 1, j = 0; i < n; i++) {
let bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) [a[i], a[j]] = [a[j], a[i]];
}
// Butterfly
for (let len = 2; len <= n; len <<= 1) {
const ang = 2 * Math.PI / len * (invert ? -1 : 1);
const [wr, wi] = [Math.cos(ang), Math.sin(ang)];
for (let i = 0; i < n; i += len) {
let [cr, ci] = [1, 0];
for (let j = 0; j < len / 2; j++) {
const [ur, ui] = a[i + j];
const [vr, vi] = a[i + j + len / 2];
const tr = cr * vr - ci * vi, ti = cr * vi + ci * vr;
a[i + j] = [ur + tr, ui + ti];
a[i + j + len / 2] = [ur - tr, ui - ti];
[cr, ci] = [cr * wr - ci * wi, cr * wi + ci * wr];
}
}
}
if (invert) for (let i = 0; i < n; i++) a[i] = [a[i][0] / n, a[i][1] / n];
}
function polyMul(a, b) {
const result = new Array(a.length + b.length - 1).fill(0);
let n = 1;
while (n < a.length + b.length) n <<= 1;
const fa = Array.from({length: n}, (_, i) => [a[i] || 0, 0]);
const fb = Array.from({length: n}, (_, i) => [b[i] || 0, 0]);
fft(fa, false); fft(fb, false);
for (let i = 0; i < n; i++) {
const [ar, ai] = fa[i], [br, bi] = fb[i];
fa[i] = [ar * br - ai * bi, ar * bi + ai * br];
}
fft(fa, true);
for (let i = 0; i < result.length; i++) result[i] = Math.round(fa[i][0]);
return result;
}- Polynomial multiplication: O(n log n) vs O(n²)
- Large number multiplication: treat digits as coefficients
- Counting pairs summing to k: convolve frequency arrays
- String matching with wildcards: model * as 0 frequency
NTT (Number Theoretic Transform): Modular FFT using a prime p where primitive root exists. Avoids floating-point precision errors. Use p = 998244353 (NTT-friendly prime).
JavaScript gotcha: No native complex number support — must implement or use Float64Array for performance. For competitive programming in JS, FFT with plain arrays suffices for n ≤ 10^6.