One of the first things that many people learn in an introduction to Computer Sciences course is the algorithm for calculating the square root of a number. The algorithm, which is often attributed to Heron of Alexandria, is as follows:

  1. Formulate a guess.
  2. Multiply that guess by itself.  If the product is “close enough” to the original number, you will stop here because you have found what you will call the square root of the number.
  3. Otherwise you formulate an new guess by taking the average of the first guess and the original number divided by the previous guess.
  4. Go back to step 2.

Now let’s actually consider an example of finding the square root of a number:

  1. 25 will be the number whose square root we are trying to find.
  2. We can use 7 as our first guess.
  3. The product of 7 × 7 is 49.
  4. Since 49 isn’t close enough to 25 we will create a new guess by doing the following:
    (guess + number / guess) / 2 = (7 + 25 / 7) / 2 ≈ 5.29
  5. The product of 5.29 × 5.29 is about 27.98.
  6. Since 27.98 isn’t close enough to 25 we will create a new guess by doing the following:
    (guess + number / guess) / 2 = (5.29 + 25 / 5.29) / 2 ≈ 5.01
  7. The product of 5.01 × 5.01 is 25.1.
  8. We can say that 25.1 is close enough to 25.  Therefore we will say that the approximate square root of 25 is 5.01.

It seems that even more than 2100 years later, Heron’s algorithm still has application for current technologies.  Now the question is, how can you implement this in a computer so that it computes the square root (and perhaps with more accuracy)?  Here is an implementation in JavaScript:


function sqrt(num) {
  // Create an initial guess by simply dividing by 3.
  var lastGuess, guess = num / 3;

  // Loop until a good enough approximation is found.
  do {
    lastGuess = guess;  // store the previous guess

    // find a new guess by averaging the old one with
    // the original number divided by the old guess.
    guess = (num / guess + guess) / 2;

  // Loop again if the product isn't close enough to
  // the original number.
  } while(Math.abs(lastGuess - guess) > 5e-15);

  return guess;  // return the approximate square root
};

If you notice, the above function is written a little bit different than the algorithm that was outlined. First of all, my initial guess of simply dividing the number by 3 isn’t really considered as a possible approximation. Instead, I take that and find the average right off the bat. Also, I have established a threshold of 5e-15 which actually determines whether or not my approximation is close enough. If the positive difference between the last guess and the current guess is greater than that threshold, another approximation will be made. The following shows this implemented in a web page:
Square Root Implementation

How cool is that!  An extremely accurate approximation for the square root of a number can quickly be determined using Heron’s algorithm.  Let me know if you have any questions or comments.

P.S. This post was inspired by the lecture for the intro to CS from edX.org.


3 Comments

Adam D · June 30, 2014 at 11:17 AM

I think your description of the algorithm is written incorrectly. I could never get close to the result… Please refer to http://www.mathsisfun.com/square-root.html

kyle hamilton · August 25, 2014 at 12:15 PM

Just for fun, you could do better for the seed:

Instead of always using 3, you could use 10 to the power of half the number of digits in num. This will result in fewer steps to compute.


var seed = Math.pow(10, num.length/2);
var lastGuess, guess = num / seed;

osaze · June 17, 2015 at 9:36 AM

Sleazy but correct!!!!!

function compute_sqrt(n) {
for(var i=0;i*i<=n;i++){
var a=i;
}
return a;
}

Leave a Reply to kyle hamilton Cancel reply

Your email address will not be published. Required fields are marked *