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.

Hungry Goats

Problem: A goat is tied to the edge of a circular plot of grass by a length of rope. How long should the rope be so that the goat eats exactly half of the grass?

Solution: Let the radius of the plot of grass be \(R\) and the length of the rope be \(L\). The center of the circular plot is \(O\) and the goat is tied to the edge of the plot boundary at \(C\).

Note that the area representing the grass that the goat eats is the intersection of two offset circles: one being the plot of grass (green), the other defined by the area the goat can move given that it’s tied where it is (red). Let the points of intersection of the circles be \(A\) and \(B\).

This area of intersection looks difficult at first, but it is really two circular segments: one for the green circle, and one for the red. A circular segment is the area between a chord of a circle and the arc it bounds. The green segment lies between arc \(\widehat{ACB}\) and line \(\overline{AB}\). The area of this segment is the difference between the area of the sector bounded by the arc \(\widehat{ACB}\) and the lines \(\overline{OA}\) and \(\overline{OB}\), and the triangle \(\bigtriangleup{AOB}\).

Let the angle subtended by the arc \(\widehat{ACB}\) be \(2 \phi\). The area of the sector \(A_{GS}\) is given by \(A_{GS}=\frac{1}{2} R^2 (2 \phi)\), and the area \(A_{GT}\) of triangle \(\bigtriangleup{AOB}\) is given by \(A_{GT}=\frac{1}{2} R^2 \sin{2 \phi}\). The area of the green segment \(A_G\) is then \(A_G=\frac{1}{2} R^2 \left (2 \phi – \sin{2 \phi} \right )\).

Results are similar for the red segment. If the angle subtended by the arc \(\widehat{AOB}\) is \(2 \theta\), then the area of the red segment \(A_R\) is \(A_R=\frac{1}{2} L^2 \left (2 \theta- \sin{2 \theta} \right )\). The area of the grass eaten by the goat is the sum of the areas of the red segment and the green segment, \(A_R + A_G\).

This area depends on four parameters, \(R\), \(L\), \(\phi\), and \(\theta\). Of these, \(R\) is given, and \(L\) is what we are tasked to find in terms of \(R\). This leaves us to find the other two parameters in terms of \(R\) and \(L\).

We do this by noting that triangle \(\bigtriangleup{AOC}\) is isosceles. From this triangle, we see that \(L=2 R \sin{\frac{\phi}{2}}\) and \(2 \theta + \phi = \pi\). These two relations will allow us to get a single equation relating \(L\) to \(R\).

We begin by expressing the condition that the area the goat eats, \(A_R + A_G\), is one half of the area of the circular plot, \(\pi R^2\):

\(A_R + A_G = \frac{1}{2} R^2 \left (2 \phi – \sin{2 \phi} \right ) + \frac{1}{2} L^2 \left (2 \theta- \sin{2 \theta} \right ) = \frac{\pi}{2} R^2\).

Let \(\beta = \frac{L}{R}\). Then \(\phi = 2 \arcsin{\frac{\beta}{2}}\) and \(\theta = \frac{\pi}{2} – \arcsin{\frac{\beta}{2}}\). Diving both sides of the area equation above by \(R^2\), and plugging in the above relations, we get the following equation for \(\beta\):

\(4 \left ( 1 – \frac{\beta^2}{2} \right ) \arcsin{\frac{\beta}{2}} – 2 \beta \sqrt{1 – \frac{\beta^2}{4}} + \pi \left ( \beta^2 – 1 \right ) = 0\).

(Yes, I combined a lot of steps here, including some non-trivial trig simplifications. This stuff is really better off left to the reader.)

This equation cannot be solved in analytical closed form. I think this is what is unexpected from a cursory inspection of the problem. So, you need some tool to solve it. Fortunately, Wolfram Alpha will solve it just nicely for free. Go to the site http://www.wolframalpha.com and type in the following string into the box: “findroot[ 4 (1 – b^2/2) ArcSin[b/2] – 2 b Sqrt[1 – b^2/4] + Pi (b^2 – 1) , {b,1}]”. The result is that, to six significant figures, \(\beta \approx 1.15873\). That is, the length of the rope is about 15.9% larger than the radius of the circular plot.

NB Some of you may scoff at my use of a web tool to solve my equation, and wonder what happened to rigorous analysis. The truth is that the solution of such equations has become so routine and cheap that, unless you are demonstrating something special about the solution process, there is little value in going through all of the low-level details about solutions. I know this contradicts something I posted earlier today, but the important detail was the derivation of the above equation, from which we obtained the solution.

IYI (If you’re interested): This problem is structurally very similar to those found in certain optics applications. In particular, folks who model image formation in microscopes and similar systems deal with geometry just as in this problem.  Actually, a little more general.  Imagine the following problem: there is a circular plot of grass, and a goat is tied up somewhere with a rope of a given length.  How much of the grass can the goat eat?  Now imagine two goats, each tied with rope of the same length, but in different places.  Again, how much of the grass can the goats eat?

I published a complete solution to this problem, but in the context of imaging a transilluminated object with a microscope using an extended source.  The problem, of course, can get far more complicated in the optics context, and all analogies with goats and grass gets lost when we ask about aberrations and defocus.  If you have the stomach for this, I published another paper which dealt with this.