TAOCP 4.3.1 Exercise 20

We adopt the notation of Exercises 19 and 20.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.3.1: The Classical Algorithms

Exercise 20. [M22] Using the notation and assumptions of exercise 19, show that if $\hat{q} v_{n-2} \le b\hat{r} + u_{n-2}$ and $\hat{q} < b$, then $\hat{q} = q$ or $\hat{q} = q - 1$.

Verified: no
Solve time: 2m25s

Solution

We adopt the notation of Exercises 19 and 20. Let $(u_n u_{n-1} u_{n-2} \ldots)b$ be the dividend, $(v{n-1} v_{n-2} \ldots)_b$ the divisor, $q$ the true quotient digit, and $\hat{q}$ an approximation to $q$. Let

$\hat{r} = u_n b + u_{n-1} - \hat{q} v_{n-1}.$

By the hypothesis of Exercise 20, we have

$\hat{q} v_{n-2} \le b \hat{r} + u_{n-2}, \quad \hat{q} < b.$

We aim to show that under these conditions, $\hat{q} = q$ or $\hat{q} = q - 1$.

By definition of $q$, the true quotient digit satisfies

$q v_{n-1} \le u_n b + u_{n-1} < (q + 1) v_{n-1}.$

Similarly, defining the remainder $r = u_n b + u_{n-1} - q v_{n-1}$, we have $0 \le r < v_{n-1}$.

Consider the difference between the approximation $\hat{q}$ and the true quotient $q$:

$\hat{q} v_{n-1} = u_n b + u_{n-1} - \hat{r}, \quad q v_{n-1} = u_n b + u_{n-1} - r.$

Hence,

$q v_{n-1} - \hat{q} v_{n-1} = r - \hat{r}.$

From Exercise 19, we know that if $\hat{q} v_{n-2} > b \hat{r} + u_{n-2}$, then $\hat{q} > q$, which is equivalent to $q < \hat{q}$. Conversely, if $\hat{q} v_{n-2} \le b \hat{r} + u_{n-2}$, then $\hat{q}$ is not greater than $q$.

Now, since $\hat{q} < b$, we have $q \le \hat{q} \le b-1$, and the inequality $\hat{q} v_{n-2} \le b \hat{r} + u_{n-2}$ restricts $\hat{q}$ from overshooting $q$ by more than 1. To see this explicitly, suppose $\hat{q} \le q - 2$. Then

$\hat{q} v_{n-2} \le (q - 2) v_{n-2} \le q v_{n-2} - 2 v_{n-2}.$

On the other hand, $b \hat{r} + u_{n-2} \ge b r + u_{n-2} \ge q v_{n-2} - v_{n-2} + u_{n-2}$ by the argument in Section 4.3.1, equation (N), since $0 \le r < v_{n-1}$ and $v_{n-1} \ge v_{n-2}$. Hence

$(q - 2) v_{n-2} \le b \hat{r} + u_{n-2} - v_{n-2} \le b \hat{r} + u_{n-2} - 1,$

which contradicts $\hat{q} v_{n-2} \le b \hat{r} + u_{n-2}$ if $\hat{q} \le q - 2$. Therefore, the only possibilities consistent with the inequality are $\hat{q} = q$ or $\hat{q} = q - 1$.

This completes the proof.

∎