I'm currently working on an exercise in The Art Of Computer Programming, Vol. 1 relating the algorithm for computing $\log_{10} x$ presented in the Mathematical Preliminaries.
The algorithm is simple; here is how it works in the words of Knuth:
We will show how to calculate $\log_{10} x$ and to express the answer in the binary system, as $$\log_{10} x = n+ b_1/2 + b_2/4 + b_3/8 + \cdots$$ First we shift the decimal point of $x$ to the left or to the right so that we have $1 \leq x/10^n < 10$; this determines the integer part, $n$. To obtain $b_1$, $b_2$, $\dots$, we now set $x_0 = x/10^n$ and, for $k \geq 1$, $$\begin {array}{l l}b_k = 0, \quad x_k = x_{k-1}^2 & \quad \text{if $x_{k-1}^2 < 10$} \\ b_k = 1, \quad x_k = x_{k-1}^2/10, & \quad \text{if $x_{k-1} \geq 10$} \end{array} \qquad \textit{Eqs. (1)}$$The validity of this procedure follows from the fact that $$1 \leq x_k = x^{2^k}/10^{2^k(n+b_1/2+b_2/4+\cdots+b_k/2^k)} < 10$$ for $k = 0,1,2,\dots$ as is easily proved by induction. In practice, of course, we must work with only finite accuracy, so we cannot set $x_k = x_{k-1}^2$ exactly. Instead, we set $x_k = x_{k-1}^2$ rounded or truncated to a certain number of decimal places.
What I don't understand is part of the claim of the exercise mentioned above, which is:
Considered 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) \leq 10^n x_0' \leq x(1+\epsilon)$; and in the determination of $x_k'$ by Eqs. (1), the quantity $y_k$ is used in place of $(x_{k-1}')^2$, where $(x_{k-1}')^2(1-\delta) \leq y_k \leq (x_{k-1}')^2(1+\epsilon)$ and $1 \leq 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 results of the calculation, show that after $k$ steps we have $$\log_{10} x + 2\log_{10}(1-\delta) - 1/2^k < \log' x \leq \log_{10} x + 2\log_{10}(1 + \epsilon)$$
The fact is that I could easily prove the inequality and solve the exercise, but I still can't understand what $\delta$ and $\epsilon$ really are. Supposedly they represent relative computational errors for the rounding/truncation process, but even then I understand only partially.
I's true, generally speaking, that $a' = a(1+\epsilon)$, where $a, a' \in \mathbb{Q}$ are respectively a finite value and its approximation to a certain number of figues, and $\epsilon$ is a relative error defined as $\frac{a' - a}{a}$. Then, assuming $1 \leq a < 10$, $\epsilon$ must be always smaller or equal to the nominator, that is the absolute error, which has a maximum, and it depends on the number of figures of the approximation: this maximum, in the case of application of the round half up approximation on a 4-significant-figures number, is exactly $0.0005$.
Now, since in this case the absolute error can also have negative values (down to $-0.0005$, as for the example), we can make up a relation such as $a(1-\epsilon) \leq a' \leq a(1+\epsilon)$, quite similar to that of Knuth's: $x(1-\delta) \leq 10^n x_0' \leq x(1+\epsilon)$. The only true difference is to be found in $\delta$: what is $\delta$? As for the definition above, it must be equal to the upper relative error, that is $\epsilon$. The funny thing here is that Knuth doesn't treat his $\epsilon$ as an upper bound, but as the lower one, whereas $\delta$ is the upper relative error.
What does all that mean? Does even a lower round-off error exist? If it was so, should it be 0? But if we take $\epsilon = 0$ the inequality above does not yield correct results anymore! Knuth in fact says in his example for $\log_{10} 2$ that "the error in the value of the logarithm is guaranteed to be less than 0.00044", and this is true only if we take $\epsilon = 0.0005$, that is the upper bound.
Am I missing something, perhaps?
