4

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++

Mike Warren
  • 223
  • 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$. – Steven Stadnicki Jan 06 '14 at 03:50
  • But how to "automatically" find a?! – Mike Warren Jan 06 '14 at 04:04
  • 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. – Steven Stadnicki Jan 06 '14 at 04:09

2 Answers2

5

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.

Ross Millikan
  • 374,822
  • 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.xxxxxxx2^{xxxxxxx}$?) – Mike Warren Jan 06 '14 at 02:42
  • 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. – Ross Millikan Jan 06 '14 at 02:43
0

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.

Mike Warren
  • 223