[Computing] square roots
A standard way to compute √n\!\(\*SqrtBox[\(n\)]\)
is Newton's method (actually used already in 2000 BC by the Babylonians), in which one takes an estimate of the value x and then successively applies the rule x 1/2 (x + n/x)x 1/2 (x + n/x)
. After t steps, this method yields a result accurate to about t2\!\(\*SuperscriptBox[\(t\),\(2\)]\)
digits.
Another approach to computing square roots is based on the fact that the ratio of successive terms in for example the sequence f[i] = 2 f[i - 1] + f[i - 2]f[i] = 2 f[i - 1] + f[i - 2]
with f[1] = f[2] = 1f[1] = f[2] = 1
tends to 1 + √21+\!\(\*SqrtBox[\(2\)]\)
. This method yields about 2.5 t2.5 t
base 2 digits after t steps.
The method of computing square roots shown in the main text is less efficient (it computes t digits in t steps), but illustrates more of the mechanisms involved. The basic idea is at every step t to maintain the relation s2 + 4 r 4t n\!\(\*SuperscriptBox[\(s\),\(2\)]\)+4r==\!\(\*SuperscriptBox[\(4\),\(t\)]\)n
, keeping r as small as possible so as to make s ≤ 2t √n < s + 4s<=\!\(\*SuperscriptBox[\(2\),\(t\)]\)\!\(\*SqrtBox[\(n\)]\)
. Note that the method works not only for integers, but for any rational number n for which 1 ≤ n < 41 ≤ n < 4
.