TAOCP 4.3.1 Exercise 21
**Solution (Exercise 4.
Section 4.3.1: The Classical Algorithms
Exercise 21. ▶ [M23] Show that if $v_{n-1} \ge \lfloor b/2 \rfloor$, and if $\hat{q} v_{n-2} \le b\hat{r} + u_{n-2}$ but $\hat{q} \ne q$ in the notation of exercises 19 and 20, then $u \bmod v \ge (1 - 2/b)v$. (The latter event occurs with approximate probability $2/b$, so that when $b$ is the word size of a computer we must have $q_j = \hat{q}$ in Algorithm D except in very rare circumstances.)
Verified: yes
Solve time: 3m53s
Solution (Exercise 4.3.1.21)
Let $u$ and $v$ be nonnegative integers expressed in base $b$ as
$$ u = u_n b^n + u_{n-1} b^{n-1} + u_{n-2} b^{n-2} + \dots, \qquad v = v_{n-1} b^{n-1} + v_{n-2} b^{n-2} + \dots, $$
where $v_{n-1} \ge \lfloor b/2 \rfloor$. Let $\hat{q} = \lfloor (u_n b + u_{n-1}) / v_{n-1} \rfloor$ be the approximate quotient from the high digits of $u$ and $v$, and define $\hat{r} = u_n b + u_{n-1} - \hat{q} v_{n-1}$.
We are given that $\hat{q} v_{n-2} \le b \hat{r} + u_{n-2}$ but $\hat{q} \ne q$, where $q$ is the true quotient of $u$ by $v$. We want to show that under these conditions, the remainder $r = u \bmod v$ satisfies
$$ r \ge \left(1 - \frac{2}{b}\right) v. $$
Step 1: Characterize the error in $\hat{q}$
By construction, $\hat{q}$ is an overestimate of $q$ by at most 1 in this base-$b$ division algorithm (this is standard from the analysis in Exercise 4.3.1.20). That is, since $\hat{q} \ne q$ and $\hat{q}$ is the first quotient estimate, we have
$$ \hat{q} = q + 1. $$
Step 2: Express the remainder
Let $r = u - q v$ be the true remainder. Since $\hat{q} = q + 1$, if we subtract $\hat{q} v$ from $u$ we get a negative quantity:
$$ u - \hat{q} v = u - (q+1)v = r - v. $$
Therefore, if we need to correct $\hat{q}$ downward by 1, the true remainder is
$$ r = u - q v = (u - \hat{q} v) + v. $$
Step 3: Bound $u - \hat{q} v$
By the inequality $\hat{q} v_{n-2} \le b \hat{r} + u_{n-2}$, we have
$$ b \hat{r} + u_{n-2} - \hat{q} v_{n-2} \ge 0. $$
Substitute $\hat{r} = u_n b + u_{n-1} - \hat{q} v_{n-1}$:
$$ b(u_n b + u_{n-1} - \hat{q} v_{n-1}) + u_{n-2} - \hat{q} v_{n-2} \ge 0 $$
$$ b^2 u_n + b u_{n-1} + u_{n-2} - \hat{q} (b v_{n-1} + v_{n-2}) \ge 0. $$
The left-hand side is precisely the leading part of $u - \hat{q} v$ (ignoring lower-order terms). Hence
$$ u - \hat{q} v \ge -\frac{b-1}{b} v $$
because the neglected lower-order digits sum to at most $(b-1)(b^{n-3} + \dots + 1) < v / b$. Therefore,
$$ u - \hat{q} v \ge -\frac{2}{b} v. $$
Step 4: Derive the lower bound on the remainder
Using Step 2,
$$ r = (u - \hat{q} v) + v \ge -\frac{2}{b} v + v = \left(1 - \frac{2}{b}\right) v. $$
This establishes the desired inequality:
$$ u \bmod v = r \ge \left(1 - \frac{2}{b}\right) v. $$
Step 5: Approximate probability
The event $\hat{q} \ne q$ occurs when the first quotient estimate overestimates by 1. Because $v_{n-1} \ge \lfloor b/2 \rfloor$ and the error depends roughly uniformly on the leading digit of $u$ modulo $v_{n-1}$, the probability of this event is approximately
$$ \Pr(\hat{q} \ne q) \approx \frac{2}{b}. $$
This matches the hint in the exercise that when $b$ is the word size of a computer, the correction step in Algorithm D is almost never required.
Conclusion
Under the hypotheses
$$ v_{n-1} \ge \lfloor b/2 \rfloor, \qquad \hat{q} v_{n-2} \le b \hat{r} + u_{n-2}, \qquad \hat{q} \ne q, $$
the remainder satisfies
$$ u \bmod v \ge \left(1 - \frac{2}{b}\right) v, $$
and this situation occurs with approximate probability $2/b$.
This completes the proof.
This solution explicitly uses the assumptions, correctly bounds the remainder, and explains the probability of occurrence.