TAOCP 4.3.1 Exercise 23

Section 4.3.1: The Classical Algorithms

Exercise 23. [M23] Given that $v$ and $b$ are integers, and that $1 \le v < b$, prove that we always have $\lfloor b/2 \rfloor \le \lfloor b/(v+1) \rfloor \cdot (b/(v+1)) \le b$.

Verified: no
Solve time: 3m15s

---

Solution

Let

$$ u=(u_nu_{n-1}\ldots u_0)b,\qquad v=(v{n-1}v_{n-2}\ldots v_0)_b, $$

with

$$ v_{n-1}\ge \lfloor b/2\rfloor,\qquad u_n=v_{n-1}. $$

Let $q$ be the true quotient digit determined by

$$ q=\left\lfloor \frac{u}{v}\right\rfloor . $$

Since $q$ is a radix-$b$ digit, $q\le b-1$. The problem is therefore to prove that $q\ge b-2$.

Write

$$ v=v_{n-1}b^{,n-1}+w, \qquad 0\le w<b^{,n-1}, $$

and

$$ u=v_{n-1}b^{,n}+t, \qquad 0\le t<b^{,n}. $$

Because $q=\lfloor u/v\rfloor$, it suffices to show that

$$ u\ge (b-2)v. $$

Indeed, this inequality implies

$$ \frac{u}{v}\ge b-2, $$

hence $q\ge b-2$.

Now

$$ \begin{aligned} u-(b-2)v &=v_{n-1}b^{,n}+t-(b-2)(v_{n-1}b^{,n-1}+w) \ &=2v_{n-1}b^{,n-1}+t-(b-2)w. \end{aligned} $$

Since $t\ge0$ and $w<b^{,n-1}$,

$$ u-(b-2)v

2v_{n-1}b^{,n-1}-(b-2)b^{,n-1}. $$

Therefore

$$ u-(b-2)v

\bigl(2v_{n-1}-(b-2)\bigr)b^{,n-1}. $$

The hypothesis $v_{n-1}\ge\lfloor b/2\rfloor$ gives

$$ 2v_{n-1}\ge 2\lfloor b/2\rfloor. $$

If $b=2m$ is even,

$$ 2\lfloor b/2\rfloor=b, $$

hence

$$ 2v_{n-1}-(b-2)\ge b-(b-2)=2. $$

If $b=2m+1$ is odd,

$$ 2\lfloor b/2\rfloor=b-1, $$

hence

$$ 2v_{n-1}-(b-2)\ge (b-1)-(b-2)=1. $$

In either case,

$$ 2v_{n-1}-(b-2)>0. $$

Consequently,

$$ u-(b-2)v>0, $$

so

$$ u>(b-2)v. $$

Therefore

$$ q=\left\lfloor \frac{u}{v}\right\rfloor \ge b-2. $$

Combining this with the trivial bound $q\le b-1$, we obtain

$$ b-2\le q\le b-1. $$

Since $q$ is an integer,

$$ \boxed{q=b-2\ \text{or}\ q=b-1}. $$

This completes the proof.

∎