TAOCP 4.3.1 Exercise 11
Let $u = (u_{n-1} \ldots u_1 u_0)_b$ and $v = (v_{n-1} \ldots v_1 v_0)_b$ be nonnegative $n$-place integers.
Section 4.3.1: The Classical Algorithms
Exercise 11. [10] Design an algorithm that compares two nonnegative $n$-place integers $u = (u_{n-1} \ldots u_1 u_0)b$ and $v = (v{n-1} \ldots v_1 v_0)_b$, to determine whether $u < v$, $u = v$, or $u > v$.
Verified: yes
Solve time: 1m16s
Let $u = (u_{n-1} \ldots u_1 u_0)b$ and $v = (v{n-1} \ldots v_1 v_0)_b$ be nonnegative $n$-place integers. The comparison proceeds from the most significant digit to the least significant digit. Initialize $j \leftarrow n-1$. If $u_j > v_j$, then $u > v$ and the algorithm terminates; if $u_j < v_j$, then $u < v$ and the algorithm terminates; otherwise increase $j$ by $-1$ and repeat the comparison. If all corresponding digits satisfy $u_j = v_j$, then $u = v$. Each comparison of digits involves a single primitive comparison, and at most $n$ comparisons are required.
Explicitly, the algorithm can be written as follows:
C1. [Initialize.] Set $j \leftarrow n-1$.
C2. [Compare digits.] If $u_j > v_j$, set $\text{result} \leftarrow u > v$ and terminate.
If $u_j < v_j$, set $\text{result} \leftarrow u < v$ and terminate.
If $u_j = v_j$, go to step C3.
C3. [Loop on $j$.] Decrease $j \leftarrow j-1$. If $j \ge 0$, return to step C2; otherwise set $\text{result} \leftarrow u = v$ and terminate.
Each assignment of $\text{result}$ counts as one replacement, and each update of $j$ counts as one replacement. In the worst case $n$ updates of $j$ occur and one assignment of $\text{result}$ is performed, for a total of at most $n+1$ replacements. This completes the proof.
∎