TAOCP 5 Exercise 1

**Corrected Solution.

taocpmathematicsalgorithmsvolume-3

Section 5: Introduction to Sorting

Exercise 1. [**] [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: 1h11m

Corrected Solution.

Mr. B. C. Dull attempted to determine whether the number in location $A$ is greater than, less than, or equal to the number in location $B$ by performing

$$ \texttt{LDA A; SUB B} $$

and then testing the sign of the accumulator. This approach is flawed for the following reasons.

In MIX, numbers are stored in sign-magnitude format, and arithmetic operations are performed on fixed-size words. Suppose the accumulator contains $A$ and we subtract $B$ with SUB B. The true mathematical result is

$$ R = A - B. $$

If $|R|$ exceeds the largest representable magnitude (i.e., if $R$ is outside the range of a MIX word), the overflow toggle is set. When overflow occurs, the sign stored in the accumulator does not reliably indicate the true sign of $A-B$. For example, if $A$ is very large and positive, and $B$ is very large and negative, then $A-B$ would mathematically be positive, but the accumulator may store an incorrect magnitude and possibly the wrong sign, because MIX cannot represent the result exactly. Consequently, testing the sign of the accumulator to determine whether $A>B$, $A<B$, or $A=B$ is unsafe.

To perform a correct comparison in MIX, one should use the comparison instructions that set the comparison indicator. For the accumulator, this instruction is

$$ \texttt{CMPA B} $$

which compares the contents of the accumulator with the contents of memory location $B$ and sets the comparison indicator according to the relation between $A$ and $B$. Specifically:

  • If $A > B$, the comparison indicator is set to >
  • If $A < B$, the comparison indicator is set to <
  • If $A = B$, the comparison indicator is set to =

Once the comparison indicator is set, one can branch safely using the MIX conditional jumps:

$$ \begin{aligned} \texttt{CMPA B} \ \texttt{JGT Greater} \ \texttt{JLT Less} \ \texttt{JEQ Equal} \end{aligned} $$

This method avoids any arithmetic overflow and does not alter the contents of $A$ or $B$. It relies solely on the comparison indicator, which MIX guarantees will correctly reflect the relation between two numbers, regardless of their magnitude.

Thus, the serious mistake Mr. Dull made was relying on the sign of the accumulator after subtraction, which is unreliable due to overflow. The correct approach is to use CMPA (or the analogous comparison instruction for other registers) and branch on the comparison indicator.

∎