2

Having $2$ formats of same function -

$f(x) = \displaystyle x(\sqrt{x+1}-\sqrt{x}) $

and

edit:

$f(x) \displaystyle = \frac{x}{\sqrt{x + 1} + \sqrt{x}} $

(evaluated as @vonbrand computed ..)

Assume we use floating point with $6$ figures , why does the function at the $2$nd format gives more accurate result ?

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
URL87
  • 391
  • 1
    In addition to the answer, it is highly instructive to read https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/02Numerics/Double/paper.pdf – Amzoti Mar 29 '13 at 13:00

4 Answers4

3

Consider a practical example $x=10^{10}\ $ then you will need at least $12$ digits precision to get a good approximation : $$f(x)\approx 10^{10}(100000.000005 - 100000)\approx 50000$$ while the other possibility (after simplification) $\ \displaystyle f(x)=x\frac 1{\sqrt{x+1}+\sqrt{x}}\ $ will give (to $6$ digits) : $$f(x)\approx 10^{10}\frac 1{100000 + 100000}\approx 50000$$ i.e. without having to take the precise value of $\sqrt{10^{10}+1}$ in consideration.

Let's consider your more general : $$f(x)=x(\sqrt{x+1}-\sqrt{x})\approx x\sqrt{x}\left(\sqrt{1+\frac 1x}-1\right)$$ $$f(x)\approx x\sqrt{x}\left(1+\frac 1{2x}-1\right)$$ The answer will of course be $\ \displaystyle f(x)\approx \frac 1{2\sqrt{x}}$ but you needed to evaluate with precision $1+\frac 1{2x}$ in the first case while in the second $\displaystyle\frac 1{2\sqrt{x}}$ was enough.

This means two times more digits in the first case for large $x$ !

Let's exhibit a 'classical' relative error handling (all the $\delta u$ terms are positive) :

  1. The error on a difference $d=x-y\ $ has the same expression than the error on $x+y$ : $\ \delta d\approx \delta x+\delta y$ (more exactly $\ \delta d\le \delta x+\delta y$)

  2. The error on a power $p=u^n$ verifies $\ \delta p\approx |n|\,|u|^{n-1}\delta u$ (more generally $\delta f(u)\approx \left|\frac {df(u)}{du}\right|\delta u$)

    Let's use them both to compare the error on $g(x):=\sqrt{x+1}-\sqrt{x}$ to the error on $\displaystyle h(x):=\frac 1{\sqrt{x+1}+\sqrt{x}}$ (omitting the common $x$ factor to simplify a little) :

Applying $2.$ with $n=\frac 12$ we get (assuming $x>0$) : $$\delta \sqrt{x}=\frac {\delta x}{2\sqrt{x}}\quad \text{and}\quad \delta \sqrt{x+1}=\frac {\delta x}{2\sqrt{x+1}}$$ So that using $1.$ : $$\delta g(x)=\delta|\sqrt{x+1}-\sqrt{x}|\le \left(\frac 1{2\sqrt{x+1}}+\frac 1{2\sqrt{x}}\right)\delta x$$ For $x$ 'not too small' this gives $\ \displaystyle\delta g(x)\approx\frac {\delta x}{\sqrt{x}}$

Now let's consider $\ \displaystyle\frac 1{\sqrt{x+1}+\sqrt{x}}$ and apply $2.$ with $n=-1$ and $u=\sqrt{x+1}+\sqrt{x}\ $ so that $\delta u\approx \delta g(x)\ $ and : $$\delta h(x)\approx\frac{\delta u}{u^2}$$ And for $x\gg 1$ : $$\delta h(x)\approx \frac{\delta x}{4x\sqrt{x}}$$

Concretely for $6$ digits precision you are imposing $\delta x\approx 10^{-6}x$ so that the absolute error will be about $\ 10^{-6}\sqrt{x}\ $ in the first case and $\ \frac {10^{-6}}{4\sqrt{x}}\ $ in the second (for 'large' $x$).

Community
  • 1
Raymond Manzoni
  • 43,021
  • 5
  • 86
  • 140
2

Rigurously as written, the second form can't give better results as it computes the same subexpressions. The trouble is that for large $x$ the substraction $\sqrt{x + 1} - \sqrt{x}$ will loose precision.

However, if you multiply out the second form: $$ \frac{x (\sqrt{x + 1} - \sqrt{x}) (\sqrt{x + 1} + \sqrt{x})} {\sqrt{x + 1} + \sqrt{x}} = \frac{x (x + 1 - x)}{\sqrt{x + 1} + \sqrt{x}} = \frac{x}{\sqrt{x + 1} + \sqrt{x}} $$ Note that this new form doesn't have any substraction, so there is no precision loss.

vonbrand
  • 27,812
2

It is related to the rounding errors and difficult to asses once the algorithm used to determine the square root is given. However it is quite clear that without the algorithm we can figure it out.

Assume that your algorithm calclates

$$ x(\sqrt{x+1}-\sqrt{x}) $$

with errors $\epsilon_1$ and $\epsilon_0$ corresponding to $\sqrt{x+1}$ and $\sqrt{x}$ respectively. Then your error reads $k(\epsilon_1-\epsilon_0)$. If you use the second formula and if you assume that it is also calculated as first $x(\sqrt{x+1}-\sqrt{x})$ and then multiplied by $\frac{\sqrt{x+1}+\sqrt{x}}{\sqrt{x+1}+\sqrt{x}}$. Then the errors would be the same. However, it seems that the nominator is rewritten as the difference of the squares and you finally get:

$$f(x) = \displaystyle \frac{x}{(\sqrt{x+1}+\sqrt{x})} $$

to be calculated. Now your error becomes

$$\frac{k}{\epsilon_1+\epsilon_0}$$

when compared to the $1$st case, since the error terms are additive and in the denominator, one can expect better accuracy.

Seyhmus Güngören
  • 7,848
  • thanks , but why does $$\frac{k}{\epsilon_1+\epsilon_0}$$ gives better accuracy then $k(\epsilon_1-\epsilon_0)$ ? – URL87 Mar 29 '13 at 13:41
  • @URL87 this holds when ${\epsilon_1}^2-{\epsilon_0}^2>1$. Since they are very small numbers this will not hold. From here I would think that the terms in the nominator and denominator are not calculated one by one but jointly. – Seyhmus Güngören Mar 29 '13 at 13:55
  • @URL87 and Seyhmus Güngören : I added a $\delta$ error handling in my answer that could interest you both ;-) (to put it mildly since errors should, for example, not be subtracted..) – Raymond Manzoni Mar 29 '13 at 21:02
0

It depends on the calculating mechanism you are using(more precisely the no. of digits it displays after any operation). Both the functions will must (and will ) give the same result once you consider all the numbers after decimal points after any operation(eg. division).

Abhra Abir Kundu
  • 8,150