TAOCP 5 Exercise 6
The MIX computer represents integers in sign‑magnitude form: each word consists of a sign (±) and five bytes, giving a magnitude in the range \(0 \le M \le 64^5-1\).
Section 5: Introduction to Sorting
Exercise 6. [15] Mr. B. C. Dull (a MIX programmer) wanted to know if the number stored in location A is greater than, less than, or equal to the number stored in location B. So he wrote LDA A; SUB B and tested whether register A was positive, negative, or zero. What serious mistake did he make, and what should he have done instead?
Verified: yes
Solve time: 7m41s
Solution
The MIX computer represents integers in sign‑magnitude form: each word consists of a sign (±) and five bytes, giving a magnitude in the range (0 \le M \le 64^5-1). The word size is (64^5 = 1,073,741,824). The SUB instruction computes (rA \leftarrow rA - M) (where (M) is the contents of the addressed memory location). If the true result has magnitude (\ge 64^5), an overflow occurs: the overflow flag is set, and the value stored in (rA) is the true result taken modulo the word size (i.e., the magnitude is reduced modulo (64^5)), with the sign of the true result except that a zero result is always given a positive sign.
Mr. Dull’s code
LDA A ; rA ← value of A
SUB B ; rA ← rA − value of B
followed by testing whether (rA) is positive, negative, or zero, fails when the true difference (A - B) is exactly (\pm 64^5).
Consider (A = 64^5-1) and (B = -1). The true difference is (64^5). Its magnitude equals the word size, so overflow occurs. The stored magnitude becomes (64^5 \bmod 64^5 = 0); the sign of the true result is positive, and the zero‑sign rule forces the result to (+0). The test therefore reports “zero”, i.e. (A = B), even though (A > B).
Similarly, if (A = -(64^5-1)) and (B = 1), the true difference is (-64^5). Overflow again yields magnitude (0) and sign positive ((+0)), so the test again reports equality while in fact (A < B).
These are not isolated cases: any pair of numbers with opposite signs whose magnitudes sum to exactly (64^5) (e.g., (A = k), (B = -(64^5-k)) for (1 \le k \le 64^5-1)) will be mis‑compared. The error violates the trichotomy law required for sorting and is therefore a serious mistake.
The correct method is to use the CMP instruction, which is designed for comparison:
LDA A ; rA ← value of A
CMP B ; compare rA with value of B; sets comparison indicator
The CMP instruction never overflows; it sets the comparison indicator to LESS, EQUAL, or GREATER according to the true arithmetic values of the two numbers. One then uses the conditional jumps JL, JE, JG (or JAN, JAZ, JAP after a CMP is not needed because CMP sets the dedicated comparison indicator). This approach works for all possible values, including the boundary cases that break the subtraction method.
This completes the proof. ∎