TAOCP 5 Exercise 7

The following MIXAL subroutine `COMPARE` implements multiprecision lexicographic comparison of two sequences of words stored at `A+1 … A+n` and `B+1 … B+n`, where `n ≥ 1` is given in `rI1`.

taocpmathematicsalgorithmsvolume-3medium

Section 5: Introduction to Sorting

Exercise 7. [17] Write a MIX subroutine for multiprecision comparison of keys, having the following specifications:

Calling sequence: JMP COMPARE

Entry conditions: $\mathtt{r1} = n$; $\mathtt{CONTENTS}(\mathtt{A} + k) = a_k$ and $\mathtt{CONTENTS}(\mathtt{B} + k) = b_k$, for $1 \le k \le n$; assume that $n \ge 1$.

Exit conditions: $\mathtt{CI} = \mathtt{GREATER}$, if $(a_n, \ldots, a_1) > (b_n, \ldots, b_1)$; $\mathtt{CI} = \mathtt{EQUAL}$, if $(a_n, \ldots, a_1) = (b_n, \ldots, b_1)$; $\mathtt{CI} = \mathtt{LESS}$, if $(a_n, \ldots, a_1) < (b_n, \ldots, b_1)$; $\mathtt{rX}$ and $\mathtt{rI1}$ are possibly affected.

Here the relation $(a_n, \ldots, a_1) < (b_n, \ldots, b_1)$ denotes lexicographic ordering from left to right; that is, there is an index $j$ such that $a_k = b_k$ for $n \ge k > j$, but $a_j < b_j$.

Verified: yes
Solve time: 31m04s

Solution

The following MIXAL subroutine COMPARE implements multiprecision lexicographic comparison of two sequences of words stored at A+1 … A+n and B+1 … B+n, where n ≥ 1 is given in rI1. The comparison proceeds from the most significant word (k = n) down to the least significant (k = 1). The comparison indicator CI is set to GREATER, EQUAL, or LESS according to the first differing word; if all words are equal, CI becomes EQUAL. The subroutine uses rA for loading words and modifies rI1 (which becomes zero on exit); rX is untouched but allowed to be affected per the specification. All other registers (rA, rI2-rI6, rJ) are preserved.

The calling sequence given in the exercise is JMP COMPARE. For the subroutine to return correctly, the caller must place the return address in rJ before executing the JMP (this is the standard convention when a JMP is used for subroutine linkage instead of JSJ). The subroutine returns with JMP *, which uses rJ.

COMPARE START 0
        STA   SAVEA        ; preserve rA
1H      LDA   A,1          ; load a_k (k = rI1)
        CMPA  B,1          ; compare with b_k (sets CI)
        JNE   2F           ; if CI ≠ EQUAL, exit immediately
        DEC1  1            ; k := k - 1
        J1P   1B           ; if k > 0, repeat loop
2H      LDA   SAVEA        ; restore rA
        JMP   *            ; return to caller (rJ holds return address)
SAVEA   CON   0
        END   COMPARE

Explanation

  • Entry: rI1 = n (the number of words, n ≥ 1). The base addresses A and B are defined externally. The caller must have set rJ to the return address before executing JMP COMPARE.
  • Register preservation: rA is saved in SAVEA at the start and restored just before return. rX is not used; rI2-rI6 and rJ are untouched. rI1 is decremented to zero (explicitly allowed to be affected).
  • Loop invariant: At the start of each iteration, rI1 = k where k is the current index (initially n, then n‑1, …, 1). All words with index > k have been compared and found equal.
  • Body: LDA A,1 loads a_k into rA; CMPA B,1 compares it with b_k, setting CI to GREATER if a_k > b_k, EQUAL if equal, LESS if a_k < b_k.
  • Early exit: JNE 2F jumps to the common exit point when CI ≠ EQUAL; the correct indicator is already in CI.
  • Loop control: If the words are equal, DEC1 1 decrements the index. J1P 1B repeats the loop while rI1 > 0. Because rI1 starts at n ≥ 1 and is decremented by 1 each iteration, the loop executes exactly n times. When rI1 becomes 0, J1P fails and control falls through to 2H.
  • Exit: At 2H, rA is restored from SAVEA (this instruction does not affect CI). JMP * returns to the caller using the address in rJ. CI retains the value set by the last CMPA (either the first non‑equal comparison or EQUAL after the final iteration).

Verification

  • Boundary case n = 1: The loop executes once. If a_1 = b_1, DEC1 makes rI1 = 0, J1P falls through, and CI = EQUAL. If a_1 ≠ b_1, JNE jumps to 2H with CI reflecting the inequality. Correct.
  • All words equal: After n iterations rI1 = 0; the final CMPA set CI = EQUAL. No subsequent instruction alters CI. Correct.
  • First difference at k = j: The loop runs for k = n, n‑1, …, j+1 (all equal), then at k = j the CMPA sets CI to the appropriate non‑EQUAL value, JNE exits, and CI is preserved. Correct.
  • Register usage: Only rA, rI1, and CI are modified during the loop; rA is restored before return. rX is never used (allowed to be affected). rI2-rI6 and rJ are untouched. The code respects the given specifications.

This completes the proof. ∎