Algorithms for finding the square root of a number without using a calculator

By Mike Turnbull

Introduction

There may be a number of valid manual algorithms for finding the square root of a given number; however, historically there are two important methods. These two methods are simple and effective – in that they both provide accurate results. These methods are:

1. The long division method, and
2. The Newton Method.
3. A Java Implementation of Newton Method.

The long division method is useful if you only want your accuracy to a few decimal places. If you want accuracy to several decimal places then Newton’s Method is by far the preferred method.

Newton’s Method can, in fact, be used to estimate the root of any continuous power function, and this topic is covered in detail in my web page titled Delving into Newton's Method for Finding the Root of a Power Function.

While the long division method is excellent for manual calculation, it is not conducive to being implemented as a computer program. Newton’s Method, on the other hand, is exceptionally easy to implement as a computer program, and example Java source code is provided below.

Both methods will be described.

Long Division Method

The particular methodology described here is the one that was taught to me by my Father – back in about 1964. The description will be in the form of worked examples.

First I will demonstrate how to find the square root of a perfect square.

Find the square root of 60025; which we know is going to be 245 – we do, don’t we!

Draw a square root symbol (a radical symbol) with the number whose square root we are seeking underneath the horizontal extension of the symbol. Start at the decimal point and write the digits, in both directions away from the decimal point, in groups of two. In our case, there are no decimal digits, so put in one group of two zeros. Put a decimal point above the horizontal radical line, directly above the decimal point in our number.	. /------------- \/ 6 00 25.00
Start with the first group of 1 or 2 digits. Find the largest single-digit, the square of which is less than or equal to that group (6). Write that single digit (in this case 2) above the radical line, and its square (4) under the first group. Draw a line under that square, and subtract it from the first group.	2 . /------------- \/ 6 00 25.00 00 00 | 4 | - | 2
Bring down the next group below the last line drawn. This forms the current remainder. Draw a vertical line to the left of the resulting number. Then double the number above the radical symbol line (highlighted), and write it down with an empty space next to it (where the question mark is placed).	2 . /------------- \/ 6 00 25.00 00 00 | 4 | ---- | 2 00 4?|
Next determine (without using a calculator) what single-digit number ? should go in the empty space so that forty-? times ? would be less than or equal to 200. 44 x 4 = 176 45 x 5 = 225, so 4 works. Write 4 on top of the radical line. Calculate 4 x 44 without using a calculator, write that below 200, subtract, and bring down the next pair of digits (in this case the digits 25).	2 4 . /------------- \/ 6 00 25.00 00 00 | 4 | ---- | 2 00 44| 1 76 | ------- | 24 25
Now double the number above the line (24), and write the doubled number (48) with an empty space next to it as indicated.	2 4 . /------------- \/ 6 00 25.00 00 00 | 4 | ---- | 2 00 44| 1 76 | ------- | 24 25 48?|
Determine (without using a calculator) what single digit number ? should go in the empty space so that four hundred and eighty-? times ? would be less than or equal to 2425. 484 x 4 = 1936, hmm … to small? 485 x 5 = 2425, so 5 works. Write 5 on top of line. Calculate 5 x 485, write that below 2425, subtract, and see that the difference is zero – we have reached the end of the algorithm.	2 4 5. /------------- \/ 6 00 25.00 00 00 | 4 | ---- | 2 00 44| 1 76 | ------- | 24 25 485| 24 25 | ----- | 00 00
We have determined that the square root of 60025 is 245. Try it and prove it.	245 x245 ---- 1225 980 +490 ----- 60025 (qed) -----

Now let’s try something a little bit more complex.

Not all numbers are perfect squares like 60025. One very important number that is not a perfect square is the number 2. In fact, not only is 2 not a perfect square, but its square root is not a rational number – it is a decimal number that has no end; you can keep adding decimal numbers to it forever! In our case, we will determine the square root of 2 to 5 decimal places.

Draw a square root symbol (a radical symbol) with the number 2 underneath the horizontal extension of the symbol. Start at the decimal point and write the digits, in both directions away from the decimal point, in groups of two. In our case, there are no decimal digits, so put in one group of two zeros. Put a decimal point above the horizontal radical line, directly above the decimal point in our number 2.00.	. /------------- \/ 2.00
Find the largest single-digit, the square of which is less than or equal to that group (2). Write that single digit (1) above the radical line, and its square (1) under the first group. Draw a line under that square, and subtract it from the first group.	1. /------------- \/ 2.00 | 1 | - | 1
Bring down the next group below the last line drawn. This forms the current remainder. Draw a vertical line to the left of the resulting number. Then double the number above the radical symbol line (highlighted), and write it down with an empty space next to it (where the question mark is placed below).	1. /------------- \/ 2.00 | 1 | - | 1 00 2?|
Next determine (without using a calculator) what single-digit number ? should go in the empty space so that twenty-? times ? would be less than or equal to 100. 25 x 5 = 125, too big 24 x 4 = 96, so 4 works. Write 4 on top of line (right of the decimal point). Calculate 4 x 24 without using a calculator, write that below 100, subtract, and bring down the next pair of digits (in this case another set of 00 that we add to the 2.00).	1. 4 /------------- \/ 2.00 00 | 1 | - | 1 00 24| 96 | ---- | 4 00
Now double the number above the radical symbol line ignoring the decimal point, and write it down with an empty space next to it (where the question mark is placed below).	1. 4 /------------- \/ 2.00 00 | 1 | - | 1 00 24| 96 | ---- | 4 00 28?|
Determine (without using a calculator) what single digit number ? should go in the empty space so that two hundred and eighty-? times ? would be less than or equal to 400. 282 x 2 = 564, too big 281 x 1 = 281, so 1 works. Write 1 on top of line. Calculate 1 x 281, write that below 400, subtract, and get the difference.	1. 4 1 /------------- \/ 2.00 00 | 1 | - | 1 00 24| 96 | ---- | 4 00 281| 2 81 | ---- | 1 19
Now just keep going doing the same thing, as shown here.	1. 4 1 4 2 1 /---------------- \/ 2.00 00 00 00 00 | 1 | - | 1 00 24| 96 | ---- | 4 00 281| 2 81 | ---- | 1 19 00 2824| 1 12 96 | ------- | 6 04 00 28282| 5 65 64 | ------- | 38 36 00 282841| 28 28 41 | -------- | 10 07 59 …

