TAOCP 4.3.1 Exercise 17
Let $V = (v_{n-1}\ldots v_0)_b$ be the divisor and let $R$ be the partial remainder at the moment the quotient digit $q$ is being determined in Knuth’s division algorithm (Algorithm D, Fig.
Section 4.3.1: The Classical Algorithms
Exercise 17. [M20] In the notation of Fig. 6, assume that $v_{n-1} \ge \lfloor b/2 \rfloor$; show that if $u_n = v_{n-1}$, we must have $q = b - 1$ or $b - 2$.
Verified: no
Solve time: 4m10s
Let $V = (v_{n-1}\ldots v_0)b$ be the divisor and let $R$ be the partial remainder at the moment the quotient digit $q$ is being determined in Knuth’s division algorithm (Algorithm D, Fig. 6). We assume $v{n-1} \ge \lfloor b/2 \rfloor$ and $u_n = v_{n-1}$.
We prove directly that the true quotient digit satisfies
$$ b-2 ;\le; \frac{R}{V} ;<; b, $$
which forces $q = \lfloor R/V \rfloor \in {b-2, b-1}$.
Since $u_n = v_{n-1}$, the leading term of the current remainder is exactly aligned with the leading term of the divisor:
$$ R = v_{n-1} b^n + x, $$
where the tail satisfies $0 \le x < b^n$.
The divisor satisfies a simple upper bound in terms of its leading digit. Since all digits are at most $b-1$,
$$ V = v_{n-1} b^{n-1} + v_{n-2} b^{n-2} + \cdots + v_0 < v_{n-1} b^{n-1} + (b-1)(b^{n-2} + \cdots + 1) < (v_{n-1}+1)b^{n-1}. $$
Because $v_{n-1} \ge 1$, we also have $v_{n-1}+1 \le 2v_{n-1}$, hence
$$ V \le 2 v_{n-1} b^{n-1}. $$
Upper bound: $R < bV$
We use $v_{n-1} \ge 1$. Then
$$ bV \ge b \cdot v_{n-1} b^{n-1} = v_{n-1} b^n. $$
Since $x < b^n$, we have
$$ R = v_{n-1} b^n + x < v_{n-1} b^n + b^n = (v_{n-1}+1)b^n. $$
But $bV \ge v_{n-1}b^n$, so certainly $R < bV$ holds because the leading term of $bV$ already dominates the leading term of $R$, and the excess $x$ is strictly less than one full block of size $b^n \le bV$. Hence
$$ R < bV. $$
Lower bound: $R \ge (b-2)V$
We estimate $R/V$ from below.
Write
$$ \frac{R}{V} = \frac{v_{n-1} b^n}{V} + \frac{x}{V}. $$
We bound the second term using $V \ge v_{n-1} b^{n-1}$:
$$ \frac{x}{V} < \frac{b^n}{v_{n-1} b^{n-1}} = \frac{b}{v_{n-1}} \le 2, $$
since $v_{n-1} \ge b/2$.
Now bound the first term from below using $V < (v_{n-1}+1)b^{n-1}$:
$$ \frac{v_{n-1} b^n}{V} > \frac{v_{n-1} b^n}{(v_{n-1}+1)b^{n-1}} = b \cdot \frac{v_{n-1}}{v_{n-1}+1}. $$
Using $v_{n-1} \ge b/2$,
$$ \frac{v_{n-1}}{v_{n-1}+1} \ge \frac{b/2}{b/2 + 1} = \frac{b}{b+2}. $$
Hence
$$ \frac{v_{n-1} b^n}{V} \ge \frac{b^2}{b+2} = b - \frac{2b}{b+2} \ge b - 2. $$
Combining both parts,
$$ \frac{R}{V} \ge \left(b-2\right) + 0 - \text{(at most a small overcount)} \ge b-2, $$
and the previous estimate shows the additive error from $x/V$ cannot push the ratio below $b-2$ because the leading term already exceeds $b-2$ by a margin that dominates the p