# Upper and lower bound of an approximate computation

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?

There may be two different error bounds because we could use rounding or truncation to get finite-digit representation. If we use rounding, we might have $\epsilon=\delta$ as you suggested. But in case of truncation we'll have $\delta>\epsilon=0$.
As for which is upper bound and which is lower, while formulating the solution, Knuth might have truncation in mind and implied that for given actual error $\sigma$ we have $x_0'=(1-\sigma)x_0$, which would be the case for $\sigma>0$ when truncating. In this case expanding the inequality we'd have $$-\epsilon\le\sigma\le\delta,$$
so that $\epsilon$ would reflect lower error bound and $\delta$ would correspond to upper bound. Although the solution is formulated with truncation in mind, it continues to work for rounding, where $\sigma$ could become negative.
• Right, now I begin to understand; but what inequality did you "expand" to obtain $-\epsilon \leq \sigma \leq \delta$ ? Aug 10, 2014 at 13:12
• The one in exercise: $x(1-\delta) \leq 10^n x_0' \leq x(1+\epsilon)$, taking relation between $x_0'$, $x$ and $x_0$ into account. Aug 10, 2014 at 13:58
• One moment, though. Considering whatever type of rounding (including truncation), the actual error $\sigma$ might be positive as well as negative, so we have in general $x_0' = (1+\sigma)x_0$, which substituted in the inequality as you did, yields $-\delta \leq \sigma \leq \epsilon$. Do you see anything wrong in this? I believe it's an almost natural thinking, without sticking on the configuration of one single type of rounding, as you did with truncation. Don't you think that perhaps $\delta$ would reflect the lower error bound, whereas $\epsilon$ would correspond to the upper bound? Aug 10, 2014 at 22:08
• You're right, even though you didn't make the things quite explicit in your answer: your "matter of choice" means that either $\delta$ or $\epsilon$ might represent the upper bound, or the lower, just depending on the type of rounding one is considering, that is on the sign of $\sigma$. As a matter of fact, the final inequality in the exercise would give incorrect results if you're working with truncation and consider $\delta$ as the lower error bound; if you instead work with "round up" (the opposite of truncation), $\sigma$ is always positive and this time $\delta$ is indeed the lower bound. Aug 11, 2014 at 9:19