TAOCP 4.4 Exercise 3
We generalize Method 2a by introducing a stopping criterion based on the desired precision $\epsilon$.
Exercise 3. ▶ [**] [25] (D. Taranto.) When fractions are being converted, there is no obvious way to decide how many digits to give in the answer. Design a simple generalization of Method 2a that, given two positive radix-$b$ fractions $u$ and $v$ between 0 and 1, converts $u$ to a rounded radix-$B$ equivalent $U$ that has just enough places $M$ to the right of the radix
point to ensure that $|U - u| < \epsilon$. (In particular if $u$ is a multiple of $b^{-m}$ and $v = b^{-m}/2$, the value of $U$ will have just enough digits so that $u$ can be recomputed exactly, given $U$ and $m$. Note that $M$ might be zero; for example, if $\epsilon \le \frac{1}{2}$ and $u > 1 - r$, the proper answer is $U = 1$.)
Verified: yes
Solve time: 3m29s
We generalize Method 2a by introducing a stopping criterion based on the desired precision $\epsilon$. Let $u \in [0,1)$ be the radix-$b$ fraction to convert, and let $U = (0.U_{-1}U_{-2}\ldots U_{-M})_B$ be its radix-$B$ approximation. Initialize $x \leftarrow u$ and $M \leftarrow 0$. Then repeatedly compute
$U_{-(M+1)} \leftarrow \lfloor B x \rfloor, \qquad x \leftarrow {B x}, \qquad M \leftarrow M+1,$
stopping when $x < \epsilon$. This ensures that the truncated remainder is less than $\epsilon$, so $|U - u| < \epsilon$. If $u$ is an exact multiple of $b^{-m}$ and $v = b^{-m}/2$, then taking $\epsilon = v$ guarantees that the computed $U$ contains exactly enough digits to reconstruct $u$ exactly, because the final fractional part is less than half the unit in the last place of $u$. If $\epsilon$ is large relative to $u$, it is possible that $M = 0$, yielding $U = 0$ or $U = 1$ when rounding up is required.
Each iteration uses two replacements ($U_{-(M+1)} \leftarrow \lfloor B x \rfloor$ and $x \leftarrow {B x}$), so the total number of replacements is $2M$. This completes the proof.
∎