# Question on benign and catastrophic cancellations

I am studying theorem 4 in this article (its proof is under theorem 13). From what I have learned, the theorem is helpful when $x$ is small but $1 \oplus x \neq 1$. At the end of theorem 4, it discussed idea of benign cancellation as follow:

The results of this section can be summarized by saying that a guard digit guarantees accuracy when nearby precisely known quantities are subtracted (benign cancellation). Sometimes a formula that gives inaccurate results can be rewritten to have much higher numerical accuracy by using benign cancellation; however, the procedure only works if subtraction is performed using a guard digit. The price of a guard digit is not high, because it merely requires making the adder one bit wider. For a 54 bit double precision adder, the additional cost is less than 2%. For this price, you gain the ability to run many algorithms such as formula (6) for computing the area of a triangle and the expression $\ln(1 + x)$. Although most modern computers have a guard digit, there are a few (such as Cray systems) that do not.

From what I understood, the enhanced formula,$\frac{ln(x+1)}{(1+x)-1}$, helps replacing the catastrophic cancellation with benign cancellation. I assumed $\ln(1+x)$ causes catastrophic cancellation.

My Question: I cannot follow how the catastrophic cancellation was replaced with benign cancellation when we replaced $\frac{ln(x+1)}{x}$ with $\frac{ln(x+1)}{(1+x)-1}$.

Thanks.

The idea is that you have a function that satisfies $f(1+x)=x\,g(x)$ with $g(0)=1\ne0$.

However, in computing $1⊕x$ you may lose precision in $x$ as $\bar x=(1⊕x)⊖1$ will be different by about $\mu=2^{-53}$ in double floating point. This means that the relative error between $x$ and $\bar x$ is $\mu/|x|$ can be arbitrarily high, and thus also the relative error between $f(1+x)$ and $f(1+\bar x)=f(1⊕x)$, seeing that $$f(1⊕x) = \bar x\,g(\bar x)$$ will also exhibit this reduced precision. But one can easily repair most of the damage by dividing out $\bar x$ and multiplying with $x$ as the relative error between $x\,g(\bar x)$ and $x\,g(x)$ has the size $\mu g'(0)/g(0)$, that is, it is small independent of $x$ (for small $x$).

So finally, $\dfrac{x\,f(1+\bar x)}{\bar x}$ is implemented as

(x*f(1+x)) / ((1+x)-1)

• Thank you for your explanation. I have a few questions: (1) I assumed $f(1+x) = \ln(1+x)$ and $g(x) = \frac{\ln(1+x)}{x}$. I thought g(0) is not defined here, but you wrote g(0)= 1. Did I miss something? – Crimson Sep 11 '16 at 13:49
• (2) You wrote we lose precision in $x \oplus 1$.(I also saw it in the documentation for function log1p[1]). Assuming we have a small number, (e.g. $2*10^{-14}, 3*10^{-14}$), which still satisfies $x \oplus 1$ in a double precision machine. I don't see how I lose precision by adding 1 to it. I wrote it on paper and I also enter in MATLAB, It can add them up accurately in double precision IEEE standards for floating point number. [1] mathworks.com/help/matlab/ref/log1p.html – Crimson Sep 11 '16 at 13:49
• The example is too simple. Say you have 4 decimal digits precision and $x=1.234\cdot 10^{-3}$, then $1+x=1.001234$ and $1⊕x=1.001$, thus losing 3 digits in $\bar x=1.000\cdot 10^{-3}$. – Lutz Lehmann Sep 11 '16 at 15:28
• (1+2e-13)-1 gives 2.000621890374532e-13 which is a rather large loss of precision, from 16 places to 4. The logarithm values confirm this, as log(1+2e-13)=2.000621890374332e-13 while log1p(2e-13)=1.9999999999998001e-13. – Lutz Lehmann Sep 11 '16 at 16:17
• Yes, and only that counts. You lose the digits of $x$ in the evaluation of $1+x$, but of course that value is as exact as representable. The cancellation or loss of precision effect only occurs in the, for this example similar, evaluations of $(1+x)-1$ or $\log(1+x)$. – Lutz Lehmann Sep 11 '16 at 16:35