TAOCP 1.4.1 Exercise 3

The subroutine MAXIMUM, as specified in equation (4), has the calling sequence `JMP MAXIMUM` and the entry condition `rI1 = n` with $n \ge 1$.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.4.1: Subroutines

Exercise 3. [M15] Complete the information in (4) by stating precisely what happens to register J and the comparison indicator as a result of the subroutine; state also what happens if register I1 is not positive.

Verified: yes
Solve time: 53s

Solution

The subroutine MAXIMUM, as specified in equation (4), has the calling sequence JMP MAXIMUM and the entry condition rI1 = n with $n \ge 1$. Its exit conditions currently describe only the values of rA, rI2, and rI3. To complete the specification, we must consider all effects of the subroutine on the machine state, specifically on register J and the comparison indicator CI, and we must also describe behavior when the entry condition is violated (i.e., when rI1 is not positive).

The subroutine begins by executing STJ EXIT, which stores the current location of the subsequent instruction in rJ. Therefore, upon entry, rJ contains the address of the location immediately following the JMP MAXIMUM in the calling program. This value is preserved until the final JMP * instruction at EXIT, which uses rJ to return control to the caller. Consequently, the final value of rJ is the return address, which is the same as its initial value upon entry of the subroutine.

During execution, the comparison indicator CI is used whenever a CMPA or CMP instruction is executed to compare the current candidate maximum with rA. At the conclusion of the subroutine, the comparison indicator reflects the last comparison performed between rA and CONTENTS(X + k) for $1 \le k \le n$. Therefore, CI is left in a state corresponding to whether rA is equal to, less than, or greater than the last element compared. No instructions in the subroutine reset CI after this comparison.

If the entry condition rI1 = n \ge 1 is violated, the subroutine may exhibit undefined behavior. Specifically, if rI1 \le 0, the indexing loop that scans the table from 1 to n will not execute any iterations, so rA remains uninitialized (or retains the value present in rA upon entry), rI2 may be undefined or left at an initial value, and rI3 remains 0 as in the original subroutine. The comparison indicator CI may retain the result of a previous comparison or remain undefined. Register rJ continues to contain the return address and will be correctly used by JMP * at EXIT.

Thus, the fully specified effects of the subroutine are:

Calling sequence: JMP MAXIMUM.

Entry conditions: rI1 = n; no assumptions on the contents of other registers.

Exit conditions:

  1. rA = \max_{1 \le k \le n} \text{CONTENTS}(X+k) if $n \ge 1$, otherwise undefined.
  2. rI2 is the index $k$ corresponding to the maximum element if $n \ge 1$, otherwise undefined.
  3. rI3 = 0.
  4. rJ contains the return address, i.e., the location following the original JMP MAXIMUM in the caller.
  5. CI reflects the result of the final comparison made in computing the maximum; if $n \le 0$, CI may be undefined.

If rI1 \le 0, the subroutine completes without modifying memory, sets rI3 = 0, preserves rJ correctly, and leaves rA, rI2, and CI in an undefined or indeterminate state.

This completes the proof.

∎