Monday, October 15, 2012

Simple Algo to compute the Square Root of a Number

Ever wondered how the square root of a number gets computed. Here's a simple algo which depicts the same. I have tried to first explain how we proceed with developing the algo and at the end I have given a small procedure which describes the above procedure in the form of a computer program. I hope it helps in your understanding of the computation of a square root.

So, let's get started. 


Problem
Given a number num, construct an algorithm to compute its square root.

Solution
Before starting to develop the algorithm, we must first understand what is meant by "square root of a number". Taking some specific examples, we know that the square root of 4 is 2, and the square root of 16 is 4 and so on. That is:

2 X 2 = 4
3 X 3 = 9
4 X 4 = 16
....

In the general case, the square root r of a number n is
     r X r = n                   ---------------------- (1)

We would derive our algorithm for finding the square root of a number with the above equation as our base.

Now, for example we want to find the square root of  81.

1. The first step would be to make an initial guess. (We'll discuss a point regarding how good this initial guess should be a little later. For now, just make an initial guess). Lets say, I make an initial guess of 20, i.e., I guess that 20 could be the square root of 81.

2.  To verify my initial guess, I calculate
         20 X 20 = 400, which is greater than 81.
Note that, from equation (1), we know that 20 should divide into 81 to give a quotient of 20 if it is the square root of  81. Instead, 20 divides into 81 to give 4.05.
       81/20 = 4.05
Squaring, 4.05 gives us 16.40 (rounded off to two digits), i.e.,
     4.05 X 4.05 = 16.40, which is less than 81.

Therefore, what we can conclude from above is that, our square root number should lie between 4.05 and 20, since, 20 is too large a number and 4.05 is too less a number to be the square root of 81.

3. Next, take the average of 20 and 4.05:
     (20 + 4.05)/2 = 12.025. This is an estimate between 20 and 4.05.

4. This new estimate might again be less, equal to, or greater than 81. Now, square the new estimate (or guess) :
    12.025 X 12.025 = 144. 60

5. Again, 144.60 is greater than 81. Therefore, divide this new estimate into 81:
    81/12.025 = 6.73
  Squaring 6.73, we get3
     6.73 X 6.73 = 45.29, which is less than 81.
Therefore, the square root number should lie between 12.025 and 6.73.

6. Take the average of these new estimates:
     (12.025 + 6.73)/2 = 9.38. This is an estimate between 20 and 4.05.

7. Again, square the new estimate:
     9.38 X 9.38 = 87.98
This is marginally more than our number, 81. But, still it is more than 81.

8. Proceed to dividing this new value into 81:
     81/9.38 = 8.63
Squaring 8.63 (should give us a value less than 81)
   8.63 X 8.63 = 74.48, which is less than 81.

9. Take the average of our new estimates:
    (9.38 + 8.63)/2 = 9.00
Squaring our new estimate gives us:
     9.00 X 9.00 = 81.

Thus, we take the approach of averaging our estimates and building upon those estimates. This approach would converge to our required square root pretty fast (even for bad initial estimates).

Only thing left is how to make a good initial guess for our estimate. Well, it does not matter much since the balancing mechanism (taking the average of the estimate and the complimentary value received by dividing the number by the estimate) of the algorithm will ensure that we rapidly converge on the square root. As for making a guess, we can take num/2 as our initial guess.

Following is an implementation of the above square root algorithm in java:

 double estimate1, estimate2;  
         double number = 81;  
         double error = 0.001;  
         if (number <= 0)  
             return;  
         estimate1 = number / 2;  
         estimate2 = (estimate1 + number / estimate1) / 2;  
         while (Math.abs(estimate1 - estimate2) > error) {  
             System.out.println("-->" + Math.abs(estimate1 - estimate2) + "--> "  
                     + error);  
             estimate1 = estimate2;  
             estimate2 = (estimate1 + number / estimate1) / 2;  
         }  
         if (Math.abs(estimate2 * estimate2 - number) <= Math.abs(estimate1  
                 * estimate1 - number)  
                 && Math.abs(estimate1 - estimate2) < error) {  
             System.out.println("square root is: " + estimate2);  
         }  

Feel free to use this code and improve upon it. And, then suggest your improvements to me as well.

Thank You and Happy Coding.

5 comments:

  1. Nice! Will this approach work for very small numbers, like 0.00001?

    ReplyDelete
    Replies
    1. Yes, it will work.. you can try it out with the above code..

      Delete
  2. A recursive version of this function would be much more elegant. This function works, but it looks a bit messy.

    ReplyDelete
  3. What you've described is called the bisection method (http://en.wikipedia.org/wiki/Bisection_method).

    ReplyDelete
  4. I don't get this shit!!!

    ReplyDelete