TAOCP 1.1 Exercise 3
The trivial replacement in Algorithm E occurs at step E3: m \leftarrow n,\qquad n \leftarrow r.
Exercise 3. [20] Change Algorithm E (for the sake of efficiency) so that all trivial replacement operations such as “$m \leftarrow n$” are avoided. Write this new algorithm in the style of Algorithm E, and call it Algorithm F.
Verified: yes
Solve time: 3m53s
The trivial replacement in Algorithm E occurs at step E3:
$$ m \leftarrow n,\qquad n \leftarrow r. $$
At the next occurrence of step E1, the old value of $m$ is never used again. Only the pair consisting of the previous values of $n$ and $r$ matters. Therefore the assignment $m \leftarrow n$ is unnecessary if the algorithm is rewritten so that the variables alternate roles.
Introduce four variables, $m$, $n$, $r$, and $t$. At each stage, divide one variable by another, then continue with the remainder while avoiding any replacement whose only purpose is to copy a value that is already available elsewhere. The resulting procedure is as follows.
Algorithm F (Euclid’s algorithm without trivial replacements). Given two positive integers $m$ and $n$, find their greatest common divisor.
F1. [Find remainder.] Divide $m$ by $n$ and let $r$ be the remainder. (We will have $0 \le r < n$.)
F2. [Is it zero?] If $r = 0$, the algorithm terminates; $n$ is the answer.
F3. [Find remainder.] Divide $n$ by $r$ and let $t$ be the remainder. (We will have $0 \le t < r$.)
F4. [Is it zero?] If $t = 0$, the algorithm terminates; $r$ is the answer.
F5. [Reduce.] Divide $r$ by $t$ and let $r$ be the remainder. (We will have $0 \le r < t$.)
F6. [Is it zero?] If $r = 0$, the algorithm terminates; $t$ is the answer.
F7. [Reduce.] Divide $t$ by $r$ and let $t$ be the remainder. (We will have $0 \le t < r$.)
F8. [Is it zero?] If $t \ne 0$, go back to step F5; $r$ is the answer. ▎
To justify correctness, compare Algorithm F with Algorithm E. Suppose Algorithm E reaches step E1 with values $(m,n)$. Step F1 computes the same remainder $r$ as E1. If $r \ne 0$, Algorithm E would perform
$$ m \leftarrow n,\qquad n \leftarrow r, $$
and then repeat E1. Instead, Algorithm F immediately performs the next division, namely dividing the old $n$ by $r$ in step F3. Thus F3 produces exactly the same remainder that Algorithm E would compute after one execution of E3 and a return to E1.
The same reasoning applies to steps F5 and F7. Each division in Algorithm F corresponds to one execution of E1 in Algorithm E after omitting the unnecessary copying operations of E3. The sequence of remainders is unchanged, and termination occurs precisely when a remainder becomes zero. At that point the divisor is the greatest common divisor, by the argument in Section 1.1.
Algorithm F therefore computes the same result as Algorithm E while avoiding all trivial replacements such as $m \leftarrow n$. This completes the proof.
∎