Convolutions and Their Applications

Two strange dice

A board-game shop sells a pair of six-sided dice with odd labels. The first die shows 1, 2, 2, 3, 3, 4 and the second shows 1, 3, 4, 5, 6, 8. The box claims that they can replace two ordinary dice in any game that only looks at the total. Is that true? For every total from 2 to 12, the pair must give as many of the 36 equally likely rolls as ordinary dice do: one way to roll 2, two ways to roll 3, and so on up to six ways to roll 7.

The table answers the question for two dice. It does not scale: the same question for two lists of ${10}^5$ numbers between 0 and ${10}^6$ (how many pairs, one number from each list, give each possible total?) has ${10}^{10}$ pairs. This module shows how to answer it with one convolution, and then uses the same step for two more problems that don't look like sums at all: comparing a short pattern with a long text at every alignment, and finding three numbers that add up to zero.

It builds on module 25, which computes a convolution fast with the fast Fourier transform. Here that computation is a tool with a known price, and the question is what it can count.

std = [1, 2, 3, 4, 5, 6]
odd1, odd2 = [1, 2, 2, 3, 3, 4], [1, 3, 4, 5, 6, 8]

def totals_by_pairs(xs, ys):
    """Count pairs by total, one pair at a time."""
    count = {}
    for x in xs:
        for y in ys:
            count[x + y] = count.get(x + y, 0) + 1
    return count

assert totals_by_pairs(odd1, odd2) == totals_by_pairs(std, std)
assert totals_by_pairs(odd1, odd2)[7] == 6 and len(totals_by_pairs(std, std)) == 11

The double loop, and where it wastes work

The double loop visits every pair, so it costs $|A|·|B|$ additions and dictionary updates. When both lists are short, that is the right method. When they are long and their values lie in a limited range, it does far more work than the answer contains. Two lists of ${10}^5$ numbers in $[0,{10}^6]$ have ${10}^{10}$ pairs, but only $2·{10}^6+1$ possible totals. The loop reaches each total thousands of times, one pair at a time.

The fix is to stop working per pair and start working per value. Describe list $A$ by its count vector: $a_v$ is the number of times the value $v$ appears in $A$. Describe $B$ by $b_w$ in the same way. The first odd die has count vector $(a_1,a_2,a_3,a_4)=(1,2,2,1)$, and the answer is then a single formula in these two vectors.

Convolution counts sums

The convolution of two sequences $a$ and $b$ is the sequence $c=a*b$ with

$$c_k=\sum _{i+j=k}{a}_i{b}_j.$$

It is the rule for multiplying polynomials: if $A(x)={\sum }_i{a}_i{x}^i$ and $B(x)={\sum }_j{b}_j{x}^j$, then $c_k$ is the coefficient of $x^k$ in $A(x)B(x)$, because $x^i{x}^j=x^{i+j}$.

Proof. Group the pairs by their values. The pairs whose first number has value $i$ and whose second has value $j$ number exactly $a_i{b}_j$. Such a pair has total $k$ exactly when $i+j=k$, so summing $a_i{b}_j$ over all $i+j=k$ counts each pair with total $k$ once and no other pair. $◻$

So the answer to the dice question is one convolution. Draw the products $a_i{b}_j$ in a grid, and $c_k$ is the sum along one anti-diagonal, the cells with $i+j=k$:

The grid has 32 cells instead of the table's 36, which is no saving yet. The saving comes from how a convolution is computed. Before that, one Python block checks the lemma on the dice with a stand-in: schoolbook computes the convolution by the definition, one product per cell. Module 25's transform gives the same numbers.

def count_vector(xs):
    """a[v] = how many times v appears; values are 0..max(xs)."""
    a = [0] * (max(xs) + 1)
    for x in xs:
        a[x] += 1
    return a

def schoolbook(a, b):
    """Stand-in for a fast convolution: c[k] = sum of a[i] * b[j] over i + j = k."""
    c = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            c[i + j] += x * y
    return c

