Skip to section
Foundationsfor rotation-free search
Section 25 of 5248% of course
Contents
Chapter 4 Section 4.6 75 min

Part III · Construction and proof

Chapter studio: derive layouts from constraints

Practice target selection, reversal, block placement, and extraction.

Derivation exercises

Try working through these without looking back at the formulas. The goal here is to reconstruct the layout directly from the destination rule, not to just regurgitate a string of symbols you memorized.

1. If D=6, list the physical positions of logical coordinates 0 through 5 in block j=2.

That block spans positions 12 through 17. The positions are 17, 16, 15, 14, 13, 12.

2. What target does that vector use?

Dj+D−1 = 12 + 5 = 17.

3. Show that coordinate i=4 actually reaches that target.

Query position 4 plus corpus position (17−4=13) gives us exactly 17.

4. Physical position 29 lies inside a D=8 block. Find j and its logical i.

j = floor(29/8) = 3. The block target is 31, so i = 31 − 29 = 2.

5. Why is p(j,i)=Dj+i the wrong layout entirely?

Because it makes a matching pair land at Dj+2i, which changes as i changes! That's just natural order shifted over into a block.

6. If we have N=64 and D=8, list every valid score tap.

7, 15, 23, 31, 39, 47, 55, and 63. It's just the right edge of each of the eight blocks.

Mastery 1 of 3

What relation are we fundamentally converting here?

Mastery 2 of 3

What is the exact target for vector j?

Mastery 3 of 3

What does polynomial multiplication actually do for us beyond just pairwise products?

Chapter 4 complete

The trick is now a solid derivation

We choose a target, solve i+p(i)=T, and get p(i)=T−i. By translating that rule into each D-wide block, we end up with reversed coordinates and score taps at Dj+D−1. The construction makes total sense and we've heavily exercised it; next up in Chapter 5, we're going to turn it into a rigorous proof.

Repository layer · second pass

Can you derive a layout from an operation’s grouping rule?

The reusable skill is to start with the relation you need and the relation your cheap primitive groups. Here the desired relation is equal logical indices; polynomial multiplication groups constant sums. Solving the mapping equation bridges them. Other workloads may require a different mapping or may not admit one.

A complete derivation includes domain, range, injectivity, target uniqueness, and boundary behavior. It also names the costs transferred elsewhere, such as unused coefficients or client extraction.

Reasoning chain

  1. 1

    Write desired logical relation.

  2. 2

    Write available physical grouping relation.

  3. 3

    Introduce a storage mapping.

  4. 4

    Solve the index equation.

  5. 5

    Prove the mapping stays in bounds and does not collide.

  6. 6

    Count benefits and displaced costs.

Worked trace

Derive with offsets

  1. Store query i at Q+i.
  2. Store corpus coordinate i in block base B at unknown p(i).
  3. Require Q+i+p(i)=T.
  4. Solve p(i)=T−Q−i and choose T so p spans B through B+D−1.

Result. Reversal is one member of a family of offset solutions.

Executable lens · Python

Make the hidden state visible

def derive_positions(d, query_base, corpus_base):
    target = query_base + corpus_base + d - 1
    positions = [target - query_base - i for i in range(d)]
    return target, positions

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

Misconception clinic

Tempting mistakes

  • Optimizing a representation before writing the relation.
  • Proving matching terms arrive without ruling out contaminating terms.

Retrieval and transfer

Close the book first

  1. Derive the mapping when the query is also placed in a block.
  2. State injectivity of p(i).
  3. Identify the two contamination questions deferred to Chapter 5.