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:

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.

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:

- Guess a solution for sqrt(x), say g
- Check whether the current value of guess is "good enough" (square roots can be irrational, so exact value is often not achievable)
- If the guess is not "good enough", compute the new guess by updating g=(g+x/g)/2
- Go back to step 2

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 !