17
$\begingroup$

I have the following formula that I need to rewrite in order to avoid catastrophic cancellation.

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

As $x$ becomes smaller, $\sqrt{1-x^{2}}$ approaches $1$, so you will get $1 - 1.000000000......1$ which will result in a catastrophic cancellation. I tried to rewrite the formula myself in a few different ways, but I didn't manage yet to avoid the catastrophic cancellation.

The goal is to approximate $\pi$:

import numpy as np


tn = 0.5
for i in range(1,100):
    tn1 = np.sqrt(0.5*(1-np.sqrt(1-tn**2)))
    print(i, 6*2**i*tn1)
    tn = tn1

Output

1 3.1058285412302498
2 3.132628613281237
3 3.139350203046872
4 3.14103195089053
5 3.1414524722853443
6 3.141557607911622
7 3.141583892148936
8 3.1415904632367617
9 3.1415921060430483
10 3.1415925165881546
11 3.1415926186407894
12 3.1415926453212157
13 3.1415926453212157
14 3.1415926453212157
15 3.1415926453212157
16 3.141593669849427
17 3.1415923038117377
18 3.1416086962248038
19 3.1415868396550413
20 3.1416742650217575
21 3.1416742650217575
22 3.1430727401700396
23 3.1598061649411346
24 3.181980515339464
25 3.3541019662496847
26 4.242640687119286
27 6.0
28 0.0
29 0.0
30 0.0
31 0.0
32 0.0

How should I rewrite the formula to avoid catastrophic cancellation?

Improve this question
$\endgroup$
3
  • 8
    $\begingroup$ Herbie is a useful tool to automate this kind of considerations (at least to some extent). $\endgroup$
    – cos_theta
    Sep 22, 2020 at 11:32
  • 1
    $\begingroup$ Heh interesting, thank you for the link. $\endgroup$
    – Ron
    Sep 22, 2020 at 13:00
  • 2
    $\begingroup$ Don't know what you tried, but a-b = (a-b)(a+b)/(a+b) = (a^2 - b^2) / (a + b) is very often useful for such differences. Especially if a or b is a square root obviously. And that's what the answer does, but it works in many more cases. $\endgroup$
    – gnasher729
    Sep 23, 2020 at 10:48

1 Answer 1

Reset to default
26
$\begingroup$

Take

\begin{align} 1-\sqrt{ 1-x^2} &= (1-\sqrt{ 1-x^2})\frac{1+\sqrt{ 1-x^2}}{1+\sqrt{ 1-x^2}}\\ &= \frac{x^2}{1+\sqrt{ 1-x^2}} \end{align}

So

\begin{align} y = x\sqrt{\frac{1}{2+2\sqrt{1-x^2}}} \end{align}

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It ought to be $y=|x|\sqrt\dots$ when taking $x^2$ out of the radical. $\endgroup$
    – Simply Beautiful Art
    Sep 24, 2020 at 15:33
  • $\begingroup$ Also, instead of $\sqrt{1-x^2}$ use $\sqrt{(1-x)(1+x)}$ to reduce error for $x$ near unity. $\endgroup$
    – njuffa
    Mar 9, 2022 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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