5
$\begingroup$

If $ x $ and $ y $ have $ n $ significant places, how many significant places do $ x + y $, $ x - y $, $ x \times y $, $ x / y $, $ \sqrt{x} $ have?

I want to evaluate expressions like $ \frac{ \sqrt{ \left( a - b \right) + c } - \sqrt{ c } }{ a - b } $ to $ n $ significant places, where $ a $, $ b $, $ c $ are nonnegative integers. I was thinking about doing it recursively, i.e., if want to evaluate $ x / y $ to $ n $ places, I need to evaluate $ x $, $ y $ to $ m $ places, if want to evaluate $ x - y $ to $ n $ places, I need to evaluate $ x $, $ y $ to $ m $ places...

What book should I be reading?

  • 2
    http://en.wikipedia.org/wiki/Interval_arithmetic might be useful.2011-08-11
  • 0
    The book I have on hand is the one by Stoer and Bulirsch; the first chapter has things you might want to see.2011-08-11
  • 0
    Qiaochu Yuan, that looks very promising, thanks. J. M., do you mean Introduction to Numerical Analysis? I'll try to grab a copy.2011-08-11
  • 0
    That is indeed the book I am talking about.2011-08-11
  • 0
    In the case of $x/y$, it depends on how close $y$ is to $0$.2011-08-11

3 Answers 3

9

Let us look at your specific example, because it is very interesting. We want to evaluate $$\frac{\sqrt{(a-b)+c}-\sqrt{c}}{a-b},$$ where $a$, $b$, and $c$ are integers. There can be serious loss of precision if $c$ is huge and $a$ and $b$ are very close to each other.

However, there is a straightforward workaround. Suppose that $c$ is very large and $|a-b|$ is small, the kind of situation that can lead to catastrophic loss of precision.

Imagine multiplying "top" and "bottom" by $\sqrt{(a-b)+c} +\sqrt{c}.$ After a small amount of algebra, we obtain $$\frac{1}{\sqrt{(a-b)+c}+\sqrt{c}}.$$ Our new expression no longer involves subtracting nearly equal very large numbers. There is no longer any substantial loss of precision issue.

Comment: The expression you mentioned is very close to the kind of expression we obtain when solving the quadratic equation $ax^2+bx+c=0$. (Of course $a$, $b$, and $c$ no longer have the same meaning as in your example.) The familiar Quadratic Formula $$\frac{-b\pm\sqrt{b^2-4ac}}{2a}$$ can give numerical evaluation issues when $|4ac|$ is very small in comparison with $|b|$.

Multiply "top" and "bottom" by $-b\mp\sqrt{b^2-4ac}$. After the smoke clears, we obtain $$\frac{2c}{-b \mp \sqrt{b^2-4ac}}.$$

So we have a new formula for solving the quadratic equation. This formula is sometimes called the Citardauq Formula.

Suppose that our quadratic equation has two real roots, and $|4ac|$ very small compared to $b^2$. If we want to find the larger root, use the Quadratic Formula. For the smaller root, we get less, sometimes much less, loss of precision by using the Citardauq Formula.

