Square roots

This post gives three methods for calculating square roots.

You may have heard that, back in the stone age, we were taught how to calculate square roots by hand, by a method that looks something like long division. It’s true, and I was taught that method as part of Algebra class. So if you’ve wondered how it was done, or if you want to be ready for the Zombie Apocalypse which for some reason might also include the failure of all the calculators, then this section is for you.

But even in those days, probably nobody professional would ever have used that method. Once you got to be an adult engineer or scientist, you no doubt had a slide rule. I had a cheap plastic student slide rule, but never got to the stage of investing in a real one like my Dad’s, because before I graduated college the electronic calculator had been invented. Anyway, this section is for you slide-rule enthusiasts. I know you’re out there.

But what do computers and calculators do? It turns out they use a different method entirely, one that is very fast and very easy to implement. That’s described here.

Square roots by hand

We’ll illustrate the method with the number 567.89. The first few digits of \sqrt{567.89} according to the wonderful online symbolic calculator Wolfram Alpha are 23.830442715149041057691021305122285926005982712153964734078. It’s an irrational number, so you could in principle carry on those digits infinitely far without repeating.

But don’t worry, we’re not going to calculate by hand that far. As you’ll see, the hand method gets more and more tedious the more digits you have. I’ll carry the method as many digits as I can stand, till I get tired of formatting the pictures.

The first thing we do is group the digits in pairs starting at the decimal point, going to the left and to the right. Each pair is going to get one digit of the answer written over it. We add some 0‘s on the right because we’re going to calculate at least a few digits in that direction. So on the left of the decimal point the 67 is paired and the 5 is alone.

\displaystyle \sqrt{5\;67.89\;00\;00\hdots}

Our first group is the single number 5. Above that we write the largest integer whose square is less than or equal to that, which is 2. Square that, subtract from 5 and bring down the remainder and the next pair of digits.

\displaystyle \begin{aligned} 2\;\phantom{67.89}\phantom{\;00\;00\hdots}& \\ \sqrt{5\;67.89\;00\;00\hdots}& \\ \underline{4\phantom{\;67}} \phantom{.89\;00\;00\hdots}& \\ 1\;67\phantom{.89\;00\;00\hdots}& \end{aligned}

What we do on the next step is what we will do on all of the subsequent steps, as many steps as we want to calculate digits. First, we double all the digits of the square root we have so far (which is just 2 so doubling it makes 4). We write that followed by a blank.

\displaystyle \begin{aligned} 2\;\phantom{67.89}\phantom{\;00\;00\hdots}& \\ \sqrt{5\;67.89\;00\;00\hdots}& \\ \underline{4\phantom{\;67}} \phantom{.89\;00\;00\hdots}& \\ 4\underline{\quad} \quad | 1\;67\phantom{.89\;00\;00\hdots}& \end{aligned}

The next digit of the square root, which we’ll put over the pair 67, is also going to be put in that blank. Then we’ll multiply that two-digit number by the digit. So if we put a 2, we’d calculate 2 * 42 = 84 and if we put a 3, we’d calculate 3 * 43 = 129. It turns out that 3 is the largest digit we can choose without exceeding 167, so that is the digit we use.

The product 129 we write under the 167 and subtract. Then we bring down the next pair of digits.

\displaystyle \begin{aligned} 2\;\phantom{6}3\phantom{.89}\phantom{\;00\;00\hdots}& \\ \sqrt{5\;67.89\;00\;00\hdots}& \\ \underline{4\phantom{\;67}} \phantom{.89\;00\;00\hdots}& \\ 43 \quad | 1\;67\phantom{.89\;00\;00\hdots}& \\ \underline{1\;29} \phantom{.89\;00\;00\hdots}& \\ 38\;89 \phantom{\;00\;00\hdots}& \end{aligned}

And now we repeat the process.

  • Double the existing digits (23) and write the result (46) next to the bottom line followed by a blank.
  • Find the largest digit which, when inserted in the blank and multiplied by the resulting 3-digit number, does not exceed the value 3889 currently on the bottom line.
  • Write that product under the bottom line number and subtract
  • Bring down the next two digits

That digit turns out to be 8 as 8 * 468 = 3744, but 9 * 469 = 4221, too large.

\displaystyle \begin{aligned} 2\;\phantom{6}3.\phantom{8}8\phantom{\;00\;00\hdots}& \\ \sqrt{5\;67.89\;00\;00\hdots}& \\ \underline{4\phantom{\;67}} \phantom{.89\;00\;00\hdots}& \\ 43 \quad | 1\;67\phantom{.89\;00\;00\hdots}& \\ \underline{1\;29} \phantom{.89\;00\;00\hdots}& \\ 46\underline{8} \quad | 38\;89 \phantom{\;00\;00\hdots}& \\ \underline{37\;44} \phantom{\;00\;00\hdots}& \\ 1\;45 \;00 \phantom{\;00\hdots}& \end{aligned}

I think you can start to see how this got tedious back in the day, as we were doing all this trial and error multiplication by hand to find the next digit.

Repeating the process, we double our existing digits 238 to get 476, and find the largest digit x such that x * 476x <= 14500. As 3 * 4763 = 14289 and 4 * 47 = 19056, too large, our next digit is 3.

