1

The formula: $f(x)=\sqrt {x-1} - \sqrt{x-2}$ is used to compute a function $f$. Suggest a more accurate way to compute the same function.

I simply do not know how to start with this question... I made the attempt employing the fixed-point iteration, I cannot see how the fixed-point iteration may help at all.

QmmmmLiu
  • 211
  • 3
    Note that we can write

    $$\sqrt{x-1}-\sqrt{x-2}=\left(\sqrt{x-1}-\sqrt{x-2}\right)\left(\frac{\sqrt{x-1}+\sqrt{x-2}}{\sqrt{x-1}+\sqrt{x-2}}\right)=\frac{1}{\sqrt{x-1}+\sqrt{x-2}}$$

     – Mark Viola Oct 27 '15 at 03:52
  • Thanks for the answer. I also wrote down this alternative form of the formula but I could not find the justification to suggest that this form is more accurate than the form presented. Would you explain to me why? :D – QmmmmLiu Oct 27 '15 at 03:54
  • I think they mean for large $x$, where we might get bad roundoff error (great loss of significant figures) from subtracting two large nearly equal quantities. – André Nicolas Oct 27 '15 at 03:55
  • Would there be a mathematical proof of some sort to express what you have said? – QmmmmLiu Oct 27 '15 at 03:56
  • Yes, there is. Suppose we are computing to $k$ significant figures. One can give quite precise estimates of the number of correct figures doing it one way, and doing it the other way. – André Nicolas Oct 27 '15 at 04:00
  • Apology for stepping away. It appears that @AndreNicolas has provided an answer to your question. - Mark – Mark Viola Oct 27 '15 at 04:03
  • I am still puzzled: how can we obtain $k$? – QmmmmLiu Oct 27 '15 at 04:06
  • @QiminLiu: This sort of issue is very real. Many computations involve numbers represented by a small number of bits, say $32$ or even $16$. Then one has to be very careful to minimize loss of significance. – André Nicolas Oct 27 '15 at 04:08
  • 2
    Catastrophic cancellation is the issue. If $x$ is large enough so that $\sqrt{x-1} \approx \sqrt{x-2}$ then the subtraction will be very noisy. For example, in 32 bit FP arithmetic, if you let $x=10^{32}$ then the first formula will return $0$, where as the other will return $5 \times 10^{-17}$. – copper.hat Oct 27 '15 at 04:33
  • 1
    See also the essentially identical question https://math.stackexchange.com/q/916402/115115 – Lutz Lehmann Oct 27 '15 at 08:43

1 Answers1

0

I think that you already received good answers and comments. In particular, the simple solution from Dr. MV will avoid tremendous losses of accuracy (at the price of two square roots as in the initial problem)

Let me propose another approximate solution using Taylor expansions $$\sqrt {x-1} - \sqrt{x-2}=\frac{1}{2 \sqrt x}\Big(1+\frac{3}{4 x}+\frac{7}{8 x^2}+\frac{75}{64 x^3}+\frac{217}{128 x^4}+\frac{1323}{512 x^5}+\cdots \Big)$$ which, for sure, you can truncate after very few terms when $x$ is large.

Claude Leibovici
  • 260,315