Skip to section
Foundationsfor rotation-free search
Section 10 of 5219% of course
Contents
Chapter 2 Section 2.4 58 min

Part I · Mathematical foundations

Why products gather into output buckets

Track every pair by the sum of its input positions.

Replace algebraic terms with labeled buckets

Imagine one output bucket for every possible destination position. Multiply an input at position i by an input at position k, then drop the numerical product into bucket i+k. At the end, add each bucket’s contents.

Interactive multiplication tableSelect an output bucket to reveal its diagonal.
bucket 2 = 3
b0=4b1=5b2=-2a0=2a1=-1a2=3
Animated visual · ManimWatch diagonals become buckets

Every cell routes according to its row index plus its column index. Unmute for narration.

Choose different buckets in the table. Cells on the same down-left diagonal share an index sum. That diagonal is exactly the set of products added into one output coefficient.

Use the interactive table as an experiment

Select bucket 0, then move one bucket at a time toward bucket 4. Before clicking, predict how many highlighted cells the next diagonal will contain. The counts grow 1, 2, 3 and then shrink 2, 1 because a finite multiplication table has edges.

Now edit one input coefficient. Only the cells in its row or column change, but several output buckets may change because that coefficient participates in a product with every coefficient on the other side. This is the key difference from coordinatewise multiplication.

Worked example

Trace output bucket 2

For A=[2,−1,3] and B=[4,5,−2], bucket 2 accepts pairs (0,2), (1,1), and (2,0):

c₂ = a₀b₂ + a₁b₁ + a₂b₀ = 2(−2) + (−1)5 + 3(4) = 3

Forward and backward views

Forward routing
(i,k) → i+k

Choose an input pair and compute its destination.

Backward gathering
k = t−i

Choose output t and find every pair that reaches it.

The backward view replaces k with t−i:

ct = ∑ aibt−i, using only indices that exist

Do not rush this formula. It says only: for output bucket t, choose a position i from A; the required B position must be whatever completes the sum to t.

Make the valid range explicit

If A has length L and B has length M, then i must satisfy both 0≤i<L and 0≤t−i<M. Solving the second condition says t−(M−1)≤i≤t. Combining the bounds yields:

max(0, t−M+1) ≤ i ≤ min(L−1, t)

This looks more formal than “omit missing indices,” but it is the same rule made executable. For L=M=3 and t=2, i ranges from 0 to 2. For t=4, only i=2 remains.

Worked example

Trace an edge bucket

For length-3 inputs, output bucket 4 requires i+k=4 while both indices lie between 0 and 2. Only (2,2) works. That is why the final diagonal has one cell even though the middle diagonal has three.

Check your understanding

Which pairs reach output bucket 4 when both inputs have positions 0 through 4?

Retrieval check: gather bucket 3 for lengths 3 and 4

The valid pairs are (0,3), (1,2), and (2,1). Pair (3,0) is excluded because the first input ends at index 2.

Section summary

  • Every product routes to bucket i+k.
  • One bucket gathers an anti-diagonal of the multiplication table.
  • The backward form bt−i names the partner needed to reach t.

Repository layer · second pass

What exactly is an output bucket?

An output bucket is the accumulator for one destination exponent. Every pair (i,k) satisfying i+k=t contributes to bucket t. On a multiplication grid these pairs lie on an anti-diagonal. The geometry, formula, and accumulation loop are three views of the same routing rule.

Buckets near the edges contain fewer possible pairs; middle buckets contain more. This triangular contribution count explains why output length is L+R−1 and why central coefficients often require the most additions.

Reasoning chain

  1. 1

    Fix one destination t.

  2. 2

    Solve k=t−i.

  3. 3

    Keep only pairs whose indices remain inside both lists.

  4. 4

    Multiply the corresponding values.

  5. 5

    Add every surviving product into bucket t.

Worked trace

Enumerate bucket 3 safely

  1. Let both inputs have positions 0 through 3.
  2. Solve i+k=3.
  3. The valid pairs are (0,3),(1,2),(2,1),(3,0).
  4. No other pair has the required sum.

Result. Bucket 3 contains four products and is the full anti-diagonal.

Executable lens · Python

Make the hidden state visible

size, target = 4, 3
pairs = [(i, target - i) for i in range(size)
         if 0 <= target - i < size]
assert pairs == [(0, 3), (1, 2), (2, 1), (3, 0)]

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Calling a grid row a bucket; rows hold one fixed left index, buckets hold one fixed sum.
  • Forgetting to reject t−i outside the right input.

Retrieval and transfer

Close the book first

  1. List contributors to bucket 5 for input lengths four and five.
  2. Derive the number of buckets from the largest destination.
  3. Sketch how contributor counts grow and shrink across equal-length inputs.