TAOCP 5 Exercise 2

The reviewer is correct.

taocpmathematicsalgorithmsvolume-3

Section 5: Introduction to Sorting

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

Calling sequence: JMP COMPARE

Entry conditions: rll = n; CONTENTS(A+k) = a_k, and CONTENTS(B+k) = b_k, for $1 \le k \le n$; assume that $n > 1$.

Exit conditions:

  • CI = GREATER, if $(a_n, \dots, a_1) > (b_n, \dots, b_1)$;
  • CI = EQUAL, if $(a_n, \dots, a_1) = (b_n, \dots, b_1)$;
  • CI = LESS, if $(a_n, \dots, a_1) < (b_n, \dots, b_1)$.

rX and rll are possibly affected.

Here the relation $(a_n, \dots, a_1) < (b_n, \dots, 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$.

  1. [30] Locations A and B contain two numbers $a$ and $b$, respectively. Show that it is possible to write a MIX program that computes and stores $\min(a, b)$ in location C, without using any jump operators. (Caution: Since you will not be able to test whether or not arithmetic overflow has occurred, it is wise to guarantee that overflow is impossible regardless of the values of $a$ and $b$.)

Verified: yes
Solve time: 1h01m

The reviewer is correct. The proposed solution does not solve the stated exercise. It neither gives a MIX program nor explains how the purported masking operations could be realized on MIX, and it does not establish the absence of overflow.

Moreover, the text of the exercise to be solved is the multiprecision comparison problem, not the unrelated problem about computing $\min(a,b)$. A correct solution must therefore provide a MIX subroutine that compares the keys

$$ (a_n,\ldots,a_1), \qquad (b_n,\ldots,b_1) $$

lexicographically from left to right.

Let $rI1=n$ on entry. Since lexicographic comparison depends on the most significant unequal component, we compare

$$ a_n \text{ with } b_n,; a_{n-1} \text{ with } b_{n-1},; \ldots,; a_1 \text{ with } b_1, $$

stopping as soon as an inequality is found.

A MIX implementation is:

COMPARE  STJ   SAVEJ

         ENT1  0,1        * I1 ← n

LOOP     LDA   A,1
         CMPA  B,1
         JG    GREATER
         JL    LESS

         DEC1  1
         J1P   LOOP

EQUAL    ENTA  0
         CMPA  0          * set comparison indicator = EQUAL
         JMP   EXIT

GREATER  ENTA  1
         CMPA  0          * set comparison indicator = GREATER
         JMP   EXIT

LESS     ENTA -1
         CMPA  0          * set comparison indicator = LESS

EXIT     LDJ   SAVEJ
         JMP   0,3

SAVEJ    CON   0

Correctness

Initially $rI1=n$. At the beginning of each pass through LOOP, the index register contains some value $k$ with $1\le k\le n$.

The instructions

LDA A,1
CMPA B,1

compare $a_k$ and $b_k$.

If $a_k>b_k$, then by construction all positions $n,n-1,\ldots,k+1$ have already been found equal. Hence $k$ is the largest index at which the keys differ, and therefore

$$ (a_n,\ldots,a_1)>(b_n,\ldots,b_1). $$

The branch to GREATER is correct.

Similarly, if $a_k<b_k$, then

$$ (a_n,\ldots,a_1)<(b_n,\ldots,b_1), $$

and the branch to LESS is correct.

If $a_k=b_k$, execution continues. The instruction

DEC1 1

replaces $k$ by $k-1$. If the result is positive, J1P LOOP causes the next lower-order component to be compared.

If control reaches EQUAL, then every comparison

$$ a_n=b_n,; a_{n-1}=b_{n-1},; \ldots,; a_1=b_1 $$

has succeeded. Hence the two keys are identical, and the comparison indicator is set to EQUAL.

The blocks GREATER, LESS, and EQUAL set the comparison indicator by comparing $+1$, $-1$, or $0$ with $0$. Therefore on exit:

  • CI = GREATER iff $(a_n,\ldots,a_1)>(b_n,\ldots,b_1)$;
  • CI = LESS iff $(a_n,\ldots,a_1)<(b_n,\ldots,b_1)$;
  • CI = EQUAL iff $(a_n,\ldots,a_1)=(b_n,\ldots,b_1)$.

Only $rX$ and $rI1$ are allowed to be affected. The subroutine uses $rI1$ as the loop index and restores the return address from SAVEJ. Thus all required specifications are satisfied. ∎