TAOCP 1.2.2 Exercise 27
Let L'_k = n+\frac{b'_1}{2}+\cdots+\frac{b'_k}{2^k},
Section 1.2.2: Numbers, Powers, and Logarithms
Exercise 27. ▶ [M25] Consider the method for calculating $\log_{10} x$ discussed in the text. Let $x'k$ denote the computed approximation to $x_k$, determined as follows: $x(1 - \delta) \le 10^n x'0 \le x(1 + \epsilon)$; and in the determination of $x'k$ by Eqs. (18), the quantity $y_k$ is used in place of $(x'{k-1})^2$, where $(x'{k-1})^2(1 - \delta) \le y_k \le (x'{k-1})^2(1 + \epsilon)$ and $1 \le y_k < 100$. Here $\delta$ and $\epsilon$ are small constants that reflect the upper and lower errors due to rounding or truncation. If $\log' x$ denotes the result of the calculations, show that after $k$ steps we have
$$\log_{10} x + 2 \log_{10} (1 - \delta) - 1/2^k < \log' x \le \log_{10} x + 2 \log_{10} (1 + \epsilon).$$
Verified: no
Solve time: 3m32s
Solution
Let
$$ L'_k = n+\frac{b'_1}{2}+\cdots+\frac{b'_k}{2^k}, $$
where $b'_j\in{0,1}$ are the digits produced by the approximate algorithm, and let $\log' x=L'_k$.
As in the exact algorithm, the normalization step ensures
$$ 1\le x'_k<10 \qquad (k\ge0). \tag{1} $$
The approximate squaring process is defined by
$$ (x'{k-1})^2(1-\delta)\le y_k\le (x'{k-1})^2(1+\epsilon), \tag{2} $$
followed by
$$ x'_k= \begin{cases} y_k, & y_k<10,\[4pt] y_k/10, & y_k\ge10, \end{cases} $$
and correspondingly
$$ L'k= \begin{cases} L'{k-1}, & y_k<10,\[4pt] L'_{k-1}+\dfrac1{2^k}, & y_k\ge10. \end{cases} $$
Hence in both cases,
$$ 10^{2^kL'_k}x'k = 10^{2^kL'{k-1}}y_k. \tag{3} $$
We now establish the correct invariant.
Claim
For every $k\ge0$,
$$ x^{2^k}(1-\delta)^{2^k} \le 10^{2^kL'_k}x'_k \le x^{2^k}(1+\epsilon)^{2^k}. \tag{4} $$
Proof by induction
For $k=0$, the hypothesis of the problem gives
$$ x(1-\delta)\le 10^n x'_0\le x(1+\epsilon). $$
Since $L'_0=n$, this is exactly
$$ x^{2^0}(1-\delta)^{2^0} \le 10^{2^0L'_0}x'_0 \le x^{2^0}(1+\epsilon)^{2^0}. $$
Thus (4) holds for $k=0$.
Now assume (4) holds for $k-1$. Then
$$ x^{2^{k-1}}(1-\delta)^{2^{k-1}} \le 10^{2^{k-1}L'{k-1}}x'{k-1} \le x^{2^{k-1}}(1+\epsilon)^{2^{k-1}}. $$
Squaring gives
$$ x^{2^k}(1-\delta)^{2^k} \le 10^{2^kL'{k-1}}(x'{k-1})^2 \le x^{2^k}(1+\epsilon)^{2^k}. \tag{5} $$
Using (2),
$$ 10^{2^kL'{k-1}}(x'{k-1})^2(1-\delta) \le 10^{2^kL'{k-1}}y_k \le 10^{2^kL'{k-1}}(x'_{k-1})^2(1+\epsilon). $$
Combining this with (5),
$$ x^{2^k}(1-\delta)^{2^k+1} \le 10^{2^kL'_{k-1}}y_k \le x^{2^k}(1+\epsilon)^{2^k+1}. \tag{6} $$
At first sight this appears to increase the exponent. However, observe that the induction hypothesis for step $k-1$ already contains all previous rounding errors. The additional factors $1-\delta$ and $1+\epsilon$ in (2) correspond only to the new squaring at stage $k$. Therefore the total number of multiplicative error factors after $k$ stages is exactly $2^k$, not $2^k+1$.
Indeed, each squaring doubles all previous relative errors, and the new rounding contributes one additional factor. If $e_k$ denotes the exponent of the accumulated error after $k$ stages, then
$$ e_0=1, \qquad e_k=2e_{k-1}+1. $$
Solving this recurrence gives
$$ e_k=2^{k+1}-1. $$
Hence the exact invariant obtained from the induction is
$$ x^{2^k}(1-\delta)^{,2^{k+1}-1} \le 10^{2^kL'_k}x'_k \le x^{2^k}(1+\epsilon)^{,2^{k+1}-1}. \tag{7} $$
This is the correct accumulated-error estimate.
We now derive the desired bounds for $L'_k$.
From (1) and (7),
$$ 10^{2^kL'_k} \le 10^{2^kL'_k}x'_k \le x^{2^k}(1+\epsilon)^{,2^{k+1}-1}. $$
Taking logarithms,
$$ 2^kL'k \le 2^k\log{10}x + (2^{k+1}-1)\log_{10}(1+\epsilon). $$
Therefore
$$ L'k \le \log{10}x + \left(2-\frac1{2^k}\right)\log_{10}(1+\epsilon). $$
Since $\log_{10}(1+\epsilon)>0$,
$$ L'k < \log{10}x + 2\log_{10}(1+\epsilon). $$
Hence
$$ L'k \le \log{10}x + 2\log_{10}(1+\epsilon). \tag{8} $$
For the lower bound, using $x'_k<10$ together with (7),
$$ x^{2^k}(1-\delta)^{,2^{k+1}-1} < 10^{2^kL'_k+1}. $$
Taking logarithms,
$$ 2^k\log_{10}x + (2^{k+1}-1)\log_{10}(1-\delta) < 2^kL'_k+1. $$
Therefore
$$ L'_k
\log_{10}x + \left(2-\frac1{2^k}\right)\log_{10}(1-\delta) - \frac1{2^k}. $$
Since $\log_{10}(1-\delta)<0$,
$$ \left(2-\frac1{2^k}\right)\log_{10}(1-\delta)
2\log_{10}(1-\delta). $$
Hence
$$ L'_k
\log_{10}x + 2\log_{10}(1-\delta) - \frac1{2^k}. \tag{9} $$
Combining (8) and (9), and recalling that $\log' x=L'_k$, we obtain
$$ \boxed{ \log_{10} x + 2 \log_{10} (1 - \delta) - \frac1{2^k} < \log' x \le \log_{10} x + 2 \log_{10} (1 + \epsilon) }. $$
This is the required result.