[Computing] square roots

A standard way to compute Sqrt[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). After t steps, this method yields a result accurate to about 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] with f[1] = f[2] = 1 tends to 1 + Sqrt[2]. This method yields about 2.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 s^{2} + 4 r == 4^{t} n, keeping r as small as possible so as to make s <= 2^{t} Sqrt[n] < s+4. Note that the method works not only for integers, but for any rational number n for which 1 <= n < 4.