TAOCP 4.3.1 Exercise 22

We are asked to find a four-digit number $u$ divided by a three-digit number $v$ in base $b = 10$ for which step D6 of Algorithm D is necessary.

taocpmathematicsalgorithmsvolume-2medium

Section 4.3.1: The Classical Algorithms

Exercise 22. ▶ [24] Find an example of a four-digit number divided by a three-digit number for which step D6 is necessary in Algorithm D, when the radix $b$ is 10.

Verified: yes
Solve time: 1m09s

Solution

We are asked to find a four-digit number $u$ divided by a three-digit number $v$ in base $b = 10$ for which step D6 of Algorithm D is necessary. Step D6 occurs when the initial quotient estimate $\hat{q}$ is too large, so that subtracting $\hat{q}v$ from the current remainder produces a negative result. In such cases, the algorithm must decrement $\hat{q}$ and add $v$ back to the remainder to correct the overestimate.

Let us denote the four-digit dividend as $u = u_3 u_2 u_1 u_0$ and the three-digit divisor as $v = v_2 v_1 v_0$. Step D6 is triggered if $\hat{q} > q$, the true quotient digit, which occurs precisely when the approximation

$\hat{q} = \left\lfloor \frac{u_3 b + u_2}{v_2} \right\rfloor$

is strictly greater than the actual quotient $q = \lfloor (u_3 u_2 u_1 u_0) / v \rfloor$. By the analysis in exercises 19 and 20, this can happen when $v_2$ is small relative to $b$ and the leading digits of $u$ are such that

$\hat{q} v_1 > b \hat{r} + u_1, \quad \hat{r} = u_3 b + u_2 - \hat{q} v_2.$

To construct an explicit example, we choose $v_2$ small so that the initial estimate is high, but $v$ divides $u$ poorly so that the overestimate occurs.

Take $v = 201$ and $u = 1000$. Then

$\hat{q} = \left\lfloor \frac{10 \cdot 100 + 0}{2} \right\rfloor = \left\lfloor \frac{1000}{2} \right\rfloor = 500.$

The actual quotient is

$q = \left\lfloor \frac{1000}{201} \right\rfloor = 4.$

The initial estimate $\hat{q} = 500$ is vastly too large. Subtracting $500 \cdot 201 = 100500$ from the dividend $1000$ produces a negative remainder. Step D6 is required to decrement $\hat{q}$ repeatedly until the remainder becomes nonnegative, ultimately producing the correct quotient $q = 4$.

A smaller and cleaner example is preferable for clarity. Let $v = 503$ and $u = 1000$. Then

$\hat{q} = \left\lfloor \frac{10 \cdot 1 + 0}{5} \right\rfloor = \left\lfloor \frac{10}{5} \right\rfloor = 2,$

but the actual quotient is

$q = \left\lfloor \frac{1000}{503} \right\rfloor = 1.$

Subtracting $2 \cdot 503 = 1006$ from $1000$ gives $-6$, a negative remainder. Step D6 corrects the overestimate by decrementing $\hat{q}$ to 1 and adding $v = 503$ back, yielding remainder $1000 - 503 = 497 \ge 0$.

Thus an explicit example satisfying the requirement is

$u = 1000, \quad v = 503.$

Step D6 is necessary because the initial quotient estimate $\hat{q} = 2$ exceeds the true quotient $q = 1$, producing a negative intermediate remainder.

This completes the solution.

∎