That’s it; we have our five decimal places – but we could keep going if we wanted to. The square root of 2, to 31 decimal places, is 1.4142135623730950488016887242097. Keep going until you are happy that you have mastered the method – it is certainly not difficult; just tedious. It’s no wonder we prefer to use a calculator; but it is nice to know that it can be done without a calculator.

Newton’s Method

Although this method is attributed to Sir Isaac Newton, a similar method was known to the ancient Babylonians. As devised by Newton, it was applied to solving polynomial equations; and it was only later that its usefulness in finding square roots was recognised.

The Newton Method’s greatest advantage is in its ability to extend the number of precise decimal places very quickly – it converges to the precise square root very quickly.

This is how the Newton Method works:

1. Choose the number for which you want to determine the square root.
2. Make a guess as to what the square root may be.
3. Apply the Newton Method to get a better guess (see below).
4. Keep applying the Newton Method until you get the required number of decimal places remaining unchanged in two successive guesses.
5. The final guess is precise to the required number of decimal places.

The Newton Method used to get a better guess for the square root of a number (designated as x) is as follows.

Approximation 1

Note that the right hand side of the above approximation is the average of the two numbers in parenthesis. In other words, the second guess is the average of the first guess and the number x divided by the first guess.

This is a fairly intuitive method, and it works like this:

Suppose our first guess is too big; then x divided by the first guess will be too small, and the average of those two numbers will be closer to the true value.

Suppose our first guess is too small; then x divided by the first guess will be too large, and the average of those two numbers will be closer to the true value.

It doesn’t matter whether our guess is too big, or too small – either way the average will be closer to the real value! All we have to do is keep taking new averages until we achieve the required decimal precision, or until the resulting value repeats (in which case we have the exact result, not an approximation).

Let’s use Newton’s Method to determine the square root of 2 (as we did before using the long division method). Let us also guess that the square root of 2 is 1.5.

Therefore, using Approximation 1, we calculate our next guess as follows.

Now, this can be done without using your calculator; but, because of the number of decimal places involved, you will be forgiven if you cheat. The answer is as follows.

As you can see, in only one iteration of the Newton Method we have a result precise to 2 decimal places.

Let’s get another guess.

Ok, use your calculator if you want to.

In only 2 iteration we have accuracy to 5 decimal places of precision! We will do one more iteration just to see where it gets us.

This gives us:

Compare that with:

Here we see that after only 3 iterations, Newton’s Method has provided an approximate result that is accurate to 11 decimal places of precision.

Now, even though we have (probably) used a calculator to do the number crunching, the potential for this method to be applied manually is very clear. Like the long division method, the manual calculations are tedious – but very easy to perform. However, the Newton Method does not require near as much manual calculation (as the long division method) to achieve rather impressive lengths of decimal precision. In fact the Newton Method at least doubles the decimal precision with each iteration.

Java Implementation of Newton’s Method

   /**
    * Newton's method for finding the square root of a number X is repeated
    * iteration of the formula:
    *       Guess(n+1) ~ (Guess(n) + X / Guess(n)) / 2
    * The iterations are repeated until the required decimal place precision is
    * achieved. The first guess is arbitrary. Here we simply use half of the 
    * number to be square rooted.
    * 
    * @param x The number to be square rooted.
    * @param precision The number of decimal place precision.
    * @return The square root of X to the required number of decimal places.
    */
    public static double Newtonsqrt(double x, int precision)
    {
        double  y = x / 2;                  // Our first "guess".
        boolean precisionAchieved = false;  // True if precision reached.
        long    precisionTest;              // Used to test if precision reached.
        int     count = 0;                  // Counts the number of iterations.
        
        while (!precisionAchieved)
        {
            // Increment the iteration count.
            count++;                                
            // The previous estimation shifted precision decimal places.
            precisionTest = (long) (y * Math.pow(10, precision)); 
            // Implement Newton's method.
            y = (y + (x / y)) / 2;               
            // Test to see if the required precision has been achieved.
            precisionAchieved = (long) (y * Math.pow(10, precision)) == precisionTest;
        }
        
        // Comment this next line out if not required.
        System.out.println("It took " + count + " iterations.");
        
        // Round to the required number of decimal places.
        double factor = Math.pow(10, precision);
        return (Math.round(y * factor) / factor);
    }