TAOCP 4.3.1 Exercise 10

We analyze the effect of interchanging instructions in Program S, which implements subtraction of nonnegative integers according to Algorithm S.

taocpmathematicsalgorithmsvolume-2medium

Section 4.3.1: The Classical Algorithms

Exercise 10. [18] Would Program S work properly if the instructions on lines 06 and 07 were interchanged? If the instructions on lines 05 and 06 were interchanged?

Verified: no
Solve time: 3m05s

Solution

We analyze the effect of interchanging instructions in Program S, which implements subtraction of nonnegative integers according to Algorithm S. The relevant instructions are:

  • Line 05: ADD U+N,1 N, adds the minuend digit $u_j$ to the accumulator.
  • Line 06: SUB V+N,1 N, subtracts the subtrahend digit $v_j$ from the accumulator.
  • Line 07: DIV WH1 N, divides by the word containing $b$ or related normalization.
  • Line 08: STA W+N,1 N, stores the result $w_j$.

Case 1: Interchange lines 06 and 07

If we perform the division (DIV WH1) before subtracting $v_j$, the accumulator holds $u_j + k$ instead of $u_j - v_j + k$. Denote the intended intermediate value as $t = u_j - v_j + k$ and the carry $k \in {-1, 0}$. Then executing DIV WH1 first produces $t' = \lfloor (u_j + k)/b \rfloor$, which is generally not equal to $\lfloor (u_j - v_j + k)/b \rfloor$. Consequently, the stored value $w_j$ in line 08 will be incorrect, and the borrow $k$ updated later will also be wrong. Therefore, the algorithm will fail to produce the correct result.

Case 2: Interchange lines 05 and 06

If we first execute SUB V+N,1 and then ADD U+N,1, the accumulator will hold $-v_j + k + u_j = u_j - v_j + k$, which is algebraically identical to the original order. The subsequent division and store instructions then compute $w_j$ and update $k$ correctly, since the operations are associative in integer arithmetic. Therefore, this interchange does not affect the correctness of the algorithm; Program S will continue to work properly.

Conclusion

Interchanging lines 06 and 07 causes the algorithm to fail, because the division depends on the accumulator containing $u_j - v_j + k$. Interchanging lines 05 and 06 preserves correctness, because addition and subtraction commute when applied to the same accumulator with the same constants.

This completes the proof.

∎