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?

$\endgroup$
  • 8
    $\begingroup$ Herbie is a useful tool to automate this kind of considerations (at least to some extent). $\endgroup$ – cos_theta Sep 22 at 11:32
  • 1
    $\begingroup$ Heh interesting, thank you for the link. $\endgroup$ – Ron Sep 22 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 at 10:48
25
$\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}

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It ought to be $y=|x|\sqrt\dots$ when taking $x^2$ out of the radical. $\endgroup$ – Simply Beautiful Art Sep 24 at 15:33

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.