FFT & NTT
Multiply two polynomials of degree one million. The school method multiplies every coefficient of the first by every coefficient of the second: multiplications, about 17 minutes at a billion per second. The Fast Fourier Transform (FFT) does it in under simple butterfly steps — a fraction of a second in C++. The same trick multiplies million-digit integers, counts how many pairs in an array sum to each value, matches strings with wildcards, and underlies every MP3, JPEG, Wi-Fi radio and MRI scanner.
The core idea fits in one sentence: a polynomial can be described by its coefficients or by its values at enough points, multiplying is easy in the value form, and the FFT converts between the two forms in by choosing very special points — the complex roots of unity. The Number Theoretic Transform (NTT) does the same with integers modulo a prime, so there is no rounding at all.
You will learn to:
- see multiplication as convolution and why the naive method is ,
- switch between coefficient and point-value representations,
- understand roots of unity and why they make evaluation fast,
- derive the Cooley–Tukey FFT recursively, then write the iterative in-place version with bit reversal,
- invert it with almost the same code,
- know when doubles are precise enough, and what to do when they are not,
- use the NTT modulo 998244353 for exact answers,
- recognise convolution in disguise: big integers, pair sums, wildcard matching, subset sums, and the Walsh–Hadamard transform for XOR.
This lesson assumes Divide & Conquer (recurrences, Karatsuba), complex numbers at the level of (recapped below), and modular inverses (Modular Arithmetic). Linear Algebra helps for one paragraph: the DFT is a matrix.
Why this exists
The Fourier transform is two centuries old (Fourier, heat equation, 1807–1822). The fast algorithm for the discrete version was published by James Cooley and John Tukey in 1965 ("An algorithm for the machine calculation of complex Fourier series", Mathematics of Computation 19(90)). Tukey's motivation reportedly included detecting Soviet nuclear tests from seismometer data; Richard Garwin at IBM pushed for the implementation. Only later did Heideman, Johnson and Burrus (1984) find that Gauss had used the same divide-and-conquer idea in unpublished notes around 1805, to interpolate asteroid orbits — before Fourier's own work.
Why it matters: the Discrete Fourier Transform (DFT) of samples costs by its definition. The FFT computes the same numbers in . For that is the difference between and operations — a factor of 50,000. It turned spectral analysis from a mainframe job into something every phone does continuously. Gilbert Strang called it "the most important numerical algorithm of our lifetime" (American Scientist, 1994).
For algorithm designers the FFT matters for a different reason: convolution. Many counting problems have the shape "for each , sum over all ". That is exactly polynomial multiplication, and the FFT makes it .
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "multiply two polynomials", degree a few thousand | FFT or NTT, |
| "for every , " | Convolution = polynomial product |
| "number of pairs with sum exactly , for every ", values | Frequency array squared by FFT |
| "multiply two numbers with + digits" | FFT on digits plus carries |
| "answer modulo 998244353" and a product / power of polynomials | NTT |
"match a pattern with ? wildcards against a text" | Three convolutions: |
| "for every shift, count positions where two strings agree" | One convolution per letter, or one with complex roots |
| "number of subsets with each possible sum", sums | Product of , divide and conquer with NTT |
| "for every , pairs with " | Walsh–Hadamard transform |
| "" or "" | Not FFT: SOS DP (zeta/Möbius) |
| sizes up to ~2,000 | Naive is simpler and fast enough |
| "frequency", "spectrum", "filter", "signal" | The FFT in its original habitat |
The meta-trigger: an index that adds up (). When the combining rule is addition of indices, it is a convolution, and FFT/NTT applies. When it is XOR of indices, use Walsh–Hadamard; OR/AND, use SOS.
Intuition & first principles
Multiplication is convolution
Write as the coefficient list [1, 2, 3] (lowest degree first) and as [4, 5]. Their product has coefficients
So , , , : . This operation on lists is called the convolution of and , written . With two lists of length , it costs multiplications.
Integer multiplication is the same thing with carries: is the polynomial product with , digits reversed: [3, 2, 1], [5, 4].
Divide & Conquer already showed one improvement: Karatsuba splits each polynomial in half and gets away with 3 half-size products instead of 4, for . The FFT goes all the way to by changing the representation instead of being clever with splitting.
Two ways to describe a polynomial
A polynomial of degree less than is pinned down by coefficients. It is also pinned down by its values at any distinct points: two points determine a line, three determine a parabola, and in general there is exactly one polynomial of degree through given points (Lagrange interpolation; in linear-algebra terms, the Vandermonde matrix of distinct points is invertible).
| Representation | Store | Add two polys | Multiply two polys | Evaluate at a new |
|---|---|---|---|---|
| Coefficients | (Horner) | |||
| Point values | (interpolate) |
In point-value form, multiplication is trivial: . One catch: has degree up to , so we need at least points. That is why the code pads both inputs to a size len(a) + len(b) - 1.
That suggests a three-step plan:
flowchart LR
A["coefficients of A and B"] -->|"evaluate at n points"| V["values A(x_k), B(x_k)"]
V -->|"multiply pointwise, O(n)"| W["values C(x_k)"]
W -->|"interpolate"| C["coefficients of C"]
With arbitrary points, evaluating is per point, total, and interpolation is no better: no gain. The FFT wins by picking points so special that evaluation at all of them costs , and interpolation turns out to be the same algorithm run backwards.
Roots of unity
A complex number is a point in the plane. Multiplying complex numbers multiplies their lengths and adds their angles. The number has length 1 and angle .
The -th roots of unity are the complex numbers with . They sit evenly spaced on the unit circle:
where is the principal -th root. For : , and the four roots are . For they are the eight compass directions.
Three facts make the FFT work:
- Periodicity: .
- Halving: . Squaring the roots of unity gives the roots of unity, each twice. Squaring doubles the angle, and the circle wraps around.
- Symmetry: . Opposite points on the circle are negatives.
A tiny example you can check by hand
Multiply by using the four points :
Interpolating from the last column (with the inverse transform, defined below) gives back [4, 13, 22, 15] — the product computed earlier. The FFT is the fast way to fill the middle columns and to undo the last one.
The DFT is a matrix
Evaluating (with coefficients ) at all roots of unity is the Discrete Fourier Transform:
As a matrix–vector product, with (an Vandermonde matrix). Computed directly, that is . Its inverse is remarkably simple: , where the bar means complex conjugate (). In words: the inverse DFT is the DFT with in place of , divided by . We prove it in Correctness.
Sign conventions
This lesson's forward transform uses (as in CLRS and cp-algorithms). Signal-processing libraries such as NumPy use for the forward direction, which conjugates every output. For multiplication it does not matter, as long as the inverse uses the opposite sign.
Mechanics
1. Cooley–Tukey, recursively
Split into even- and odd-indexed coefficients:
Then . Check with : , , and ✔.
Evaluate at . By the halving fact, : the two halves only need to be evaluated at the roots of unity of order — two DFTs of size . Then, using symmetry for the second half of the outputs, for :
where and are the DFTs of the even and odd halves. This pair of formulas is the butterfly: two inputs, one multiplication by a twiddle factor , one addition and one subtraction.
import cmath
def fft_recursive(a):
"""DFT of a (len a power of two) with omega = e^(2*pi*i/n)."""
n = len(a)
if n == 1:
return a[:]
even = fft_recursive(a[0::2])
odd = fft_recursive(a[1::2])
out = [0j] * n
for k in range(n // 2):
t = cmath.exp(2j * cmath.pi * k / n) * odd[k] # twiddle * odd part
out[k] = even[k] + t
out[k + n // 2] = even[k] - t
return out
res = fft_recursive([1, 2, 3, 4])
assert all(abs(x - y) < 1e-9 for x, y in zip(res, [10, -2 - 2j, -2, -2 + 2j]))
The recurrence is , so by the Master theorem — the same as merge sort.
flowchart TD
R["DFT of a0 a1 a2 a3"] --> E["DFT of a0 a2 (even)"]
R --> O["DFT of a1 a3 (odd)"]
E --> E0["a0"]
E --> E1["a2"]
O --> O0["a1"]
O --> O1["a3"]
Read the leaves left to right: . That order is the key to the iterative version.
2. Bit reversal: where the leaves end up
Write each index in binary with bits. After all the even/odd splits, the coefficient at position of the leaves is , where reverses the bits. Why: the first split sorts by the lowest bit (even first), the next by the second-lowest, and so on — so the lowest bit becomes the most significant in the final order.
| Position | binary | reversed | coefficient |
|---|---|---|---|
| 0 | 000 | 000 | |
| 1 | 001 | 100 | |
| 2 | 010 | 010 | |
| 3 | 011 | 110 | |
| 4 | 100 | 001 | |
| 5 | 101 | 101 | |
| 6 | 110 | 011 | |
| 7 | 111 | 111 |
So for the leaf order is . Bit reversal is its own inverse, so one pass of swaps (if i < rev(i): swap) does the permutation in place. The code maintains j = rev(i) incrementally by "adding 1 from the top": clear the leading 1-bits of j from the top down, then set the first 0-bit.
3. The iterative FFT
With the leaves in bit-reversed order, the recursion can run bottom-up with no recursion and no extra arrays:
- Bit-reverse permute the array.
- For
length= 2, 4, 8, …, : for each block oflengthconsecutive entries, combine its two halves with butterflies using the twiddles , .
flowchart LR
subgraph s0["bit-reversed input"]
x0["1 (a0)"]
x1["3 (a2)"]
x2["2 (a1)"]
x3["4 (a3)"]
end
subgraph s1["after length 2"]
y0["4"]
y1["-2"]
y2["6"]
y3["-2"]
end
subgraph s2["after length 4"]
z0["10"]
z1["-2-2i"]
z2["-2"]
z3["-2+2i"]
end
x0 --> y0
x1 --> y0
x0 --> y1
x1 --> y1
x2 --> y2
x3 --> y2
x2 --> y3
x3 --> y3
y0 --> z0
y2 --> z0
y0 --> z2
y2 --> z2
y1 --> z1
y3 --> z1
y1 --> z3
y3 --> z3
4. Trace: a 4-point FFT of [1, 2, 3, 4]
, , . Each butterfly takes (top) and = bottom × twiddle and writes , .
| Stage | Pair (positions) | twiddle | writes , | Array after the stage | ||
|---|---|---|---|---|---|---|
| bit reversal | swap 1 ↔ 2 | [1, 3, 2, 4] | ||||
| length 2 | (0, 1) | 1 | 3 | 4, −2 | ||
| length 2 | (2, 3) | 2 | 4 | 6, −2 | [4, -2, 6, -2] | |
| length 4 | (0, 2) | 4 | 6 | 10, −2 | ||
| length 4 | (1, 3) | −2 | , | [10, -2-2i, -2, -2+2i] |
Check against the definition: ✔; ✔. The trace was produced by instrumenting the code.
5. The inverse FFT
Run the same loop with (that is, angle ) and divide every output by . In code this is one boolean flag. To multiply: forward-transform both padded inputs, multiply pointwise, inverse-transform, round to the nearest integer.
6. The NTT: the same algorithm, exactly, modulo a prime
The FFT needs only three things from : , for (so it is a primitive -th root), and the halving and symmetry facts that follow. The integers modulo a prime can supply such an whenever divides .
Why: the nonzero residues mod form a cyclic group of order : there is a primitive root whose powers hit every nonzero residue. Then has order exactly .
The favourite prime is
Since divides , every power-of-two size up to has a root of unity. A primitive root is . That is easy to verify: is a primitive root iff for every prime dividing . Here , and the values , , mod are (that is, ), and — none is 1. (Also checked: is prime by trial division, and = 15311432 is a primitive -th root: its -th power is .)
A tiny NTT you can do by hand uses , primitive root 3, : . Powers of 13: — the mod-17 analogues of (indeed ). The same [1, 2, 3, 4]:
| Stage | Pair | twiddle | , (mod 17) | Array | ||
|---|---|---|---|---|---|---|
| bit reversal | [1, 3, 2, 4] | |||||
| length 2 | (0, 1) | 1 | 1 | 3 | 4, 15 | |
| length 2 | (2, 3) | 2 | 1 | 4 | 6, 15 | [4, 15, 6, 15] |
| length 4 | (0, 2) | 4 | 1 | 6 | 10, 15 | |
| length 4 | (1, 3) | 15 | 13 | 6, 7 | [10, 6, 15, 7] |
Direct evaluation agrees: .
The NTT gives the product modulo . If the true coefficients are below (non-negative), that is the answer. If the problem wants the answer mod 998244353 anyway, it is exactly the answer. If the true coefficients can exceed , see the precision section.
Other NTT-friendly primes: (root 3), (root 3), (root 11). Three of them plus the Chinese Remainder Theorem reconstruct any coefficient below their product, about for 998244353, 469762049 and 167772161.
Precision: when doubles are enough
Each FFT stage adds rounding error, roughly proportional to the size of the values times (double precision), and there are stages. The output coefficients are integers, so we round at the end. Rounding is correct as long as the accumulated error stays below 0.5.
A rule of thumb: the largest output coefficient must stay well below , since a double cannot even represent integers exactly beyond that — and in practice you want a margin of a few bits for the error. To see it, the C++ code below was run on random inputs of two sizes and four coefficient ranges, and compared with an exact __int128 naive product:
| Length of each input | Coefficients up to | Largest output coefficient | Max error before rounding | Wrong coefficients |
|---|---|---|---|---|
| 1,000 | 0 | |||
| 1,000 | 0.094 | 0 | ||
| 32,768 | 0 | |||
| 32,768 | 0.047 | 0 | ||
| 32,768 | 5 | 50,682 of 65,535 |
At (close to ) the answer is garbage. Notice how fast the error grows with the coefficient bound: 0.047 at , 5 at — ten times bigger inputs, a hundred times bigger error, because the outputs are products.
Things that help, from cheap to thorough:
- Precompute roots directly with
cos/sinof , as the code below does. Computing by repeated multiplication (w *= wlen) accumulates error along each block and is a common source of wrong answers on large inputs. - Round, do not truncate.
(long)xturns 14.9999999 into 14. Useround/llround/Math.round. - Split coefficients. To multiply polynomials with coefficients mod (products up to , hopeless in doubles), write each coefficient as with both halves below . Then four products , , , have coefficients at most — about for , safely exact — and you recombine mod . Tuned versions pack the halves into the real and imaginary parts and need only 2–3 FFTs instead of 8 (cp-algorithms, "Fast Fourier transform", section on arbitrary modulus).
- Use the NTT when the answer is wanted mod an NTT prime, or with three primes and CRT for exact big results.
- Use
long doublein C++ on x86 (64-bit mantissa) for a few more bits, at a speed cost.
The split version, in Python, reusing multiply_fft from the implementation below:
def multiply_mod_any(p, q, m):
"""p * q with coefficients mod an arbitrary m < 2^30, using doubles safely:
split every coefficient into 15-bit halves so each convolution stays small."""
S = 1 << 15
p_hi, p_lo = [x // S for x in p], [x % S for x in p]
q_hi, q_lo = [x // S for x in q], [x % S for x in q]
hh = multiply_fft(p_hi, q_hi) # each entry <= n * 2^30: exact after rounding
hl = multiply_fft(p_hi, q_lo)
lh = multiply_fft(p_lo, q_hi)
ll = multiply_fft(p_lo, q_lo)
return [((hh[i] % m) * (S * S % m) + ((hl[i] + lh[i]) % m) * S + ll[i]) % m
for i in range(len(hh))]
import random
rng = random.Random(5)
M = 10**9 + 7
p = [rng.randrange(M) for _ in range(300)]
q = [rng.randrange(M) for _ in range(300)]
assert multiply_mod_any(p, q, M) == [x % M for x in multiply_naive(p, q)]
The ladder: brute force → better → optimal
Problem: multiply two polynomials with coefficients each.
Rung 1: schoolbook,
Two nested loops. : multiplications, ~10 seconds in C++. For it is the right choice: no setup, exact, cache-friendly.
Rung 2: Karatsuba,
Split each input into halves: . Three products , and give all four cross terms. Exact over the integers, no special numbers required. For : about operations. GMP uses Karatsuba and Toom–Cook in the middle range of sizes. See Divide & Conquer.
Rung 3: FFT, with doubles
Pad to a power of two , three transforms of size , pointwise products. For : , about butterflies. Fast, but subject to the precision limits above.
Rung 4: NTT, , exact mod
Same structure with modular arithmetic. Slower per operation than doubles (a modular multiplication is a 64-bit multiply plus a reduction; Montgomery or Barrett reduction speed it up), but exact. The standard choice in contests when the answer is wanted mod 998244353.
| Method | Time | Exact? | Good for |
|---|---|---|---|
| Schoolbook | yes | ~2,000 | |
| Karatsuba | yes | medium , arbitrary rings | |
| Toom–Cook 3 | yes | big-integer libraries, medium-large | |
| FFT (doubles) | if outputs | real/complex signals, small integer coefficients | |
| FFT with 15-bit split | , ~2–4× slower | yes, for any modulus | "answer mod " |
| NTT mod 998244353 | yes, mod | contest answers mod NTT primes | |
| NTT with 3 primes + CRT | , 3× slower | yes, up to | exact large coefficients, arbitrary modulus |
| Schönhage–Strassen | bit operations | yes | huge integers (GMP, beyond tens of thousands of words) |
Correctness
The butterfly identity. For , is just at , and (the halving fact: ). For : (same evaluation point for the halves) and . So both outputs use the same , , with opposite signs on the twiddle term. Induction on completes the proof that the recursive FFT computes the DFT.
The iterative version computes the same thing. After bit reversal, positions for every block of size hold exactly the inputs of one size- subproblem in the recursion tree, and after the stage with length they hold that subproblem's DFT. Induction on , using the butterfly identity.
The inverse. Let and . Then
because while for (primitivity). So . This argument uses only " is a primitive -th root of unity" and " is invertible", which is why it works unchanged mod .
The convolution theorem. means for every , i.e. pointwise, as long as . If , the powers and evaluate the same at roots of unity, and coefficients wrap around: you get the cyclic convolution, . That is why we pad.
Complexity
| Quantity | Value |
|---|---|
| FFT / NTT of size | butterflies: time |
| Multiply two polynomials of sizes , | 3 transforms of size = next power of two : |
| Space | ; the iterative transform is in place |
| Padding overhead | , so at most about 2× wasted |
| Best / average / worst | identical: the FFT does not look at the data |
For : , butterflies; well under a second in C++ or Java, several seconds in pure Python (use NumPy's numpy.fft in Python for real work).
Implementation
Each block has (1) an iterative complex FFT with bit reversal and precomputed roots, and multiply_fft for integer polynomials; (2) an iterative NTT modulo 998244353 with primitive root 3, and multiply_ntt. Each main checks the example from this lesson and then compares both multiplications with the naive product on 200 random pairs of polynomials (lengths 1–60, coefficients in ), plus NTT products with coefficients up to . All four printed all FFT/NTT tests passed.
The TypeScript NTT needs care: residues are below , so a product needs 60 bits, and JavaScript numbers are exact only to . mulMod splits one factor into 15-bit halves (the same idea as the precision section, in miniature).
import cmath
import random
from typing import List
# ---------- 1. Iterative complex FFT ----------
def fft(a: List[complex], invert: bool) -> None:
"""In-place FFT of a (len(a) a power of two). invert=True computes the inverse."""
n = len(a)
j = 0
for i in range(1, n): # bit-reversal permutation
bit = n >> 1
while j & bit:
j ^= bit
bit >>= 1
j ^= bit
if i < j:
a[i], a[j] = a[j], a[i]
sign = -1 if invert else 1
# roots[k] = e^(sign·2πik/n), each computed directly (no error build-up from w *= wlen)
roots = [cmath.exp(sign * 2j * cmath.pi * k / n) for k in range(n // 2)]
length = 2
while length <= n:
half, step = length // 2, n // length
for start in range(0, n, length):
for k in range(half): # butterfly
u = a[start + k]
v = a[start + k + half] * roots[k * step]
a[start + k] = u + v
a[start + k + half] = u - v
length <<= 1
if invert:
for i in range(n):
a[i] /= n
def multiply_fft(p: List[int], q: List[int]) -> List[int]:
"""Product of two integer polynomials (coefficient lists, lowest degree first)."""
if not p or not q:
return []
need = len(p) + len(q) - 1
n = 1
while n < need:
n <<= 1
fa = [complex(x) for x in p] + [0j] * (n - len(p))
fb = [complex(x) for x in q] + [0j] * (n - len(q))
fft(fa, False)
fft(fb, False)
for i in range(n):
fa[i] *= fb[i] # pointwise product of the values
fft(fa, True)
return [round(fa[i].real) for i in range(need)] # round: results are integers
# ---------- 2. NTT modulo 998244353 = 119 * 2^23 + 1 ----------
MOD = 998244353
G = 3 # primitive root of MOD
def ntt(a: List[int], invert: bool) -> None:
n = len(a)
j = 0
for i in range(1, n):
bit = n >> 1
while j & bit:
j ^= bit
bit >>= 1
j ^= bit
if i < j:
a[i], a[j] = a[j], a[i]
length = 2
while length <= n:
w = pow(G, (MOD - 1) // length, MOD) # a primitive length-th root of unity
if invert:
w = pow(w, MOD - 2, MOD)
half = length // 2
for start in range(0, n, length):
wk = 1
for k in range(half):
u = a[start + k]
v = a[start + k + half] * wk % MOD
a[start + k] = (u + v) % MOD
a[start + k + half] = (u - v) % MOD
wk = wk * w % MOD
length <<= 1
if invert:
n_inv = pow(n, MOD - 2, MOD)
for i in range(n):
a[i] = a[i] * n_inv % MOD
def multiply_ntt(p: List[int], q: List[int]) -> List[int]:
"""Product modulo 998244353. Needs len(p) + len(q) - 1 <= 2^23."""
if not p or not q:
return []
need = len(p) + len(q) - 1
n = 1
while n < need:
n <<= 1
fa = [x % MOD for x in p] + [0] * (n - len(p))
fb = [x % MOD for x in q] + [0] * (n - len(q))
ntt(fa, False)
ntt(fb, False)
fa = [x * y % MOD for x, y in zip(fa, fb)]
ntt(fa, True)
return fa[:need]
def multiply_naive(p: List[int], q: List[int]) -> List[int]:
if not p or not q:
return []
r = [0] * (len(p) + len(q) - 1)
for i, x in enumerate(p):
for j, y in enumerate(q):
r[i + j] += x * y
return r
if __name__ == "__main__":
assert multiply_fft([1, 2, 3], [4, 5]) == [4, 13, 22, 15]
assert multiply_ntt([1, 2, 3], [4, 5]) == [4, 13, 22, 15]
a = [1, 2, 3, 4]
fft_a = [complex(x) for x in a]
fft(fft_a, False)
assert all(abs(x - y) < 1e-9 for x, y in zip(fft_a, [10, -2 - 2j, -2, -2 + 2j]))
rng = random.Random(2026)
for _ in range(200):
p = [rng.randint(-1000, 1000) for _ in range(rng.randint(1, 60))]
q = [rng.randint(-1000, 1000) for _ in range(rng.randint(1, 60))]
exact = multiply_naive(p, q)
assert multiply_fft(p, q) == exact
assert multiply_ntt(p, q) == [x % MOD for x in exact]
big_p = [rng.randrange(MOD) for _ in range(len(p))]
assert multiply_ntt(big_p, q) == [x % MOD for x in multiply_naive(big_p, q)]
print("all FFT/NTT tests passed")
import java.util.*;
public class Main {
// ---------- 1. Iterative complex FFT (real and imaginary parts in two arrays) ----------
static void fft(double[] re, double[] im, boolean invert) {
int n = re.length;
for (int i = 1, j = 0; i < n; i++) { // bit-reversal permutation
int bit = n >> 1;
for (; (j & bit) != 0; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) {
double t = re[i]; re[i] = re[j]; re[j] = t;
t = im[i]; im[i] = im[j]; im[j] = t;
}
}
double sign = invert ? -1 : 1;
double[] cosT = new double[n / 2], sinT = new double[n / 2];
for (int k = 0; k < n / 2; k++) { // roots computed directly, not by repeated products
double ang = sign * 2 * Math.PI * k / n;
cosT[k] = Math.cos(ang);
sinT[k] = Math.sin(ang);
}
for (int len = 2; len <= n; len <<= 1) {
int half = len / 2, step = n / len;
for (int start = 0; start < n; start += len) {
for (int k = 0; k < half; k++) {
int i = start + k, j = i + half;
double wr = cosT[k * step], wi = sinT[k * step];
double vr = re[j] * wr - im[j] * wi; // v = a[j] * w
double vi = re[j] * wi + im[j] * wr;
re[j] = re[i] - vr; im[j] = im[i] - vi;
re[i] += vr; im[i] += vi;
}
}
}
if (invert) for (int i = 0; i < n; i++) { re[i] /= n; im[i] /= n; }
}
static long[] multiplyFft(long[] p, long[] q) {
if (p.length == 0 || q.length == 0) return new long[0];
int need = p.length + q.length - 1, n = 1;
while (n < need) n <<= 1;
double[] ar = new double[n], ai = new double[n], br = new double[n], bi = new double[n];
for (int i = 0; i < p.length; i++) ar[i] = p[i];
for (int i = 0; i < q.length; i++) br[i] = q[i];
fft(ar, ai, false);
fft(br, bi, false);
for (int i = 0; i < n; i++) { // pointwise complex product
double r = ar[i] * br[i] - ai[i] * bi[i];
double im = ar[i] * bi[i] + ai[i] * br[i];
ar[i] = r; ai[i] = im;
}
fft(ar, ai, true);
long[] res = new long[need];
for (int i = 0; i < need; i++) res[i] = Math.round(ar[i]);
return res;
}
// ---------- 2. NTT modulo 998244353 = 119 * 2^23 + 1 ----------
static final long MOD = 998244353L, G = 3;
static long power(long b, long e) {
long r = 1; b %= MOD;
for (; e > 0; e >>= 1, b = b * b % MOD) if ((e & 1) == 1) r = r * b % MOD;
return r;
}
static void ntt(long[] a, boolean invert) {
int n = a.length;
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; (j & bit) != 0; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) { long t = a[i]; a[i] = a[j]; a[j] = t; }
}
for (int len = 2; len <= n; len <<= 1) {
long w = power(G, (MOD - 1) / len);
if (invert) w = power(w, MOD - 2);
int half = len / 2;
for (int start = 0; start < n; start += len) {
long wk = 1;
for (int k = 0; k < half; k++) {
long u = a[start + k], v = a[start + k + half] * wk % MOD;
a[start + k] = u + v < MOD ? u + v : u + v - MOD;
a[start + k + half] = u - v >= 0 ? u - v : u - v + MOD;
wk = wk * w % MOD;
}
}
}
if (invert) {
long nInv = power(n, MOD - 2);
for (int i = 0; i < n; i++) a[i] = a[i] * nInv % MOD;
}
}
static long[] multiplyNtt(long[] p, long[] q) {
if (p.length == 0 || q.length == 0) return new long[0];
int need = p.length + q.length - 1, n = 1;
while (n < need) n <<= 1;
long[] fa = new long[n], fb = new long[n];
for (int i = 0; i < p.length; i++) fa[i] = ((p[i] % MOD) + MOD) % MOD;
for (int i = 0; i < q.length; i++) fb[i] = ((q[i] % MOD) + MOD) % MOD;
ntt(fa, false);
ntt(fb, false);
for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % MOD;
ntt(fa, true);
return Arrays.copyOf(fa, need);
}
static long[] multiplyNaive(long[] p, long[] q) {
long[] r = new long[p.length + q.length - 1];
for (int i = 0; i < p.length; i++)
for (int j = 0; j < q.length; j++) r[i + j] += p[i] * q[j];
return r;
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
long[] want = {4, 13, 22, 15};
check(Arrays.equals(multiplyFft(new long[]{1, 2, 3}, new long[]{4, 5}), want), "fft example");
check(Arrays.equals(multiplyNtt(new long[]{1, 2, 3}, new long[]{4, 5}), want), "ntt example");
Random rng = new Random(2026);
for (int it = 0; it < 200; it++) {
long[] p = new long[1 + rng.nextInt(60)], q = new long[1 + rng.nextInt(60)];
for (int i = 0; i < p.length; i++) p[i] = rng.nextInt(2001) - 1000;
for (int i = 0; i < q.length; i++) q[i] = rng.nextInt(2001) - 1000;
long[] exact = multiplyNaive(p, q);
check(Arrays.equals(multiplyFft(p, q), exact), "fft random");
long[] got = multiplyNtt(p, q);
for (int i = 0; i < exact.length; i++) check(got[i] == ((exact[i] % MOD) + MOD) % MOD, "ntt random");
long[] bigP = new long[p.length];
for (int i = 0; i < p.length; i++) bigP[i] = (long) (rng.nextDouble() * MOD);
long[] gotBig = multiplyNtt(bigP, q);
for (int k = 0; k < gotBig.length; k++) { // naive product, reduced as we go
long s = 0;
for (int i = 0; i < bigP.length; i++)
if (k - i >= 0 && k - i < q.length) s = ((s + bigP[i] * (((q[k - i] % MOD) + MOD) % MOD)) % MOD);
check(gotBig[k] == s, "ntt big");
}
}
System.out.println("all FFT/NTT tests passed");
}
}
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
using cd = complex<double>;
const double PI = acos(-1.0);
// ---------- 1. Iterative complex FFT ----------
void fft(vector<cd>& a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) { // bit-reversal permutation
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
vector<cd> roots(n / 2);
for (int k = 0; k < n / 2; k++) // roots computed directly
roots[k] = polar(1.0, (invert ? -2 : 2) * PI * k / n);
for (int len = 2; len <= n; len <<= 1) {
int half = len / 2, step = n / len;
for (int start = 0; start < n; start += len)
for (int k = 0; k < half; k++) {
cd u = a[start + k], v = a[start + k + half] * roots[k * step];
a[start + k] = u + v;
a[start + k + half] = u - v;
}
}
if (invert) for (cd& x : a) x /= n;
}
vector<int64_t> multiplyFft(const vector<int64_t>& p, const vector<int64_t>& q) {
if (p.empty() || q.empty()) return {};
int need = p.size() + q.size() - 1, n = 1;
while (n < need) n <<= 1;
vector<cd> fa(p.begin(), p.end()), fb(q.begin(), q.end());
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; i++) fa[i] *= fb[i];
fft(fa, true);
vector<int64_t> res(need);
for (int i = 0; i < need; i++) res[i] = llround(fa[i].real());
return res;
}
// ---------- 2. NTT modulo 998244353 = 119 * 2^23 + 1 ----------
const uint32_t MOD = 998244353, G = 3;
uint64_t power(uint64_t b, uint64_t e) {
uint64_t r = 1;
for (b %= MOD; e > 0; e >>= 1, b = b * b % MOD) if (e & 1) r = r * b % MOD;
return r;
}
void ntt(vector<uint64_t>& a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
uint64_t w = power(G, (MOD - 1) / len);
if (invert) w = power(w, MOD - 2);
int half = len / 2;
for (int start = 0; start < n; start += len) {
uint64_t wk = 1;
for (int k = 0; k < half; k++) {
uint64_t u = a[start + k], v = a[start + k + half] * wk % MOD;
a[start + k] = u + v < MOD ? u + v : u + v - MOD;
a[start + k + half] = u >= v ? u - v : u + MOD - v;
wk = wk * w % MOD;
}
}
}
if (invert) {
uint64_t nInv = power(n, MOD - 2);
for (auto& x : a) x = x * nInv % MOD;
}
}
vector<uint64_t> multiplyNtt(const vector<int64_t>& p, const vector<int64_t>& q) {
if (p.empty() || q.empty()) return {};
int need = p.size() + q.size() - 1, n = 1;
while (n < need) n <<= 1;
vector<uint64_t> fa(n, 0), fb(n, 0);
for (size_t i = 0; i < p.size(); i++) fa[i] = ((p[i] % (int64_t)MOD) + MOD) % MOD;
for (size_t i = 0; i < q.size(); i++) fb[i] = ((q[i] % (int64_t)MOD) + MOD) % MOD;
ntt(fa, false);
ntt(fb, false);
for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % MOD;
ntt(fa, true);
fa.resize(need);
return fa;
}
vector<int64_t> multiplyNaive(const vector<int64_t>& p, const vector<int64_t>& q) {
vector<int64_t> r(p.size() + q.size() - 1, 0);
for (size_t i = 0; i < p.size(); i++)
for (size_t j = 0; j < q.size(); j++) r[i + j] += p[i] * q[j];
return r;
}
int main() {
vector<int64_t> want = {4, 13, 22, 15};
assert(multiplyFft({1, 2, 3}, {4, 5}) == want);
auto nt = multiplyNtt({1, 2, 3}, {4, 5});
assert(vector<int64_t>(nt.begin(), nt.end()) == want);
mt19937 rng(2026);
for (int it = 0; it < 200; it++) {
vector<int64_t> p(1 + rng() % 60), q(1 + rng() % 60);
for (auto& x : p) x = int64_t(rng() % 2001) - 1000;
for (auto& x : q) x = int64_t(rng() % 2001) - 1000;
auto exact = multiplyNaive(p, q);
assert(multiplyFft(p, q) == exact);
auto got = multiplyNtt(p, q);
for (size_t i = 0; i < exact.size(); i++)
assert((int64_t)got[i] == ((exact[i] % (int64_t)MOD) + MOD) % MOD);
vector<int64_t> bigP(p.size());
for (auto& x : bigP) x = rng() % MOD;
auto gotBig = multiplyNtt(bigP, q);
for (size_t k = 0; k < gotBig.size(); k++) {
uint64_t s = 0;
for (size_t i = 0; i < bigP.size(); i++)
if (k >= i && k - i < q.size())
s = (s + (uint64_t)bigP[i] * (uint64_t)(((q[k - i] % (int64_t)MOD) + MOD) % MOD)) % MOD;
assert(gotBig[k] == s);
}
}
cout << "all FFT/NTT tests passed\n";
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("check failed: " + what);
}
function bitReverse(n: number, swap: (i: number, j: number) => void): void {
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) swap(i, j);
}
}
// ---------- 1. Iterative complex FFT (real and imaginary parts in two arrays) ----------
function fft(re: Float64Array, im: Float64Array, invert: boolean): void {
const n = re.length;
bitReverse(n, (i, j) => {
let t = re[i]; re[i] = re[j]; re[j] = t;
t = im[i]; im[i] = im[j]; im[j] = t;
});
const sign = invert ? -1 : 1;
const cosT = new Float64Array(n / 2), sinT = new Float64Array(n / 2);
for (let k = 0; k < n / 2; k++) { // roots computed directly
cosT[k] = Math.cos((sign * 2 * Math.PI * k) / n);
sinT[k] = Math.sin((sign * 2 * Math.PI * k) / n);
}
for (let len = 2; len <= n; len <<= 1) {
const half = len / 2, step = n / len;
for (let start = 0; start < n; start += len) {
for (let k = 0; k < half; k++) {
const i = start + k, j = i + half;
const wr = cosT[k * step], wi = sinT[k * step];
const vr = re[j] * wr - im[j] * wi, vi = re[j] * wi + im[j] * wr;
re[j] = re[i] - vr; im[j] = im[i] - vi;
re[i] += vr; im[i] += vi;
}
}
}
if (invert) for (let i = 0; i < n; i++) { re[i] /= n; im[i] /= n; }
}
function multiplyFft(p: number[], q: number[]): number[] {
if (p.length === 0 || q.length === 0) return [];
const need = p.length + q.length - 1;
let n = 1;
while (n < need) n <<= 1;
const ar = new Float64Array(n), ai = new Float64Array(n);
const br = new Float64Array(n), bi = new Float64Array(n);
p.forEach((v, i) => (ar[i] = v));
q.forEach((v, i) => (br[i] = v));
fft(ar, ai, false);
fft(br, bi, false);
for (let i = 0; i < n; i++) {
const r = ar[i] * br[i] - ai[i] * bi[i];
ai[i] = ar[i] * bi[i] + ai[i] * br[i];
ar[i] = r;
}
fft(ar, ai, true);
return Array.from(ar.subarray(0, need), (x) => Math.round(x) + 0); // + 0 turns -0 into 0
}
// ---------- 2. NTT modulo 998244353 = 119 * 2^23 + 1 ----------
const MOD = 998244353, G = 3;
// a, b < 2^30: split b into 15-bit halves so every intermediate stays below 2^53 (exact in a double)
function mulMod(a: number, b: number): number {
const hi = Math.floor(b / 32768), lo = b % 32768;
return (((a * hi) % MOD) * 32768 + a * lo) % MOD;
}
function powMod(b: number, e: number): number {
let r = 1;
for (b %= MOD; e > 0; e = Math.floor(e / 2)) {
if (e % 2 === 1) r = mulMod(r, b);
b = mulMod(b, b);
}
return r;
}
function ntt(a: number[], invert: boolean): void {
const n = a.length;
bitReverse(n, (i, j) => { const t = a[i]; a[i] = a[j]; a[j] = t; });
for (let len = 2; len <= n; len <<= 1) {
let w = powMod(G, (MOD - 1) / len);
if (invert) w = powMod(w, MOD - 2);
const half = len / 2;
for (let start = 0; start < n; start += len) {
let wk = 1;
for (let k = 0; k < half; k++) {
const u = a[start + k], v = mulMod(a[start + k + half], wk);
a[start + k] = u + v < MOD ? u + v : u + v - MOD;
a[start + k + half] = u >= v ? u - v : u - v + MOD;
wk = mulMod(wk, w);
}
}
}
if (invert) {
const nInv = powMod(n, MOD - 2);
for (let i = 0; i < n; i++) a[i] = mulMod(a[i], nInv);
}
}
function multiplyNtt(p: number[], q: number[]): number[] {
if (p.length === 0 || q.length === 0) return [];
const need = p.length + q.length - 1;
let n = 1;
while (n < need) n <<= 1;
const norm = (x: number): number => ((x % MOD) + MOD) % MOD;
const fa = new Array(n).fill(0), fb = new Array(n).fill(0);
p.forEach((v, i) => (fa[i] = norm(v)));
q.forEach((v, i) => (fb[i] = norm(v)));
ntt(fa, false);
ntt(fb, false);
for (let i = 0; i < n; i++) fa[i] = mulMod(fa[i], fb[i]);
ntt(fa, true);
return fa.slice(0, need);
}
function multiplyNaive(p: number[], q: number[]): number[] {
const r = new Array(p.length + q.length - 1).fill(0);
p.forEach((x, i) => q.forEach((y, j) => (r[i + j] += x * y)));
return r;
}
{
check(multiplyFft([1, 2, 3], [4, 5]).join() === "4,13,22,15", "fft example");
check(multiplyNtt([1, 2, 3], [4, 5]).join() === "4,13,22,15", "ntt example");
let seed = 2026;
const rand = (k: number): number => { seed = (seed * 48271) % 2147483647; return seed % k; };
for (let it = 0; it < 200; it++) {
const p = Array.from({ length: 1 + rand(60) }, () => rand(2001) - 1000);
const q = Array.from({ length: 1 + rand(60) }, () => rand(2001) - 1000);
const exact = multiplyNaive(p, q);
check(multiplyFft(p, q).join() === exact.join(), "fft random");
check(multiplyNtt(p, q).join() === exact.map((x) => ((x % MOD) + MOD) % MOD).join(), "ntt random");
const bigP = p.map(() => rand(MOD));
const qn = q.map((x) => ((x % MOD) + MOD) % MOD);
const gotBig = multiplyNtt(bigP, q);
for (let k = 0; k < gotBig.length; k++) {
let s = 0;
for (let i = 0; i < bigP.length; i++) if (k - i >= 0 && k - i < q.length) s = (s + mulMod(bigP[i], qn[k - i])) % MOD;
check(gotBig[k] === s, "ntt big");
}
}
console.log("all FFT/NTT tests passed");
}
Convolution in disguise: applications
The snippets below are Python fragments that reuse multiply_fft and multiply_ntt from the implementation. Each was checked against a brute-force version on 200 random inputs.
Big-integer multiplication
Digits are coefficients, . Multiply the digit polynomials, then propagate carries. Each column sum is at most , so doubles are safe up to millions of digits; production code uses bigger digit groups (base or ) to shorten the transform, at the cost of precision headroom.
def multiply_big(x: str, y: str) -> str:
"""Multiply two non-negative decimal strings with one FFT convolution."""
a = [int(c) for c in reversed(x)] # lowest digit first
b = [int(c) for c in reversed(y)]
prod = multiply_fft(a, b) # column sums, each at most 9*9*min(len)
carry, digits = 0, []
for v in prod:
carry += v
digits.append(carry % 10)
carry //= 10
while carry:
digits.append(carry % 10)
carry //= 10
while len(digits) > 1 and digits[-1] == 0:
digits.pop()
return "".join(map(str, reversed(digits)))
assert multiply_big("1234", "5678") == "7006652"
assert multiply_big("9" * 20, "9" * 20) == str((10**20 - 1) ** 2)
assert multiply_big("0", "12345") == "0"
Counting pairs with each sum
Given values in , how many pairs sum to each ? Build the frequency polynomial . Then : the coefficient of counts ordered pairs including . Remove the terms (one at per element) and halve. instead of — the core of the classic "three numbers summing to a target, values bounded" and "how many triangles can you form from sticks" problems.
def pair_sum_counts(values):
"""counts[s] = number of unordered pairs i < j with values[i] + values[j] == s."""
freq = [0] * (max(values) + 1)
for v in values:
freq[v] += 1
sq = multiply_fft(freq, freq) # ordered pairs (i, j), i == j included
for v in values:
sq[2 * v] -= 1 # remove i == j
return [c // 2 for c in sq] # each unordered pair was counted twice
counts = pair_sum_counts([1, 2, 3, 4, 5])
assert counts[5] == 2 and counts[6] == 2 and counts[7] == 2 and counts[3] == 1 and counts[10] == 0
String matching with wildcards
Text and pattern over letters, where ? (in either) matches anything. Encode letters as and ? as 0. Pattern position aligned at text offset matches iff : the product is 0 if either is a wildcard or the letters are equal, and positive otherwise. The sum over is 0 iff the whole window matches, and expanding gives
three correlations. Reversing the pattern turns each into a convolution. Total versus for checking every offset (Clifford and Clifford, "Simple deterministic wildcard matching", Information Processing Letters, 2007). KMP (KMP) cannot handle wildcards directly, because a wildcard breaks the prefix-function logic.
def wildcard_matches(text: str, pattern: str):
"""Start positions where pattern matches text; '?' in either string matches anything.
Uses sum_j p_j * t_(i+j) * (p_j - t_(i+j))^2 = 0 with '?' encoded as 0."""
enc = lambda c: 0 if c == "?" else ord(c) - ord("a") + 1
t = [enc(c) for c in text]
p = [enc(c) for c in reversed(pattern)] # reverse: correlation becomes convolution
m = len(pattern)
t1, t2, t3 = t, [v * v for v in t], [v ** 3 for v in t]
p1, p2, p3 = p, [v * v for v in p], [v ** 3 for v in p]
# sum p^3 t - 2 p^2 t^2 + p t^3, each term one convolution
c1, c2, c3 = multiply_fft(p3, t1), multiply_fft(p2, t2), multiply_fft(p1, t3)
return [i for i in range(len(text) - m + 1)
if c1[i + m - 1] - 2 * c2[i + m - 1] + c3[i + m - 1] == 0]
assert wildcard_matches("abacaba", "a?a") == [0, 2, 4]
assert wildcard_matches("ab?d", "cd") == [2]
assert wildcard_matches("abc", "abcd") == []
Subset-sum counting
The number of subsets of items with sum is the coefficient of in . The Knapsack DP computes the same in . Multiplying the factors in a balanced tree (pairs, then pairs of pairs) costs — the divide-and-conquer product. Counts are huge, so this is done mod 998244353 with the NTT.
def subset_sum_counts(items):
"""ways[s] = number of subsets with sum s (mod 998244353): the product of (1 + x^a)."""
polys = []
for a in items:
poly = [0] * (a + 1)
poly[0] += 1
poly[a] += 1
polys.append(poly)
if not polys:
return [1]
while len(polys) > 1: # multiply in pairs: small degrees stay together
nxt = [multiply_ntt(polys[i], polys[i + 1]) for i in range(0, len(polys) - 1, 2)]
if len(polys) % 2:
nxt.append(polys[-1])
polys = nxt
return polys[0]
assert subset_sum_counts([1, 2, 3]) == [1, 1, 1, 2, 1, 1, 1]
For [1, 2, 3] the counts are [1, 1, 1, 2, 1, 1, 1]: sum 3 is reachable twice ({3} and {1, 2}).
XOR convolution: the Walsh–Hadamard transform
What if indices combine by XOR instead of addition: ? The roots-of-unity trick has an analogue on the group of bit strings, the Walsh–Hadamard transform (WHT). It has the same butterfly shape as the FFT but no twiddle factors: each pair becomes . Transform both arrays, multiply pointwise, transform again and divide by .
def walsh_hadamard(a, invert=False):
"""In-place XOR transform; len(a) is a power of two."""
n = len(a)
length = 1
while length < n:
for start in range(0, n, 2 * length):
for k in range(start, start + length):
u, v = a[k], a[k + length]
a[k], a[k + length] = u + v, u - v
length <<= 1
if invert:
for i in range(n):
a[i] //= n # exact: the true results are integers
def xor_convolution(a, b):
n = len(a)
fa, fb = a[:], b[:]
walsh_hadamard(fa)
walsh_hadamard(fb)
c = [x * y for x, y in zip(fa, fb)]
walsh_hadamard(c, invert=True)
return c
cnt = [0, 1, 1, 1, 1, 0, 1, 0] # the values 1, 2, 3, 4, 6
assert xor_convolution(cnt, cnt) == [5, 2, 4, 2, 2, 4, 2, 4]
Example: the values [1, 2, 3, 4, 6] as a count array of size 8; XOR-convolving it with itself counts ordered pairs by XOR value: [5, 2, 4, 2, 2, 4, 2, 4]. (Five pairs have XOR 0 — the five ; four pairs have XOR 2 — .) The row sums to ✔. For OR and AND convolutions, the analogous transforms are the subset and superset zeta/Möbius transforms of SOS DP, which use the same loop structure with written only into the upper (or lower) cell.
Real-world uses
- Signal processing everywhere. Spectrum analysers, audio equalisers, pitch detection, noise cancellation and radar all compute FFTs. FFTW ("the Fastest Fourier Transform in the West", Frigo and Johnson, Proceedings of the IEEE 93(2), 2005) is the reference library; NumPy's
numpy.fftuses PocketFFT; GPUs ship cuFFT. - Wireless communication. OFDM, used by Wi-Fi (IEEE 802.11a/g/n/ac/ax), 4G LTE and 5G NR, transmits data on many sub-carriers at once; the transmitter builds the signal with an inverse FFT and the receiver separates the sub-carriers with an FFT.
- Image and audio compression. JPEG uses the Discrete Cosine Transform (DCT) on 8×8 blocks, a real-valued relative of the DFT that is computed with FFT-style fast algorithms (ITU-T T.81, 1992); MP3 and AAC use the Modified DCT. The DCT concentrates a smooth block's energy into a few coefficients, which are then quantised.
- Big-integer arithmetic. GMP multiplies very large integers with an FFT-based method derived from Schönhage–Strassen (1971), which works in a ring of integers modulo rather than with floating point; smaller sizes use schoolbook, Karatsuba and Toom–Cook, with size thresholds tuned per CPU (GMP manual, "Multiplication Algorithms"). The exact crossover points vary by machine and version. Record computations of (e.g. y-cruncher) rely on FFT/NTT-style multiplication. In 2019, Harvey and van der Hoeven gave an integer multiplication algorithm (Annals of Mathematics 193(2), 2021), of theoretical interest only so far.
- Medical imaging and astronomy. MRI scanners measure the Fourier transform of the image directly ("k-space") and reconstruct with an inverse 2-D FFT; radio telescopes (interferometers) do the same with sky images.
- Scientific computing. Fast Poisson solvers, spectral methods for fluid dynamics, and particle-mesh Ewald summation in molecular dynamics (GROMACS, AMBER) all use 3-D FFTs.
- Machine learning. Large convolutions in signal and image models can be computed via FFT; long-sequence models such as Hyena and FNet use FFTs to mix tokens in .
- Post-quantum cryptography. The lattice schemes standardised by NIST in 2024 — ML-KEM (Kyber, FIPS 203) and ML-DSA (Dilithium, FIPS 204) — multiply polynomials with the NTT, modulo and respectively.
Pitfalls & edge cases
- Not padding enough. The size must be at least
len(a) + len(b) - 1, rounded up to a power of two. Too small gives a cyclic convolution: high coefficients wrap around onto low ones. - Truncating instead of rounding.
int(14.9999999)is 14. Always round. - Precision limits. If outputs can exceed about –, doubles are unsafe (see the table). Split, use NTT, or use three primes.
- NTT with negative numbers or results . The NTT gives the answer mod . Negative true coefficients come out as ; true coefficients above are silently reduced. Know your bounds.
- NTT size above with 998244353. No root of unity of order exists mod this prime; the transform is simply wrong. Results longer than 8,388,608 coefficients need another prime or splitting.
- Wrong root for the inverse. The inverse uses (angle negated, or
pow(w, p-2)) and divides by . Forgetting either gives results scaled by or reversed in order (indices ). - Overflow in the NTT butterfly.
a * b % pwith needs 64-bit. In JavaScript it needsBigIntor the split trick. - Accumulating twiddles.
w *= wlenin a long loop drifts; precompute or periodically recompute. - Empty input. Multiplying by an empty polynomial should return empty, not crash on
len - 1 = -1. - Python speed. A pure-Python FFT of size takes tens of seconds. Use
numpy.fft.rfft/irfft(with the same precision caveats), or PyPy, or C++. - Using FFT when is small. For a few hundred coefficients the naive loop is faster and exact.
Variations
- Real-input FFT. Two real sequences can be packed into one complex FFT (real part and imaginary part) and separated afterwards using conjugate symmetry, halving the work.
rfftin NumPy and FFTW's r2c plans do this. - Mixed radix and Bluestein. Sizes that are not powers of two: radix-3 and radix-5 butterflies, or Bluestein's algorithm, which turns a DFT of any size into a convolution of power-of-two size.
- Radix-4 and split-radix. Fewer multiplications per point; FFTW and most libraries use them.
- Multidimensional FFT. Transform each row, then each column. Image filtering and 2-D pattern matching use it.
- Polynomial division, inverse, log, exp, sqrt. Newton iteration on power series makes all of them given fast multiplication; contest libraries such as the AtCoder Library (
convolution) and many "formal power series" templates build on the NTT. - Multipoint evaluation and interpolation. Evaluate a degree- polynomial at arbitrary points in with a subproduct tree.
- Kitamasa / linear recurrences. characteristic polynomial with FFT-based multiplication gives the -th term of an order- recurrence in ; see Matrix Exponentiation for the matrix route.
- Number-theoretic transforms in other rings. Schönhage–Strassen uses , where the root of unity is a power of two and multiplying by it is a shift.
- Other "convolutions" over bits. XOR: Walsh–Hadamard. OR/AND: zeta/Möbius (SOS DP). Subset (disjoint union): ranked zeta transform, . GCD/LCM convolutions: Dirichlet-style transforms over divisors.
Practice ladder
Easy to hard. Problems are described in my own words; follow the links for the full statements. Hints for all; key solutions in the details blocks were checked against brute force.
1. Multiply Strings (LeetCode 43) — Multiply two decimal strings (up to 200 digits) without converting to integers. Teaches convolution plus carries; the naive loop is the intended solution, and multiply_big above is the FFT version.
Hint
res[i + j] += d1[i] * d2[j] with reversed digits, then one carry pass. That is the convolution — computed naively.
2. Convolution (AtCoder Library Practice Contest F) — Multiply two polynomials of length up to modulo 998244353. Teaches the NTT in its purest form: multiply_ntt is the full solution.
Hint
Exactly multiply_ntt. In Python, use NumPy-based tricks or another language; pure Python is too slow at this size.
3. 高速フーリエ変換 / Fast Fourier Transform (AtCoder ATC001 C) — For each , compute for two short lists of small integers. Teaches the complex FFT with rounding.
Hint
multiply_fft on the two lists, with index offset handled (dishes are numbered from 1).
4. Apples and Bananas (CSES 2111) — Given weights of apples and bananas, for every possible total weight count apple–banana pairs. Teaches frequency polynomials.
Solution
Frequency arrays of apple weights and banana weights; their convolution's coefficient counts pairs with total .
def apple_banana_counts(k, apples, bananas):
fa = [0] * (k + 1)
fb = [0] * (k + 1)
for w in apples:
fa[w] += 1
for w in bananas:
fb[w] += 1
prod = multiply_fft(fa, fb)
return prod[2:2 * k + 1] # totals 2 .. 2k
assert apple_banana_counts(5, [1, 3, 2], [3, 3]) == [0, 0, 2, 2, 2, 0, 0, 0, 0]
5. One Bit Positions (CSES 2112) — For a bit string, for every distance , count pairs of 1-bits that are apart. Teaches correlation = convolution with one input reversed.
Solution
Let be the bits and the reversed bits. Then .
def one_bit_positions(s):
a = [int(c) for c in s]
prod = multiply_fft(a, a[::-1])
n = len(a)
return [prod[n - 1 + k] for k in range(1, n)]
assert one_bit_positions("1001011010") == [1, 2, 3, 0, 2, 1, 0, 1, 0]
6. Signal Processing (CSES 2113) — Slide a short integer mask across a signal and report the sum of products at every offset, including partial overlaps. Teaches the same reversal trick and getting the output range right.
Hint
Convolve the signal with the reversed mask; every index of the full product is one offset, from the mask hanging off the left end to hanging off the right end.
7. Fuzzy Search (Codeforces 528D) — DNA strings over A, C, G, T; a pattern "fuzzily" occurs at a position if each pattern letter appears in the text within distance of where it should be. Count occurrences. Teaches one convolution per letter of the alphabet.
Hint
For each letter : mark text positions that have within distance (prefix sums), and pattern positions equal to . Correlate the two 0/1 arrays. A position matches iff the four counts sum to .
8. Yet Another String Matching Problem (Codeforces 954I) — For every substring of of length , find the minimum number of "replace all occurrences of letter by letter " operations to make it equal to (letters a–f). Teaches letter-pair correlations plus a small union-find per position.
Hint
For each ordered pair of letters , , one correlation tells, for every offset, whether some position has in and in . Then for each offset, union those letter pairs; the answer is the number of unions performed.
9. Thief in a Shop (Codeforces 632E) — Exactly items (with repetition) from given costs; list every achievable total. Teaches polynomial powers by repeated squaring, keeping coefficients 0/1.
Hint
Raise the 0/1 polynomial to the -th power with binary exponentiation, clamping coefficients to 0/1 after every product (or doing it mod a prime and accepting a negligible collision risk). Subtracting the minimum cost from every item first shrinks degrees.
10. Lucky Tickets (Codeforces 1096G) — Tickets of digits from an allowed digit set; count tickets whose first-half digit sum equals the second-half digit sum, mod 998244353. Teaches raising a polynomial to a large power with the NTT.
Solution
Let . The coefficient of counts half-tickets with sum ; the answer is . Compute by binary exponentiation with multiply_ntt.
def lucky_tickets(n, digits):
base = [0] * 10
for d in digits:
base[d] = 1
result, e = [1], n // 2
while e:
if e & 1:
result = multiply_ntt(result, base)
base = multiply_ntt(base, base)
e >>= 1
return sum(c * c for c in result) % MOD
assert lucky_tickets(4, [1, 8]) == 6
assert lucky_tickets(20, [6]) == 1
11. Divisor Set (Codeforces 1257G) — Given the prime factorisation of a huge number, find the largest set of its divisors in which none divides another. Teaches the divide-and-conquer product of many small polynomials.
Hint
By a classical theorem (de Bruijn–Tengbergen–Kruyswijk), the answer is the number of divisors with exactly prime factors counted with multiplicity: the middle coefficient of . Multiply the factors in a balanced tree with the NTT.
12. Binary Table (Codeforces 662C) — A 0/1 table; flip any rows and columns to minimise the number of 1s. Teaches the Walsh–Hadamard transform: XOR convolution of column-pattern counts with a per-pattern cost.
Hint
Columns are 20-bit masks; for a row-flip mask , a column costs . The total for is : an XOR convolution. WHT both arrays, multiply, inverse, take the minimum.
Common mistakes & interview follow-ups
"Why does the FFT need roots of unity specifically?" So that squaring the evaluation points gives only distinct points — that is what lets the two half-size subproblems reuse each other. Arbitrary points do not collapse under squaring.
"Why powers of two?" So that the halving can continue all the way down to size 1. Other sizes work with mixed-radix or Bluestein variants.
"FFT or NTT?" NTT if the answer is wanted mod an NTT-friendly prime, or exactness matters and coefficients fit. FFT for real-valued signals, or small integer coefficients where doubles are safe, or an arbitrary modulus with the 15-bit split.
"What is the error behaviour?" Rounding error grows roughly like times the magnitude of the values. Outputs near are unrecoverable; keep them below about for comfort.
"Count pairs summing to — what if values go up to ?" The polynomial would have degree : FFT is out. Use hashing or sorting with two pointers for a single . FFT pays off when the value range is small, not the count.
"How does this relate to Karatsuba?" Both are divide and conquer on multiplication. Karatsuba is exact in any ring but ; FFT needs roots of unity but reaches .
Mistakes interviewers watch for: forgetting to pad, forgetting the in the inverse, truncating instead of rounding, using int for NTT products, not removing self-pairs in pair counting, and not knowing that 998244353 .
Quick quiz
1. What is the smallest power of two you can use to multiply a degree-5 polynomial by a degree-3 polynomial?
Answer
The product has degree 8, i.e. 9 coefficients. The smallest power of two is 16.
2. List the 4th roots of unity and the bit-reversed order for .
Answer
. Bit-reversed order of indices 0–3: 0, 2, 1, 3.
3. In the 4-point trace, which entry of the output equals , and why is it real?
Answer
Index 2: . Evaluating a polynomial with real coefficients at a real point gives a real value: .
4. Why can't the NTT modulo multiply polynomials of length ?
Answer
, so the only power of two dividing is 2. There is no root of unity of order (or even 4) mod .
5. You multiply two polynomials with 10,000 coefficients each, all at most . Are doubles safe?
Answer
Outputs can reach . No: split into 15-bit halves, or use NTT with several primes.
6. What does the Walsh–Hadamard butterfly do to the pair ?
Answer
.
Further reading / sources
- James W. Cooley and John W. Tukey, "An algorithm for the machine calculation of complex Fourier series", Mathematics of Computation 19(90), 1965.
- Michael T. Heideman, Don H. Johnson, C. Sidney Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine 1(4), 1984.
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 3rd ed. Chapter 30 / 4th ed. Chapter 30 ("Polynomials and the FFT").
- cp-algorithms: Fast Fourier transform (including NTT and arbitrary-modulus multiplication) and Operations on polynomials and series.
- Matteo Frigo and Steven G. Johnson, "The Design and Implementation of FFTW3", Proceedings of the IEEE 93(2), 2005.
- Arnold Schönhage and Volker Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7, 1971; GMP manual, chapter "Algorithms → Multiplication".
- David Harvey and Joris van der Hoeven, "Integer multiplication in time ", Annals of Mathematics 193(2), 2021.
- Peter Clifford and Raphaël Clifford, "Simple deterministic wildcard matching", Information Processing Letters 101(2), 2007.
- AtCoder Library documentation,
convolution(NTT modulo 998244353). - NIST FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA), 2024 — NTT-based polynomial multiplication in standardised cryptography.
Lessons: previous — Linear Algebra for Algorithms · next — Computational Geometry · module — Math · course — DSA: Zero to Mastery.
Related Archon pages: Divide & Conquer · SOS DP · Matrix Exponentiation · Knapsack · KMP · String Hashing · Bit Manipulation · Modular Arithmetic · Compression · Cryptography.