\displaystyle \begin{aligned} 2\;\phantom{6}3.\phantom{8}8\phantom{\;0}3 \phantom{\;00\hdots}& \\ \sqrt{5\;67.89\;00\;00\hdots}& \\ \underline{4\phantom{\;67}} \phantom{.89\;00\;00\hdots}& \\ 43 \quad | 1\;67\phantom{.89\;00\;00\hdots}& \\ \underline{1\;29} \phantom{.89\;00\;00\hdots}& \\ 468 \quad | 38\;89 \phantom{\;00\;00\hdots}& \\ \underline{37\;44} \phantom{\;00\;00\hdots}& \\ 476\underline{3} \quad |1 \;45 \;00 \phantom{\;00\hdots}& \\ \underline{1 \;42 \;89} \phantom{\;00\hdots}& \\ 2 \; 11 \;00 \phantom{\hdots}& \end{aligned}

And that’s the method! Now you can impress all your friends at parties with your ability to extract square roots by hand, if you don’t mind missing the whole party doing something they can do on their phone with a couple of key clicks.

Square roots with slide rule

This is about the simplest thing you can do on a slide rule. There is a row of numbers with an A next to it, the A-scale, and another with a D next to it called the D-scale. Just line them up. The D-scale is the square root of the numbers on the A-scale, so you put the cursor on the desired number on the A-scale and read its square root on the D-scale.

See an illustration like this one to see what I’m talking about.

Slide rules are not meant for high-accuracy calculations. You can really only estimate 2-3 significant digits. Another part about using a slide rule is that you have to work out the powers of 10 on your own.

For our sample problem, you would approximate 5.67 on the A scale between 5.6 and 5.7, and look down and see the square root on the D scale between 2.3 and 2.4, closer to 2.4. That tells you that \sqrt{5.67} \approx 2.4 from which you would know \sqrt{567} \approx 24.

The Newton-Raphson method

The algorithm used by computers was one originally developed by Isaac Newton, and it is known as Newton’s Method or the Newton-Raphson Method.

It’s an iterative method, meaning you start with one guess, x_0. The algorithm then generates the next, presumably better, guess. You repeat this process until you decide to stop the algorithm, either because the guesses aren’t changing any more, or because you set an upper limit on the number of iterations.

Newton’s Method is not just for square roots. It’s a general method for finding where a function f(x) crosses the x-axis, that is, the solution to f(x) = 0. You can think of finding a square root x of a number A as finding the x such that x^2 - A = 0. So f(x) = x^2 - A.

The figure above illustrates the method. We have a guess x_1 which is not a zero. We evaluate the slope at x_1, f'(x_1) and draw the tangent line there. The place where the tangent line intersects the x-axis is the next guess, which as you can see in the figure is closer to the actual x-intercept.

When the method converges, it converges very quickly, in fact it is one of the fastest-converging iterative algorithms of any kind. It converges quadratically, meaning that if the error (distance between guess and actual zero) is for instance 0.1 on one step, it will be about 0.01 on the next. The number of digits of accuracy roughly doubles at each iteration.

We know from algebra that a line with slope m which goes through point (a, b) has the equation in point-slope form, y - b = m(x - a). So if our current guess at step n is x_n, the equation of the line with slope f'(x_n) going through point (x_n, f(x_n)) is y - f(x_n) = f'(x_n) (x - x_n). Thus, x_{n+1}, the point where y = 0 on this line, is given by

\displaystyle \begin{aligned}    -f(x_n) &= f'(x_n)(x_{n+1} - x_n) \\[9 pt]     -\frac{f(x_n)}{f'(x_n)} &= x_{n+1} - x_n \\[9 pt]     x_{n+1} &= x_n - \frac{f(x_n)}{f'(x_n)} \end{aligned}

This is the general Newton-Raphson update formula. Now let’s see how it applies to square roots. We have f(x) = x^2 - A, therefore f'(x) = 2x and the update rule is

\displaystyle \begin{aligned}    x_{n+1} &= x_n - \frac{x_n^2 - A}{2x_n} \\[9 pt]    &= x_n - \frac{x_n}{2} + \frac{A}{2x_n} \\[9 pt]    &= \frac{1}{2} \left ( x_n + \frac{A}{x_n} \right ) \end{aligned}

The new guess for sqrt(A) is the average of the old guess x_n and A/x_n. The only remaining question is what to use for an initial guess x_0. Because the method converges so quickly, x_0 does not need to be very close to the actual square root. Using A will do for instance.

Let’s see how the method works with the sample problem used in other sections, A = 567.89.

\displaystyle \begin{aligned}    x_0 &= 567.89 \\    x_1 &= 284.445 \\    x_2 &= 143.2207421909332 \\    x_3 &= 73.592940070157866 \\    x_4 &= 40.654788505971773 \\    x_5 &= 27.311688365308999 \\    x_6 &= 24.052308736660752 \\    x_7 &= 23.831465995950072 \\    x_8 &= 23.830442737117970 \\    x_9 &= 23.830442715149040 \\    x_{10} &= 23.830442715149040 \end{aligned}

After 10 iterations, the value stops changing, indicating that the value is correct to the limit of accuracy of the computer.

If this iterative method works so well, why didn’t we use it for manual calculations instead of that long grueling “long-division” method? The answer is that this method requires a division A/x_n at every step. For a CPU, a 16-digit division is not much more difficult than a 16-digit multiplication. But for a human, just one such division would be almost as hard as doing 16 digits of the entire square root algorithm.

If you were aware of the manual method, did you ever wonder why it works? I know I did. But that’s a topic for a future post.

So now you know three methods of finding square roots if you ever find yourself without a square root button on your calculator. Enjoy!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: