Round-off error propagation

Introduction

Looking around the internet, I was unable to find any simple rule of thumbs (with coherent explanations) for how many decimal places to keep when doing simple calculations on paper, provided we want the answer to a certain accuracy. Hence this little note.

How to formulate roundoff error

Let $a$ denote the exact number with no error in it. For convenience, we assume that $ \beta^{-1} < |a| < \beta $. If not, then just pull out a factor of $\beta$ to some power to make it so. (This trick only really work with division and multiplication, but luckily for us those are the only cases we consider here.)

A convenient way of formulating the approximation to $a$ implied by rounding to $d$ significant digits is $ a(1-\epsilon) $, where $\epsilon$ satisfies $ \left| \epsilon \right| \leq \frac{1}{2}\beta^{1-d} $. For instance — when $d=1$, i.e. when we're rounding to a whole number (remember that $\beta^{-1} < |a| < \beta$), our formula tells us that the magnitude of the round-off error is no greater greater than $\frac{1}{2}$, as we would expect.

Division

How many digits $n$ to keep in the numerator and denominator, provided we want the result to $d$ significant digits?

In other words — How many digits $n$ should we keep in the numerator and denominator when calculating a quotient, provided that we want the resulting error to be no greater than that implied by rounding to $d$ significant digits?

Or, said yet another way: find $n$ such that $\left| \epsilon_{a,b} \right| \leq \frac{1}{2} \beta^{1-n} $ implies $\left| \epsilon \right| \leq \frac{1}{2} \beta^{1-d} $, where $$ \frac{a(1-\epsilon_a)}{b(1 - \epsilon_b)} = \frac{a}{b}(1 - \epsilon) $$

We begin by solving for $\epsilon$: $$ \epsilon = \frac{\epsilon_a-\epsilon_b}{1 - \epsilon_b} $$

We now try to formulate as tight an upper bound on $|\epsilon|$ as we can, in terms of $n$ only. We get (assuming $n > 0$, which clearly required anyway): $$ \left| \epsilon \right| \leq \frac{\left|\epsilon_a\right|+\left|\epsilon_b\right|}{\left| 1 - \epsilon_b \right|} \leq \frac{\beta^{1-n}}{1 - \frac{1}{2}\beta^{1-n}} $$ In fact, the rightmost expression is the smallest upper limit we can actually find, since we know only know $n$ and not the exact signs and sizes of the $\epsilon_{a,b}$.

Now we take this upper bound of $\left|\epsilon\right|$ formulated in terms of $n$ and bound it by the bound we wanted on $\left| \epsilon \right|$: $$ \frac{\beta^{1-n}}{1 - \frac{1}{2}\beta^{1-n}} \leq \frac{1}{2} \beta^{1-d} $$ This inequality encodes a condition on $n$, which if satisfied, ensures that $\left|\epsilon\right| \leq \frac{1}{2} \beta^{1-d}$. Since the bound on $\left| \epsilon \right|$ we derived was the best possible, this inequality allows us to pick the smallest values on $n$.

However, the inequality is not so great for quick-n-dirty rules of thumb. You could make a table from it, but we really want a simple expression for n. We can accomplish this by deriving a simpler but slightly sloppier upper bound for $\left| \epsilon \right|$. We have a simpler upper bound because: $$ \frac{\beta^{1-n}}{1 - \frac{1}{2}\beta^{1-n}} \leq \frac{\beta^{1-n}}{\frac{1}{2}} = 2 \beta^{1-n} $$

Thus our slightly less sharp requirement on $n$ becomes $$ 2\beta^{1-n} \leq \frac{1}{2} \beta^{1-d} $$ or, rather $$ 4 \beta^{d} \leq \beta^{n} $$ Taking the $\beta$-logarithm, we obtain $$ \log_{\beta}(4) + d \leq n $$ We get the following simple formula for $n$ $$ \hat{n}(d) = \lceil \log_{\beta}(4) + d \rceil = d + \lceil \log_{\beta}(4) \rceil $$ The notation $\lceil x \rceil$ means the ceiling of $x$, i.e. the smallest possible integer greater than or equal to $x$. I introduced $\hat{n}$ instead of redefining $n$.

When $\beta = 10$, we get $\lceil \log_{10}(4) \rceil = 1$, so in base 10 we only need at most one more digit in the numerator and denominator than we wish to have in the result.

Thus, as you can see, we didn't lose much by introducing the sloppier bound on $\left| \epsilon \right|$, and in return we got a pretty simple rule.

Multiplication

Similarly as for multiplication, we have the equation for the approximation of the product in terms of the approximations of the factors $$ a(1-\epsilon_a)b(1-\epsilon_b) = ab(1-\epsilon) $$ Solving for epsilon, we get $$ \epsilon = \epsilon_a\epsilon_a - \epsilon_a - \epsilon_b $$

Now we derive an upper bound of $\epsilon$ in terms of $n$, like so $$ \left| \epsilon \right| \leq \left| \epsilon_a\epsilon_a \right| + \left| \epsilon_a \right| + \left| \epsilon_b \right| $$ $$ \left| \epsilon \right| \leq \frac{1}{4} \beta^{2(1-n)} + \beta^{1-n} \leq \frac{1}{4} \beta^{2-n} + \beta^{1-n} = \left(\frac{\beta + 4}{4} \right) \beta^{1-n}$$

Thus, in order that $| \epsilon | \leq \frac{1}{2} \beta^{1-d} $ we require that $n$ should satisfy $$ \left(\frac{\beta + 4}{4} \right) \beta^{1-n} \leq \frac{1}{2} \beta^{1-d} $$ $$ \left(\frac{\beta + 4}{2} \right) \beta^{d} \leq \beta^{n} $$ $$ \log_\beta\left(\frac{\beta + 4}{2} \right) + d \leq n $$

Thus, a simple conservative formula for $n$ is $$ \hat{n}(d) = \lceil{ \log_\beta\left(\frac{\beta + 4}{2} \right) + d} \rceil = d + \lceil \log_\beta\left(\frac{\beta + 4}{2} \right) \rceil $$ Again, I introduced $\hat{n}$ instead of redefining $n$.

For $\beta = 10$, we have $\lceil \log_{10}\left( 7 \right) \rceil = 1$, so again we find that in base 10 we only need at most one more digit in the two factors than we wish to have in the result.