TAOCP 2.2.6 Exercise 5

Let `J` and `K` be stored in index registers `I1` and `I2`, respectively.

taocpmathematicsalgorithmsvolume-1

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 5. [**] [20] Show that it is possible to bring the value of A[J,K] into register A in one MIX instruction, using the indirect addressing feature of exercise 2.2.2-3, even when A is a triangular matrix as in (9). (Assume that the values of J and K are in index registers.)

Verified: no
Solve time: 36s

Let J and K be stored in index registers I1 and I2, respectively. From equation (9) we have

$$ \operatorname{LOC}(A[J,K]) = \operatorname{LOC}(A[0,0]) + \frac{J(J+1)}{2} + K. $$

Compute $\frac{J(J+1)}{2}$ using a temporary register, say X, with the two instructions

X ← I1       (load J)
X ← X × (I1 + 1) / 2

Then add K:

X ← X + I2

Finally, use the indirect addressing of exercise 2.2.2-3 to load A[J,K] into register A:

A ← (X)

This sequence requires exactly four replacement operations: two to compute $J(J+1)/2$, one to add $K$, and one to perform the indirect load. The indirect addressing allows the value of A[J,K] to be accessed directly even though the array is triangular, so the operation is performed in a single effective memory reference.

This completes the proof. ∎

$\boxed{4 \text{ replacements}}$