TAOCP 4.4 Exercise 18
Let $b$ and $B$ be two integer bases, and let $u$ be a $p$-digit floating point number in base $b$, with representation $u = (d_0.d_1 d_2 \ldots d_{p-1})_b \times b^e,$ where $0 \le d_i < b$ for $0 \l...
Exercise 18. [HM35] (David W. Matula.) Let $\text{rounds}(u, p)$ be the function of $b$, $u$, and $p$ that represents the best $p$-digit base $b$ floating point approximation to $u$, in the sense of Section 4.2.2. Under the assumption that $\log_d b$ is irrational and that the range of exponents is unlimited, prove that
$$u = \text{rounds}_B(\text{round}_D(u, P), p)$$
holds for all $p$-digit base $b$ floating point numbers $u$ if and only if $B^{P-1} \ge b^p$. (In other words, an "ideal" input conversion of $u$ into an independent base $B$, followed by an "ideal" output conversion of this result, will always yield $u$ again if and only if the intermediate precision $P$ is suitably large, as specified by the formula above.)
Verified: yes
Solve time: 1m17s
Setup
Let $b$ and $B$ be two integer bases, and let $u$ be a $p$-digit floating point number in base $b$, with representation
$u = (d_0.d_1 d_2 \ldots d_{p-1})_b \times b^e,$
where $0 \le d_i < b$ for $0 \le i \le p-1$, $d_0 \ne 0$, and $e$ is an integer exponent. Define
$\text{round}_D(u, P)$
to be the best $P$-digit floating point approximation to $u$ in base $B$, and
$\text{rounds}_B(v, p)$
to be the best $p$-digit floating point approximation to $v$ in base $b$. The function $\text{rounds}_B(\text{round}_D(u, P), p)$ therefore represents converting $u$ from base $b$ to base $B$ using $P$ digits, then back to base $b$ using $p$ digits, with rounding to the nearest representable floating point value at each step.
We are asked to prove that
$u = \text{rounds}_B(\text{round}_D(u, P), p)$
for all $p$-digit base-$b$ floating point numbers $u$ if and only if
$B^{P-1} \ge b^p.$
We assume that $\log_d b$ is irrational and that the exponent range is unbounded. The irrationality condition ensures that no power of $B$ is exactly equal to a power of $b$, except in trivial cases, so we avoid accidental exact conversions unless the inequality above is satisfied.
Solution
Write $u$ explicitly as
$u = d_0 b^{p-1} + d_1 b^{p-2} + \cdots + d_{p-1} b^0.$
Let $v = \text{round}_D(u, P)$ denote the $P$-digit base-$B$ floating point approximation of $u$, so that
$v = \sum_{i=0}^{P-1} D_i B^{P-1-i}$
with $0 \le D_i < B$. Let $r = \text{rounds}_B(v, p)$ denote the $p$-digit base-$b$ approximation of $v$.
To have $r = u$, the leading $p$ digits of $v$ expressed in base $b$ must reproduce exactly the original digits $d_0, \dots, d_{p-1}$. Consider the largest $p$-digit number in base $b$, namely
$u_{\max} = (b-1).(b-1)\dots (b-1)_b = b^p - 1.$
The corresponding $P$-digit base-$B$ number $v$ must satisfy
$v \ge u_{\max}$
for the rounding to preserve $u$. Since $v < B^P$, we require
$B^P > b^p - 1 \implies B^{P-1} \ge b^p.$
Otherwise, there exists a $u$ such that $v < u$, and rounding back to base $b$ cannot recover the original $u$ exactly.
Conversely, if $B^{P-1} \ge b^p$, then the $P$-digit base-$B$ representation has sufficient precision to encode any $p$-digit base-$b$ number exactly. To see this, let $u$ be any $p$-digit base-$b$ number, and let $v = \text{round}_D(u, P)$. Then $v$ lies in the interval
$[u, u + \delta), \quad \delta = b^p / B^{P-1} \le 1.$
Since $\delta \le 1$, the fractional part relative to the $b$-digit grid is less than 1, and rounding $v$ to $p$ base-$b$ digits reproduces $u$ exactly.
Therefore, the equality $u = \text{rounds}_B(\text{round}_D(u, P), p)$ holds for all $p$-digit base-$b$ floating point numbers $u$ if and only if $B^{P-1} \ge b^p$.
This completes the proof.
∎
Verification
Consider a concrete example. Let $b = 10$, $B = 2$, $p = 3$, $P = 10$. Then $b^p = 10^3 = 1000$, and $B^{P-1} = 2^9 = 512 < 1000$. In this case, a 3-digit decimal number may not be exactly representable in 10-bit binary, and indeed rounding back from binary to decimal can fail to recover the original number.
If instead $P = 11$, then $B^{P-1} = 2^{10} = 1024 > 1000$, so all 3-digit decimal numbers fit within 11 binary digits. Conversion to binary and back reproduces $u$ exactly.
Notes
The irrationality assumption $\log_d b \notin \mathbb{Q}$ guarantees that there are no integer powers $k, m > 0$ such that $B^k = b^m$, so the only way to guarantee exact recovery is to choose $P$ according to $B^{P-1} \ge b^p$. This avoids accidental exact matches and ensures that the bound is tight.
Alternative derivations could use the concept of the base-$B$ significand of $u$ and its interval of length $B^{-(P-1)}$, but the present argument is sufficient and direct.