Tuesday, February 15, 2011

Algorithm for finding square-root

It always intrigued me how one could find the square-root of a number. In school I was taught a digit-by-digit method to calculate square-root. I did implement it using BASIC in Std IX, but the solution did not seem elegant enough. By Std XI I had actually figured out the Bisection method by myself and used it to find any root of a number. This again was implemented in C++ (... and I still have the code !).

Then in my B.Sc. I was formally introduced to the Newton-Raphson method and I have been using that ever since. At about this time only a classmate told me of the logarithm based method, which (if Wikipedia is to be believed) is the method of choice for most implementation of sqrt().

Recently I have been going through the MIT open course, Structure and Interpretation of Computer Programs. While watching the original 1981 videos, I came across this brilliant algorithm which was supposedly invented by the Babylonians around 2000 years back. It is also often attributed to Heron of Alexandria, who was also a great inventor (the link to his biography in Wikipedia has a section on his inventions ... looks impressive to me).

Heron's Algorithm can be derived from the Newton-Raphson method and can be considered to be a special case of that. The brilliance however lies in the fact that it precedes Newton-Raphson by 1600+ years. The algorithm is very simple:
  1. Guess a solution for sqrt(x), say g
  2. Check whether the current value of guess is "good enough" (square roots can be irrational, so exact value is often not achievable)
  3. If the guess is not "good enough", compute the new guess by updating  g=(g+x/g)/2
  4. Go back to step 2
You know from my last post that I have recently been learning Python. So here is a python implementation of the above algorithm.

Once again, please let me know if you find any bugs in the implementation. I am a Python newbie and your suggestions can help me improve.

No comments:

Post a Comment

I'd love to hear from you !