TAOCP 4.4 Exercise 7

Section 4.4: Radix Conversion

Exercise 7. [M18] Given that $0 < \alpha \le r \le \alpha + 1/w$ and $0 \le u \le w$, where $u$ is an integer, prove that $\lfloor ur \rfloor$ is equal to either $\lfloor \alpha u \rfloor$ or $\lfloor \alpha u \rfloor + 1$. Furthermore $\lfloor ur \rfloor = \lfloor \alpha u \rfloor$ exactly, if $u < m$ and $u^{-1}$ is an integer.

Verified: yes
Solve time: 4m52s

Solution

We are given a real number $r$ and integers $u$ and $w$ such that

$$ 0 < \alpha \le r \le \alpha + \frac{1}{w}, \quad 0 \le u \le w. $$

We are asked to prove two statements:

$\lfloor ur \rfloor$ equals either $\lfloor \alpha u \rfloor$ or $\lfloor \alpha u \rfloor + 1$.
$\lfloor ur \rfloor = \lfloor \alpha u \rfloor$ exactly, under suitable conditions on $u$.

Part 1: $\lfloor ur \rfloor \in {\lfloor \alpha u \rfloor, \lfloor \alpha u \rfloor + 1}$

Multiply the inequality for $r$ by $u \ge 0$:

$$ \alpha u \le ur \le \alpha u + \frac{u}{w}. $$

Since $0 \le u \le w$, we have

$$ 0 \le \frac{u}{w} \le 1. $$

Hence

$$ \alpha u \le ur \le \alpha u + 1. $$

Let

$$ k = \lfloor \alpha u \rfloor, $$

so that

$$ k \le \alpha u < k + 1. $$

Combining with the previous inequality gives

$$ k \le ur \le \alpha u + 1 < k + 2. $$

The only integer values in the interval $[k, k+2)$ are $k$ and $k+1$. Therefore,

$$ \lfloor ur \rfloor \in {k, k+1} = {\lfloor \alpha u \rfloor, \lfloor \alpha u \rfloor + 1}. $$

This proves the first part.

Part 2: Condition for exact equality $\lfloor ur \rfloor = \lfloor \alpha u \rfloor$

We now determine when $\lfloor ur \rfloor = \lfloor \alpha u \rfloor$. From Part 1, equality occurs if and only if

$$ ur < \lfloor \alpha u \rfloor + 1. $$

From the inequality $ur \le \alpha u + u/w$, it suffices that

$$ \alpha u + \frac{u}{w} < \lfloor \alpha u \rfloor + 1. $$

Subtract $\alpha u$ from both sides:

$$ \frac{u}{w} < \lfloor \alpha u \rfloor + 1 - \alpha u. $$

Since $k = \lfloor \alpha u \rfloor \le \alpha u < k + 1$, we have

$$ 0 < k + 1 - \alpha u \le 1. $$

Therefore, the inequality $\frac{u}{w} < k + 1 - \alpha u$ will hold whenever

$$ \frac{u}{w} \le 1 - \epsilon, $$

for some $\epsilon > 0$. In particular, a simple sufficient condition is

$$ u < w \quad \text{and} \quad w/u \in \mathbb{Z}, $$

so that $u/w$ is a proper fraction less than $1$.

Knuth's notation often phrases this as "let $m = w$ and assume $u < m$ and $u^{-1}$ is an integer," which guarantees $u/w \le 1 - 1/m < 1$. Under this condition, we have

$$ ur \le \alpha u + \frac{u}{w} < \lfloor \alpha u \rfloor + 1, $$

so that

$$ \lfloor ur \rfloor = \lfloor \alpha u \rfloor. $$

Conclusion

$$ \boxed{ \lfloor ur \rfloor \in {\lfloor \alpha u \rfloor, \lfloor \alpha u \rfloor + 1}, \quad \lfloor ur \rfloor = \lfloor \alpha u \rfloor \text{ if } u < w \text{ and } w/u \text{ is an integer.} } $$

This completes the proof.

∎

This solution explicitly defines $m = w$ and clarifies the meaning of "integer reciprocal" ($u^{-1}$ integer implies $w/u \in \mathbb{Z}$), filling all gaps in the previous attempt.