4
$\begingroup$

As both a programmer and a math student, I am trying to come up with a fool-proof way to handle errors from subtractive cancellation caused by trying to evaluate $x-y$, where x,y are extended (long double) precision floating-point numbers. (Obviously, if x is very close to y, this causes problem.) I found two equivalent forms, ${x^2-y^2\over x+y}$ and $(\sqrt{x}-\sqrt{y})(\sqrt{x}+\sqrt{y})$. I was trying to evaluate regions where either form would work better, as well as the regions where either form might produce the same result, and/or a worse result in comparison to a straight subtraction.


I have tried to do the error-analysis as such:

Let the long double c be defined such that $x-y=c$.Then, ${x^2-y^2\over x+y}=x-y=c$, which rewrites as ${x^2-y^2\over x-y}={x^2-y^2\over c}=x+y$, which means that, if ${x^2-y^2\over x+y}$ does better than x-y, then $|x+y|>1$. Now, we take a look at $(\sqrt{x}-\sqrt{y})(\sqrt{x}+\sqrt{y})=x-y=c$. A rewriting of this yields $\sqrt{x}-\sqrt{y}={c\over \sqrt{x}+\sqrt{y}}$, which means that $\sqrt{x}+\sqrt{y}<1$ for this decomposition to work. (This also poses the additional condition that x,y>0.) It would then follow that $x+y=x-y+2y>1$, or, in other terms, $x-y>1-2y$. Also, $\sqrt{x}+\sqrt{y}<1$ can be rewritten as $\sqrt{x}<1-\sqrt{y}$, or after squaring both sides, $x-y<1-2\sqrt{y}$. This means that $1-2y<1-2\sqrt{y}$, which simplifies to $y>\sqrt{y}$ which returns $y>1$ (this is the only place where it is true....)

So, if y > 1, then the decomposition works better, right? Well, not according to my program, which can be found here: http://ideone.com/amwv9H ; // Disclaimer: It is written in C++

$\endgroup$
3
  • $\begingroup$ This is a case where domain-dependent knowledge is invaluable - as Ross says in his answer, once you've gotten down to 'subtract $y$ from $x$' you're stuck; instead, if you know how $x$ and $y$ are generated, then you can rework that subtraction - for instance, if $x$ is $\sqrt{y^2+a^2}$ for $a\ll y$ then there are much better approximations for $x-y$. $\endgroup$ Jan 6 '14 at 3:50
  • $\begingroup$ But how to "automatically" find a?! $\endgroup$ Jan 6 '14 at 4:04
  • $\begingroup$ There's no way to 'automatically' find $a$. If literally all you have are $x$ and $y$ - if the values are given to you raw - then there's nothing you can do; that's Ross's point. But numbers seldom come 'out of the blue'; usually they're generated by some process. If you know what that process is, then you can 'back up' your subtraction into that process. $\endgroup$ Jan 6 '14 at 4:09
5
$\begingroup$

Once you have $x$ and $y$ and want to subtract them, you won't do better. What is useful is (if $x \approx y$, which is where the problem is) to find some number $a$ that is close to $x,y$ and you can subtract from them analytically. Now you are calculating $(x-a)-(y-a)$. For example, suppose $x=1+10^{-4}$ and $y=1+10^{-8}$. If you just do the subtraction $x-y$, you lose four decimal digits of precision because of the cancellation. If you can do $(x-1)-(y-1)=10^{-4}-10^{-8}$ you don't lose any.

$\endgroup$
2
  • $\begingroup$ Holy crap, why didn't I think of this??? // And, it might be a good idea to then subtract the integer part out of each operand before trying the subtraction?? Plus, will this work for computer-style floating-point numbers (the ones that are represented as $(-1)^{b_0}*1.xxxxxxx*2^{xxxxxxx}$?) $\endgroup$ Jan 6 '14 at 2:42
  • $\begingroup$ Finding the integer part is not the key, as subtracting $0.999$ would do almost as well here. If you already have this $x,y$ as floats, if you now subtract off $1$ you have four or eight decimals that are zero at the low end instead of useful data. That is why I said subtract analytically-you want to calculate $x-a$ and $y-a$. For example, you might want to calculate $e^{-.04}-e^{-.08}$. The first three terms of the Taylor series are $(1-0.04+\frac 12(-0.04)^2)-(1-0.08+\frac 12(-0.08)^2)$ If you cancel the $1$'s before calculating the Taylor series you have solved the problem. $\endgroup$ Jan 6 '14 at 2:43
0
$\begingroup$

I think my error lies in getting from $x<1-\sqrt{y}$ to $x-y<1-2\sqrt{y}$. Since I have already imposed the condition that x,y>0, it would then follow that $x,y\in [0,1]$. I then went from $x-y<1-2\sqrt{y}$ to $y>1$, which contradicts the previous statement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.