Skip to section
Foundationsfor rotation-free search
Section 9 of 5217% of course
Contents
Chapter 2 Section 2.3 60 min

Part I · Mathematical foundations

Multiply every term by every term

Build polynomial multiplication with the same distributive law used in arithmetic.

Begin with the distributive law you already know

For ordinary numbers, a(b+c)=ab+ac. The left factor multiplies every term inside the parentheses. With two sums, every left term multiplies every right term.

(a+b)(c+d) = ac + ad + bc + bd

Polynomial multiplication uses exactly this rule. The only extra bookkeeping is the power label on each term.

Worked example

Multiply two two-term polynomials

Let A(x)=2+3x and B(x)=4−x. Draw all four pairings:

2 × 48
2 × (−x)−2x
3x × 412x
3x × (−x)−3x²

Now combine the two terms labeled x:

(2+3x)(4−x) = 8 + 10x − 3x²

Each pair has two independent calculations

Values3 × (−1) = −3

Multiply coefficients as ordinary numbers.

Positionsx¹ × x¹ = x²

Add exponents to find the output label.

Trace the product as records

Instead of doing mental FOIL, write each pair as a record (left position, right position, product, destination). For A=[2,3] and B=[4,−1], the four records are:

paircoefficient productdestination
(0,0)2·4 = 80+0 = 0
(0,1)2·(−1) = −20+1 = 1
(1,0)3·4 = 121+0 = 1
(1,1)3·(−1) = −31+1 = 2

Grouping records by destination gives bucket 0: 8; bucket 1: −2+12=10; bucket 2: −3. This trace format scales beyond the two-term mnemonic and maps directly to a program.

Check your understanding

In (1+2x)(3+4x), which pairs contribute to the x term?

Longer inputs use the same rule

A length-3 polynomial has three terms, including any explicitly zero terms. Multiplying two length-3 polynomials creates 3×3=9 pair products. The largest possible position is 2+2=4, so the full output can require five positions.

length L times length M produces at most length L+M−1

Check your understanding

What is the highest possible output position for lengths 4 and 6?

Count products separately from output positions

Lengths L and M create L·M input pairs because each of the L left terms meets each of the M right terms. Those products collapse into at most L+M−1 destination positions. For L=M=100, that is 10,000 pair products but only 199 output buckets. Mixing up these two counts leads to incorrect storage estimates and incorrect performance estimates.

Worked example

Justify the output length

The smallest destination is 0+0=0. The largest is (L−1)+(M−1)=L+M−2. Counting all integer positions from 0 through L+M−2 inclusively gives L+M−1 buckets.

Turn the hand procedure into a program

The first implementation deliberately uses arrays, two loops, one multiplication, and one addition. A library call would be shorter, but it would hide the exact mechanism we are trying to learn. Step through the source line by line and connect each line to the multiplication table above.

Runnable Python · explicit lists and loopsComplete source
01output = [0] * (len(left) + len(right) - 1)02 03for i, left_value in enumerate(left):04    for k, right_value in enumerate(right):05        destination = i + k06        product = left_value * right_value07        output[destination] += product
Retrieval check: state a loop invariant for the nested loops

After some set of input pairs has been processed, every output bucket equals the sum of products from exactly the processed pairs whose index sum names that bucket. Each new pair preserves the statement by adding its product to its one correct destination.

Section summary

  • The distributive law creates every input pair.
  • Coefficient values multiply; position exponents add.
  • Products with equal destination positions add together.
  • Full output length grows to L+M−1.

Repository layer · second pass

Why must every term meet every term?

Polynomial multiplication is ordinary distribution applied systematically. Each left coefficient multiplies each right coefficient exactly once. The numeric values multiply, while the position labels add. Only after all pairs exist do we combine products with equal destination labels.

For lengths L and R there are L×R elementary products. This pair count matters later: the NTT changes how efficiently we compute the same product, but it does not change which mathematical pairs contribute.

Reasoning chain

  1. 1

    Choose one left term.

  2. 2

    Distribute it across every right term.

  3. 3

    Repeat for every left term.

  4. 4

    Annotate each product with i+k.

  5. 5

    Collect products only after the full table is visible.

Worked trace

A two-by-three product

  1. Let A=1+2x and B=3−x+4x².
  2. The first row is 3−x+4x².
  3. The second row is 6x−2x²+8x³.
  4. Matching labels combine to 3+5x+2x²+8x³.

Result. Six pair products become four output coefficients.

Executable lens · Python

Make the hidden state visible

a, b = [1, 2], [3, -1, 4]
pairs = [(i, k, left * right) for i, left in enumerate(a)
         for k, right in enumerate(b)]
assert len(pairs) == len(a) * len(b)

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

Misconception clinic

Tempting mistakes

  • Pairing only matching indices, which computes part of a dot product instead.
  • Combining products before recording their destinations.

Retrieval and transfer

Close the book first

  1. Draw the full pair table for lengths three and four.
  2. Predict the lowest and highest destinations before multiplying values.
  3. Explain why a zero coefficient still owns a position.