c_odd = schoolbook(count_vector(odd1), count_vector(odd2))
c_std = schoolbook(count_vector(std), count_vector(std))
assert c_odd == c_std == [0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
assert count_vector(odd1)[1:] == [1, 2, 2, 1]

def poly_mul(*ps):
    out = [1]
    for p in ps:
        out = schoolbook(out, p)
    return out

X, ONE_X, ONE_X_X2, ONE_MX_X2 = [0, 1], [1, 1], [1, 1, 1], [1, -1, 1]
assert poly_mul(X, ONE_X, ONE_X_X2, ONE_MX_X2) == count_vector(std)
assert poly_mul(X, ONE_X, ONE_X_X2) == count_vector(odd1)
assert poly_mul(X, ONE_X, ONE_X_X2, ONE_MX_X2, ONE_MX_X2) == count_vector(odd2)

The model: a convolution as one step with a known price

Module 25 computes the convolution of two sequences with lengths adding to at most $N+1$, for $N$ a power of two, by three transforms of length $N$, one pointwise product and one scaling. It works with exact integers modulo the prime $p=998244353$ (a number-theoretic transform), and it costs

$$\frac{3}{2}N{\log }_{2}N+2N$$

multiplications modulo $p$, in the worst case, with no randomness. The model is the word RAM: numbers below $p$ fit in a machine word, and each addition or multiplication modulo $p$ is one step. Two facts about that price matter here.

It depends on the lengths of the vectors, not on how many items they count. A count vector for values in $[0,U]$ has length $U+1$ whether the list has 3 numbers or ${10}^5$.

It is exact only when every true $c_k$ is below $p$. The transform returns each $c_k$ modulo $p$, so an answer of $p$ or more comes back wrong without warning. A count is safe when it is provably small. For two lists without repeated values, $c_k\le min(|A|,|B|)$, because each $x$ in $A$ has at most one partner $y=k-x$ in $B$. With repeats, $c_k$ can reach $|A|·|B|$, and past $p$ you need a second prime and the Chinese remainder theorem (module 25). A floating-point FFT with complex numbers is faster in practice but rounds, and module 25 showed it rounding wrong on large inputs. Every count in this module stays below $p$.

For the big instance, two lists of ${10}^5$ distinct numbers in $[0,{10}^6]$, the totals run from 0 to $2·{10}^6$, so $N=2^{21}$. That is about $7·{10}^7$ multiplications against ${10}^{10}$ pair visits, and each count is at most ${10}^5$, far below $p$.

def ntt_mults(N):
    """Multiplications of one exact convolution of padded length N (module 25's count)."""
    return 3 * (N // 2) * (N.bit_length() - 1) + 2 * N

def padded_length(size):
    N = 1
    while N < size:
        N *= 2
    return N

P = 998244353
N_big = padded_length(2 * 10**6 + 1)
assert N_big == 2**21 and ntt_mults(N_big) == 70_254_592
assert 10**5 * 10**5 == 10**10 and 10**5 < P

Any range: shift the values

Values need not start at 0. Temperatures, offsets and differences are often negative. Shift every value of $A$ by its smallest value, ${\ell }_A$, so that index $v-{\ell }_A$ holds the count of $v$, and do the same for $B$. A pair $(x,y)$ then lands at index

$$k=(x-{\ell }_A)+(y-{\ell }_B),$$

so entry $k$ of the convolution counts the pairs with total $k+{\ell }_A+{\ell }_B$. This also settles what the transform pays for: the span of each list, its largest value minus its smallest, and not the size of the numbers. The values ${10}^6$ to ${10}^6+100$ need a vector of length 101, not ${10}^6+101$.

Sliding a pattern: every alignment at once

Reverse one of the two sequences and the convolution computes something that does not look like a sum of pairs. Take a long sequence $t_0,\dots ,t_{n-1}$ and a short one $q_0,\dots ,q_{m-1}$, and place $q$ against $t$ starting at position $s$. Their correlation at $s$ is the dot product of the pattern with the window it covers:

$$r_s=\sum _{j=0}^{m-1}{t}_{s+j}{q}_j,0\le s\le n-m.$$

Now let $q^R$ be $q$ reversed, $q_i^R=q_{m-1-i}$, and convolve. In entry $s+m-1$ of $t*q^R$, the index pairs are $(s+j,m-1-j)$, one for each $j$, and they sum to $s+m-1$ as they should. Their products are $t_{s+j}{q}_j$. So

$$r_s=(t*q^R{)}_{s+m-1},$$

and one convolution gives the dot product at every one of the $n-m+1$ alignments.

Here is a use for it. A sequencing machine reads a short strand of DNA, and a lab wants to know where on a reference it fits best: at every alignment, how many letters disagree? The reference is CCTAGGATTAGCTAGA and the read is TAGC.

Letters are not numbers, but a letter's positions are a 0/1 sequence. For each letter $x$, let $t_i^{(x)}=1$ when the reference has $x$ at position $i$, and $q_j^{(x)}=1$ when the read has $x$ at position $j$. The correlation of these two indicator sequences at $s$ counts the positions where both have an $x$. Summed over the letters, it counts every agreement at alignment $s$, so the number of disagreements is

$$d_s=m-\sum _x{r}_s^{(x)}.$$

A letter that never occurs in the read contributes nothing, so a read with $\sigma$ distinct letters needs $\sigma$ correlations, each one convolution.

The block checks the table against a direct count, one alignment at a time (a stand-in, again: it is the slow method this section replaces).

ref, read = "CCTAGGATTAGCTAGA", "TAGC"
n, m = len(ref), len(read)

def agreements(letter, s):
    """Direct count: positions j where both ref[s+j] and read[j] are the letter."""
    return sum(ref[s + j] == letter == read[j] for j in range(m))

d = [m - sum(agreements(x, s) for x in set(read)) for s in range(n - m + 1)]
direct = [sum(ref[s + j] != read[j] for j in range(m)) for s in range(n - m + 1)]
assert d == direct == [4, 4, 1, 3, 4, 3, 4, 3, 0, 4, 4, 4, 1]
assert [agreements("T", s) for s in range(n - m + 1)] == [0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1]
assert [agreements("A", s) for s in range(n - m + 1)] == [0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1]

Three numbers that sum to zero

The last application answers a yes-or-no question. Given three lists $A$, $B$, $C$ of integers in $[-U,U]$, are there $x$ in $A$, $y$ in $B$ and $z$ in $C$ with $x+y+z=0$? This is 3SUM. Sorting $A$ and $B$ and walking two pointers inward once for each $z$ answers it with $O(n^2)$ comparisons and additions for lists of $n$ numbers.

Convolution answers it by counting. By the counting lemma, the convolution of the count vectors of $A$ and $B$ gives, for every total $k$, the number of pairs with $x+y=k$. A triple exists exactly when some $z$ in $C$ finds a nonzero count at $k=-z$. Summing the counts over the $z$ in $C$ gives the number of triples. The cost is $O(n)$ to build the vectors and read the answers, plus one convolution of length about $4U$: $O(n+U\log U)$ operations in the word RAM, in the worst case. That is below $n^2$ when the values lie in a range small compared with $n^2$.

This does not contradict what is believed about 3SUM. In one common form, the 3SUM conjecture says that for integers in $[-n^3,n^3]$, no algorithm on the word RAM runs in $O(n^{2-\epsilon })$ time for a fixed $\epsilon >0$. It is unproved, and algorithms faster by logarithmic factors are known. When $U$ is around $n^3$, $U\log U$ is far above $n^2$, so the convolution route helps only for dense lists.

A3, B3, C3 = [-8, -3, 5, 9], [-6, 2, 4, 11], [-7, -1, 3, 10]
lo = min(A3) + min(B3)
sums = schoolbook(count_vector([x - min(A3) for x in A3]), count_vector([y - min(B3) for y in B3]))

def pairs_with_total(k):
    return sums[k - lo] if 0 <= k - lo < len(sums) else 0

hits = {z: pairs_with_total(-z) for z in C3}
assert hits == {-7: 1, -1: 1, 3: 0, 10: 0} and sum(hits.values()) == 2
brute = [(x, y, z) for x in A3 for y in B3 for z in C3 if x + y + z == 0]
assert brute == [(-3, 4, -1), (5, 2, -7)]

The two triples are $-3+4-1$ and $5+2-7$. For $z=3$ the pairs would have to total $-3$, and none does.

Why the answers are right, and what they cost

All three applications rest on the counting lemma, used in three ways: count vectors for sums, indicator sequences with one of them reversed for alignments, and a lookup at $-z$ for 3SUM. The remaining step is exactness. With the transform working modulo $p$, each answer is right when the true value is below $p$. For totals of lists without repeats that is $min(|A|,|B|)$ at most, and an agreement count is at most $m$.

The costs, in the word RAM with arithmetic modulo $p$ as unit steps, worst case. For totals, the lists hold $n_A$ and $n_B$ numbers with spans at most $U$; for alignments, the text has $n$ letters, the read $m$, with $\sigma$ distinct letters in the read; for 3SUM, the lists hold $n$ numbers in $[-U,U]$. The convolution column leaves out the linear time to build the vectors and read the answers.

Neither column wins everywhere. A convolution pays for the range, the double loop for the pairs. Ten numbers spread over $[0,{10}^6]$ make 100 pairs and a convolution of length $2^{21}$. For alignments, a read with many distinct letters needs many convolutions: with $\sigma$ near $m$, the direct count wins. The honest summary is the table, not "convolution is faster".

Measure the claim

Take two lists of $n$ numbers drawn uniformly from $[0,2^{14})$ (seeds $451+n$), and compare the pairs the double loop visits with the multiplications of the convolution of their shifted count vectors ("mults" in the table, with padded length $N$), computed with ntt_mults from the spans.

import random

rows = []
for size in (100, 1000, 10000):
    rng = random.Random(451 + size)
    xs = [rng.randrange(2**14) for _ in range(size)]
    ys = [rng.randrange(2**14) for _ in range(size)]
    N = padded_length((max(xs) - min(xs)) + (max(ys) - min(ys)) + 1)
    rows.append((size, size * size, N, ntt_mults(N)))
assert rows == [(100, 10_000, 32768, 802_816), (1000, 1_000_000, 32768, 802_816),
                (10000, 100_000_000, 32768, 802_816)]
assert 896**2 == 802_816

The convolution's cost does not move with $n$, because the spans barely change: even 100 random numbers spread over most of $[0,2^{14})$. The double loop grows a hundredfold per row. On these instances the two meet at $n=896$, where $n^2$ is exactly 802,816. These are counts, not timings; a Python double loop and a Python transform have different constants per operation.

A problem that looks different

A cashier has one coin each of 1, 2, 5, 10, 20 and 50 cents, plus one each of a few odd commemorative coins. In how many ways can she pay exactly $k$ cents, for every $k$ up to the total value of her coins? Think about it before the next module.

Practise

The lab makes each idea yours. You draw a pattern sliding along a signal one shift at a time, then compute every shift with one convolution. You predict and then watch the totals of two lists with negative values. You compute disagreements at every alignment of a strand, with a meter on how much of it you read. You measure where the double loop and the convolution cross over, on lists of your own. And you solve a problem from an observatory that doesn't say what it is.

Recap

You can now: state and prove the counting lemma; count the totals of two lists with one convolution of shifted count vectors; turn a correlation into a convolution by reversing one sequence; count disagreements at every alignment with one correlation per letter; decide 3SUM on a bounded range by counting; and say when each beats the double loop.

Invariant: entry $k$ of the convolution of two count vectors is exactly the number of pairs whose shifted values add up to $k$; with one sequence reversed, entry $s+m-1$ is the dot product at alignment $s$.

Complexity achieved: totals of two lists in $O(|A|+|B|+U\log U)$ word-RAM operations, worst case, where $U$ bounds the spans, exact modulo $p=998244353$ when every count is below $p$; disagreements at all alignments with $\sigma$ convolutions of length about $2n$; 3SUM on $[-U,U]$ in $O(n+U\log U)$. The double loop costs $|A|·|B|$, $(n-m+1)m$ and $n^2$.

Failure mode: forgetting the shift or the reversal (the answer lands at the wrong index), or trusting a count at or past $p$ (it comes back reduced modulo $p$).

In real software: NumPy's numpy.convolve computes the sum directly, and does it by handing the reversed second array to its correlation routine, the same reversal as above; its documentation points to scipy.signal.fftconvolve for large inputs. SciPy's scipy.signal.convolve with method="auto" estimates the operations of both methods and picks the cheaper, and it falls back to the direct sum for integer inputs once a simple bound on the results reaches $2^{52}$, near the $2^{53}$ up to which a double holds every integer exactly.

Retrieval (module 05): Karp–Rabin fingerprints find every exact occurrence of a pattern in expected $O(n+m)$ time. Why can't a rolling fingerprint tell you how many letters disagree at each alignment?

Check yourself

1. Why is entry $k$ of the convolution of two count vectors exactly the number of pairs with total $k$, and when does the transform modulo $p$ return that number unchanged?
2. Convolve a text of length $n$ with a reversed pattern of length $m$. Entry $s+m-1$ is the dot product at alignment $s$. What do the entries before $m-1$ and after $n-1$ hold?
3. For disagreements at every alignment, compare the convolution method with the direct count. For which reads (length, number of distinct letters) does the direct count win?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.