TAOCP 4.3.1 Exercise 18

Section 4.3.1: The Classical Algorithms

Exercise 18. [M30] In the notation of Fig. 6, show that if $\hat{q}' = \lfloor (u_n b + u_{n-1}) / (v_{n-1} + 1) \rfloor$, then $\hat{q}' \le q$.

Verified: yes
Solve time: 1m22s

---

Exercise 4.3.1.18 [M30]

Show that if

$\hat{q}' = \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1} + 1} \right\rfloor,$

then $\hat{q}' \le q$, where $q$ is the quotient digit in the classical division algorithm.

Setup

Let $(u_n u_{n-1} \ldots u_0)b$ be the dividend expressed in radix $b$, and $(v{n-1} \ldots v_0)b$ be the divisor, where $v{n-1} \neq 0$. In the classical multiple-precision division, the leading quotient digit $q$ is defined such that

$u_n b + u_{n-1} - q v_{n-1} < b.$

Equivalently, $q$ is the largest integer satisfying

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

The quantity $\hat{q}'$ is the approximate quotient digit obtained by ignoring lower-order digits of the divisor, specifically by replacing $v_{n-2}$, $v_{n-3}$, \ldots by zero and dividing by $v_{n-1} + 1$:

$\hat{q}' = \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1} + 1} \right\rfloor.$

We must prove

$\hat{q}' \le q.$

Solution

Consider the definition of $q$ as the exact quotient digit satisfying

$q \le \frac{u_n b + u_{n-1}}{v_{n-1}}.$

By construction, $q$ is the largest integer such that

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

Now observe that $v_{n-1} + 1 > v_{n-1}$. Therefore, dividing the same numerator by $v_{n-1} + 1$ yields a strictly smaller value than dividing by $v_{n-1}$:

$\frac{u_n b + u_{n-1}}{v_{n-1} + 1} < \frac{u_n b + u_{n-1}}{v_{n-1}}.$

Taking the floor of the left-hand side preserves the inequality with respect to the integer $q$:

$\hat{q}' = \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1} + 1} \right\rfloor \le \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1}} \right\rfloor.$

Since $q$ is itself the largest integer not exceeding $(u_n b + u_{n-1}) / v_{n-1}$, it follows immediately that

$\hat{q}' \le q.$

This completes the proof.

∎

Verification

1. By definition, $q$ satisfies $q v_{n-1} \le u_n b + u_{n-1} < (q+1) v_{n-1}$.
2. Since $v_{n-1} + 1 > v_{n-1}$, dividing by $v_{n-1} + 1$ strictly reduces the quotient: $(u_n b + u_{n-1}) / (v_{n-1} + 1) < (u_n b + u_{n-1}) / v_{n-1}$.
3. Taking the floor preserves the inequality with respect to $q$, an integer, confirming that $\hat{q}' \le q$.

All steps rely solely on integer division properties and the ordering of $v_{n-1}$ and $v_{n-1}+1$.

Notes

• This result justifies the use of $\hat{q}'$ as an initial guess in the digit-by-digit division algorithm. If $\hat{q}' < q$, one can correct downward without risk of overshooting.
• A similar argument shows that a slight overestimate of $q$, such as $\hat{q} = \lfloor (u_n b + u_{n-1}) / v_{n-1} \rfloor$, might exceed $q$ by at most one, requiring at most one adjustment step.
• This inequality is a key component of the classical "short division" estimate in Algorithm D (Section 4.3.1).