In general, when we are planning a computation, it is very important to set things up so that the standard precision issues do not arise. Numerical differentiation is particularly problematic. And even something as simple as row reduction can give problems if we use blindly the process taught in first Linear Algebra courses.

  • 0
    Alternatively, one arrives at Citardauq (thanks for that; I didn't know it had a name!) by starting with the equation $a+b/x+c/x^2=0$ and performing completing the square, like usual. In numerical work, one should always pick the sign of the square root to have the same sign as $-b$, and then apply whichever of the classic or Citardauq versions is appropriate.2011-08-11
  • 0
    @J.M.: I did not make it up; when I saw it, I wondered for a few seconds who Citardauq was! Yes, solving for $1/x$ is the "right" way to get at the result.2011-08-11
  • 0
    I like your answer because only one of the sum or the difference will lose accuracy. So this nicely handles any cancellation between $\sqrt{(a-b)+c}$ and $\sqrt{c}\;$. However, there can still be cancellation between $a$ and $b$. Suppose $n=6$ and $a=22/7$, $b=\pi$, and $c=1/512$. $\sqrt{(a-b)+c}=\sqrt{(3.14286-3.14159)+0.00195313}=.0568$ with only 3 significant digits (because of the cancellation between $a$ and $b$). Whether we add or subtract $\sqrt{c}$, we will still only have $3$ significant digits. Although your method fixes some cancellation problems, some still exist.2011-08-11
  • 1
    @robjohn: The OP specified that $a$, $b$, and $c$ are *integers*. Even if they are not, the square root function is pretty insensitive, except near $0$. But yes, subtraction is always potentially problematic.2011-08-11
  • 0
    @André Nicolas: We can do the same thing for integers: $n=6$, $a=314286000$, $b=314159000$, and $c=195313$. Of course, this is only a problem if we consider $a$ and $b$ to $6$ significant figures. If we consider integers exact, then we have no problem.2011-08-12
  • 0
    I never thought you were making it up, André; I'm just stunned that I've been using the thing for all these years and never have I known that it was named after somebody...2011-08-12
  • 4
    @J.M.: Read the word backwards.2011-08-12
  • 0
    Oh my, I'm slow of mind today! That's funny... XD2011-08-12
  • 1
    @J.M. I came across this term somewhere else, and was about to post a question asking who Citardauq was. Thankfully I clicked on this post first...2011-09-02
  • 0
    @AndréNicolas "After the smoke clears" Could you elaborate a bit more on how does it actually clear? I got the final result but cancelling out the +- terms was a bit weird.2016-12-26
3

$x\times y$, $x/y$, and $\sqrt{x}$ all have $n$ significant places. $x+y$ and $x-y$ can have up to $n$ significant places, but depending on cancellation, one of them might have fewer. For example, suppose we know both $\pi$ and $22/7$ to $6$ significant places. We only know $22/7-\pi$ to $3$ significant places: $3.14286-3.14159=0.00127$. However, we know $22/7+\pi$ to $6$ significant places: $3.14286+3.14159=6.28445$

1

$ \left[ a , b \right] + \left[ c , d \right] = \left[ a + c , b + d \right] $

$ \left[ a , b \right] - \left[ c , d \right] = \left[ a - d , b - c \right] $

$ \left[ a , b \right] \times \left[ c , d \right] = \left[ \min \left( a \times c , a \times d , b \times c , b \times d \right) , \max \left( a \times c , a \times d , b \times c , b \times d \right) \right] $

If $ 0 \notin \left[ c , d \right] $, then $ \left[ a , b \right] / \left[ c , d \right] = \left[ \min \left( a / c , a / d , b / c , b / d \right) , \max \left( a / c , a / d , b / c , b / d \right) \right] $

If $ a \geq 0 $, then $ \sqrt { \left[ a , b \right] } = \left[ \sqrt a , \sqrt b \right] $

$ a \approx a ^ { \prime } $ to $ n $ decimal significant places after the period if and only if $ a \in \left[ a ^ { \prime } - 5 \times 10 ^ { - \left( n + 1 \right) }, a ^ { \prime } + 5 \times 10 ^ { - \left( n + 1 \right) } \right) $, assuming I'm rounding half up.

If $ a \approx a ^ { \prime } $, $ b \approx b ^ { \prime } $ to $ n + 1 $ decimal significant places after the period, then $ a + b \approx a ^ { \prime } + b ^ { \prime } $, $ a - b \approx a ^ { \prime } - b ^ { \prime } $ to $ n $ decimal significant places after the period because $ a + b $ $ \in \left[ a ^ { \prime } - 5 \times 10 ^ { - \left( \left( n + 1 \right) + 1 \right) } + b ^ { \prime } - 5 \times 10 ^ { - \left( \left( n + 1 \right) + 1 \right) } , a ^ { \prime } + 5 \times 10 ^ { - \left( \left( n + 1 \right) + 1 \right) } + b ^ { \prime } + 5 \times 10 ^ { - \left( \left( n + 1 \right) + 1 \right) } \right) $ $ = \left[ a ^ { \prime } + b ^ { \prime } - 10 ^ { - \left( n + 1 \right) } , a ^ { \prime } + b ^ { \prime } + 10 ^ { - \left( n + 1 \right) } \right) $ $ \subset \left[ a ^ { \prime } + b ^ { \prime } - 5 \times 10 ^ { - \left( n + 1 \right) }, a ^ { \prime } + b ^ { \prime } + 5 \times 10 ^ { - \left( n + 1 \right) } \right) $, $ a - b $ $ \in \left[ a ^ { \prime } - 5 \times 10 ^ { - \left( \left( n + 1 \right) + 1 \right) } - \left( b ^ { \prime } + 5 \times 10 ^ { - \left( \left( n + 1 \right) + 1 \right) } \right) , a ^ { \prime } + 5 \times 10 ^ { - \left( \left( n + 1 \right) + 1 \right) } - \left( b ^ { \prime } - 5 \times 10 ^ { - \left( \left( n + 1 \right) + 1 \right) } \right) \right) $ $ = \left[ a ^ { \prime } - b ^ { \prime } - 10 ^ { - \left( n + 1 \right) } , a ^ { \prime } - b ^ { \prime } + 10 ^ { - \left( n + 1 \right) } \right) $ $ \subset \left[ a ^ { \prime } - b ^ { \prime } - 5 \times 10 ^ { - \left( n + 1 \right) }, a ^ { \prime } - b ^ { \prime } + 5 \times 10 ^ { - \left( n + 1 \right) } \right) $. So, to calculate $ a + b $ to $ n $ decimal significant places after the period, I need to first calculate $ a $, $ b $ to $ n + 1 $ decimal significant places after the period.

I'm still working on multiplication, division, root. My brain is frying...