Mathematica: "15 digits of Sqrt[x] yield 42+ million digits of x"

I did this in Mathematica to compute Sqrt[5]:

a[0] = 2 
a[n_] := a[n] = a[n-1] - (a[n-1]^2-5)/2/a[n-1] 

How close is a[25] to Sqrt[5]?

N[Sqrt[5]-a[25]] // FortranForm 
4.440892098500626e-16 

And how close is a[25]^2 to 5?

N[a[25]^2-5] // FortranForm 
8.305767102358763e-42074769 

This seems odd to me. My estimate: if x is within 10^-n of Sqrt[5], then x^2 is within 10^(-2*n) of 5, give or take. No? In fact:

a[25]^2 = (Sqrt[5]-4.440892098500626e-16)^2 ~ 5 - 2*5*4.440892098500626e-16 

(expanding (a-b)^2), so the accuracy should be only about 14 digits (or n digits in general).

Of course, Newton's method yielding only 15 accu开发者_运维百科rate digits in 25 iterations also seems odd.

Am I losing precision too early in the calculations above? Note that:

N[Log[Sqrt[5]-a[25]]] // FortranForm 
-35.35050620855721 

agrees w/ the 15 digit precision above, even though I do N[] after taking the Log (so it should be accurate).

The problem is how Mma is calculating your sequence.

a[n] are Rational numbers. Lets see the order of magnitude for the Numerators, in a loglog scale:

a[0] = 2 
a[n_] := a[n] = a[n-1] - (a[n-1]^2-5)/2/a[n-1] 
ListPlot@Table[Log[10, Log[10, Numerator[ a[i]]]], {i, 1, 25}]

so, your numerators are increasing as a double exponential.

The 10^-16 precision is achieved much before a[25]:

For[i = 1, i < 5, i++,
 Print["dif[", i, "]= ", N[a[i] - Sqrt[5], 16]]
 ]

dif[1]= 0.01393202250021030

dif[2]= 0.00004313361132141470

dif[3]= 4.160143063513508*10^-10

dif[4]= 3.869915959583412*10^-20  

Afterward, you have start controlling the precision for the division as the Numerator for a[5] has already 20 digits.