Computing square roots

Let’s say you want to take the square root of a real number $$a$$ without a computer. How would you do it? How do you think a computer does it?

The only way I know any computer performs square roots practically is via the following recurrence:

$$s_1=1; s_n=\displaystyle \frac{1}{2} \left ( s_{n-1} + \frac{a}{s_{n-1}} \right )$$,

where

$$\sqrt{a}=\displaystyle \lim_{n\to\infty}s_n$$.

The recurrence derives from Newton’s Method of finding roots, as applied to the function $$f(x)=x^2-a$$. But that is not the point; the point is the recurrence and how fast it converges to its goal. Typically, roots found via Newton’s Method exhibit quadratic convergence; that is, the error in an iteration is the square of the error of the previous iteration. It turns out that the above recurrence has an exact solution, and from this solution we can closely examine the convergence toward the above limit.

The way to see this solution is to set $$s_n=\sqrt{a} \coth{\theta_n}$$, where the hyperbolic cotangent is

$$\coth{x}=\displaystyle \frac{e^{x}+e^{-x}}{e^{x}-e^{-x}}$$.

The hyperbolic cotangent satisfies a doubling formula:

$$\coth{2 x}=\displaystyle \frac{1}{2} \left ( \coth{x} + \frac{1}{\coth{x}} \right )$$.

The above recurrence then takes the simplified form

$$\theta_{1}=\tanh^{-1}{\sqrt{a}}; \theta_{n}=2 \theta_{n-1}$$.

The solution to the original recurrence then easily follows:

$$s_n=\sqrt{a} \coth{ \left ( 2^{n-1} \tanh^{-1}{\sqrt{a}} \right ) }$$.

One slight complication: for $$a>1$$, $$\tanh^{-1}{\sqrt{a}}$$ is a complex number with imaginary part = $$\frac{\pi}{2}$$. Because the recurrence involves a doubling of the argument, the imaginary part has no effect on the result. That said, it is more direct to write the result as

$$s_n=\sqrt{a} \coth{ \left ( 2^{n-1} \Re \left [ \tanh^{-1}{\sqrt{a}} \right ] \right ) }$$,

where $$\Re \left [ z \right ]$$ denotes the real part of $$z$$.

On the surface, it seems silly to express this solution to the recurrence in terms of the limit that it approximates. That said, the goal in deriving this solution was to examine how it converges to the limit. Along these lines, consider the following approximation, valid for large arguments:

$$\coth{x} \approx 1+2 e^{-2 x}$$.

The error at later stages of the recurrence is then about

$$\displaystyle \left | \frac{s_n}{\sqrt{a}} – 1 \right | \approx 2 \times 10^{- \left (\log_{10}{e} \right ) \left ( \Re \left [ \tanh^{-1}{\sqrt{a}} \right ] \right ) 2^{n}}$$.

For each increment in $$n$$, the error is the square of the previous error, as I mentioned above being a characteristic of root finding via Newton’s Method. The solution allows us to be even more specific. Because $$\log_{10}{e} \approx 0.4343$$ and $$\Re \left [ \tanh^{-1}{\sqrt{a}} \right ] \approx 1$$ for most values of $$a>1$$, each iteration supplies slightly less than $$2^n$$ decimal places of accuracy.

Note that this analysis only applies to square roots of real numbers. For complex square roots, the initial guess in Newton’s Method must be complex, and the solution of the recurrence is more complicated.