4

Given the expression

$$2675394361153184*(A+B+C+D)$$ Where... $$A=\frac{873892798365919}{334424295144148}\approx2.613125933$$ $$B=-(\sqrt{2}*\sqrt{(2+\sqrt{2})})\approx−2.613125930$$ $$C=\frac{1235871046525617}{668848590288296}*\sqrt{2}\approx2.613125931$$ $$D=\frac{-118236843671656}{83606073786037}*\sqrt{(2+\sqrt{2})}\approx−2.613125935$$

This results in... $$2675394361153184*(A+B+C+D)\approx−2675394.361153184$$ When the accurate result is... $$2675394361153184*(A+B+C+D)\approx0.000185883$$

Due to the lack of initial precision for the 4 terms and the fact their values are so closed to one another, the result is a value that is wildly off because of catastrophic cancellation. Is there a general method or rule to rearrange the equation to prevent this loss of precision other than being forced to increase it?

Drake Jacovian
  • 61
  • Since each of $A,B,C,D \approx \pm 2.6$ and $A+B+C+D \approx 7 \times 10^{-20}$ you just need a calculator with a precision which can capture this range. If you used rational approximations to $\sqrt2$ and $\sqrt{2+\sqrt2}$, you would be dealing with integers much larger than 10^{20} which would not be easier. – Henry Aug 09 '14 at 11:05
  • I don't know for sure if it will help, but I'd suggest looking in Knuth's AOCP, and Higham's work on floating point arithmetic. Catastrophic cancellation is a well-known problem, and it's likely that there are standard approaches to reducing it. – bubba Aug 31 '14 at 11:11

4 Answers4

2

Thanks to everyone who replied.

Unfortunately most of these seemed to either required calculating to greater precision or came with complexities that were really not at my disposal to take advantage of.

However with a sizable amount of googling and using the identity...

$$ a-b=\frac{a^{2}-b^{2}}{a+b} $$

I was able to convert the expression to...

$$ (\frac{\frac{2218922995426324599263732563440173267243588267540415488}{(20245131845729346779847938030624+-((-14315469975380507081228626675712*\sqrt{2})))}}{((4943484186102468*\sqrt{2})+-(((-2675394361153184*\sqrt{2})*\sqrt{(2+\sqrt{2})})))}+\frac{\frac{-2218923000832706942746447217078707659528620579120214016}{(20245131813752124018701547507776+-((-14315470030270074363021089112064*\sqrt{2})))}}{(6991142386927352+-((-3783578997492992*\sqrt{(2+\sqrt{2})})))}) $$

In this form it is possible to use standard precision to get the correct result even though the expression is made more complicated and is not very pretty.

I hope this method of conversion will catch a majority of these issues.

Drake Jacovian
  • 61
0

You can use a common denominator in order to represent $A+B+C+D$ as follows:

$\frac { 3575731358058071001505461047880153496135647147956712099892919567403972111048861727680010033109631385790971177403304308564585151977964488268427380282686715110926060936509021700772235697853916232082549146464679733894051137344195234026614190284685748786831767118464175795945305329770579403212229045776067391921975947857968071181058841932766830635113811188136521343633627324717825000949422046813976478178409458933697 } { 51465510988596121091440469814015052510508559825362615771552289268007611821007822859557515012057086449433091687932874147396314615748433771213854498400441081576302516854261887909749167542410259052963219107722593448921482316433438540893581542040052682891447881771009698122037995051713928100054112137414587772004747077492191879009552930946844188111721346002111764321797985322982380602304745937852660670505680214863027338467278084046848 } $

This, when multiplied by $2675394361153184$, will give you a result of $0.0001858816$.

If you can't see the numbers properly, then you can edit the answer and copy them...

In general, you should calculate a rational approximation of each irrational factor.

Here is an algorithm that you can use in order to calculate it for a square root:

Function (input number, input num_of_iterations, output root):
    Set root.numerator   = number
    Set root.denominator = 1
    Run num_of_iterations:
        Set root = root-(root^2-number)/(root*2)

You might find this C++ implementation useful (it also includes the conversion of the numerator divided by the denominator into a numerical string with predefined floating-point precision).

Please note that no floating-point operations are required (as demonstrated at the given link).

barak manos
  • 43,109
0

Hint:

Clearly the major obstacle of this problem standing in the way of computing the value in a conventional manner is the presence of very large irreducible prime factors. Let Barak's answer stand as a testament to why trying to find a common denominator without a computer algebra program is a laughable request.

One quick and dirty work-around is adding $1$ or $2$ to the numerators and denominators and seeing if the nearby "neighbors" of these numbers are comprised of smaller prime factors. Because the numerators and denominators are so large, additions on the order of $1$ should have a negligible impact on the overall value.

David H
  • 29,921
0

Let $\alpha=2.6131259$ and $\beta=10^{-8}$ then: $$A=\alpha+\color{red}{3.32975}\;\color{blue}{25895}\;\color{green}{8594}\;\color{violet}{14870}\beta\\ -B=\alpha+\color{red}{2.97527}\;\color{blue}{53055}\;\color{green}{71328}\;\color{violet}{63468}\beta\\ C=\alpha+\color{red}{3.12177}\;\color{blue}{12751}\;\color{green}{35301}\;\color{violet}{02157}\beta\\ -D=\alpha+\color{red}{3.47624}\;\color{blue}{85591}\;\color{green}{42965}\;\color{violet}{98453}\beta$$

from here, here, here and here

So, let $Z=(A+B+C+D)$. Now taking precision of terms with $\beta$ upto n digits after decimal: $$\begin{array}{|c|c|}\hline n&Z/\beta\\\hline 0&1\\\hline 1&10^{-1}\\\hline 2&0\\\hline 3&-1\times10^{-3}\\\hline 4&0\\\hline 5&1\times10^{-5}\\\hline 6&0\\\hline 7&-1\times10^{-7}\\\hline 8&0\\\hline 9&0\\\hline 10&0\\\hline 11&0\\\hline \color{red}{ 12}&\color{red}{7\times10^{-12}}\\\hline \color{red}{13}&\color{red}{7\times10^{-12}}\\\hline \color{red}{14}&\color{red}{6.96\times10^{-12}}\\\hline \color{red}{15}&\color{red}{6.949\times10^{-12}}\\\hline\cdots&\cdots\\\hline \color{blue}{20}&\color{blue}{6.94788936 \times 10^{-12}}\\\hline \end{array}$$ You can see the question maker could not code further values, since they almost became constant now $$\color{purple}{2675394361153184}\times\color{blue}{6.94788936 \times 10^{-20}}\approx\color{green}{0.0001858834401}\cdots$$

I'm greatly impressed by the question.

RE60K
  • 17,716