Developing your algorithmic thinking skills is a great idea whatever your programming goals are. As well as making you a much better programmer, you will also need to develop theses skills if you want to apply for software development jobs with prestigious companies such as Facebook, Google, Amazon etc., along with many less famous yet still awesome companies. It’s just as well algorithmic thinking happens to be fascinating in its own right as a form of mental sport!
The Babylonian Algorithm for finding square roots is impressive both because of its effectiveness and its age. You may be surprised to learn that although this algorithm over is 3000 years old, it is still used today in modern calculators.
The basic approach used in the algorithm is guess, check, improve, repeated until the required level of precision is reached.
The algorithm depends of the fact that if x is an overestimate for the square root of a positive number S, then S/x will be an underestimate, and so the average of these two provides a better approximation (and vice versa, for an underestimate). We can then repeat the process until we reach a suitably precise answer.
Confused? Let’s look at a concrete example:
Calculating √5 Using the Babylonian Algorithm
We start with an “educated guess” for what the square root of 5 might be. Let’s choose 2. Since 2 is an underestimate (we know this because 2² < 5), 5/2 is an overestimate.
Think about why this is true.
5 divided by a number which is less than its square root will give a value greater than its square root.
Here’s a short detour to emphasize this point, using an actual square number to make it clearer:
8 is the square root of 64. if I divide 64 by 7, I get a number bigger than 8. That is, 9.14 ( to 2 d.p.). It’s like a see-saw with the exact square root in the middle…
In our √5 example, if you start with guessing 3 for √5, your estimate is too large (since 3² = 9), so √5 / 3 will be too small.
Here’s the key to the algorithm:
The mean* of an overestimate and an underestimate may reasonably be expected to provide a better approximation to the actual value.
* often called “average” in a vague colloquial sense which leads to all sorts of misunderstanding of the prevalent aspects of the situation being discussed, but that is another story…
We can tabulate the process of finding √5 using the Babylonian algorithm like so:
x 5/x Mean
2.000000 2.500000 2.250000
2.250000 2.222222 2.236111
2.236111 2.236025 2.236068
2.236068 2.236068 2.236068
2.236068 2.236068 2.236068
x represents our guess each time. (Actually it’s only a guess the first time, after that, the algorithm takes over and calculates successive values of x for you, according to the relation shown by this equation.
Don’t be fazed if you are not familiar with this kind of notation though. Some people are more comfortable with mathematical notation than others. If it helps, you can refer to these mathematical facts to help you understand, but it is perfectly possible to think purely in algorithmic terms to grasp how the algorithm works.
To calculate √a, notice that
x . ᵃ⁄ₓ = a = √a . √aIf x < √a, then ᵃ⁄ₓ > √aIf x > √a, then ᵃ⁄ₓ < √a
What the equation is basically saying is, “each new x value is the mean calculated in the previous row”.
You should try this process out for yourself on paper until you get a good feel for how it works. Note that the 5 in the5/x column heading below is the number whose square root we are trying to find. It does not change throughout the algorithm. All the values below are displayed with the defualt precision for a float using pythons f-strings.
Compare the result to Python’s value for √5 (calculated without using math.sqrt, since x ** 0.5 = √x.
>>> 5 ** 0.5
2.23606797749979
Python implementation of the Babylonian Square Root Algorithm
So how to implement this in Python?
Have a go at implementing this algorithm for yourself. For this first attempt, just use a fixed number of iterations (inside a for loop) rather than worrying about when to stop the algorithm. That will come next. Please note also that for the purposes of this article, we are only discussing positive square roots.
If you want a staring point, you can use the template code below.
def babylonian_algorithm(S, x):
print(f"x\t\t{S}/x\t\tMean") # f-strings for displaying vars in string. \t for tab (spacing)
for i in range(5): # Just five iterations for now.
...
...
print(f"{x:f}\t{estimate:f}\t{mean:f}")
...
return x
S = 5 # Number to find the square root of
x = 2 # Initial guess
print(f"The square root of {n} is close to {round(babylonian_algorithm(S, x), 6)}")
Here’s a possible solution. Don’t worry if yours is different, as long as it works.
Improved Python implementation of the Babylonian Square Root Algorithm
It’s reasonably easy for human to guess a sensible initial value for the square root. However, computers don’t have the awareness to perform this task. In the second implementation of the algorithm we use the value of S (the number we wish to find the square root of) as our initial guess. We then determine whether each successive guess brings us to within an acceptable range of out target value
Because of rounding errors, you should never rely on equality of doubles or floats. You need another method for determining when your approximation will be good enough.
Here is another Python implementation of the Babylonian Square Root Algorithm:
def babylonian_algorithm(S):
e = 0.00001
mean = (S + 1) / 2 # This is the first pass of the algorithm
print(f"x\t\t{S}/x\t\tMean")
while abs(mean ** 2 - S) > e:
estimate = S / mean
mean = (mean + estimate) / 2
print(f"{mean:f}\t{estimate:f}\t{mean:f}")
return mean
S = 5 # Number to find the square root of
print(f"\nThe square root of {S} is close to {babylonian_algorithm(S):f}\n")
S = 64 # Number to find the square root of
print(f"\nThe square root of {S} is close to {babylonian_algorithm(S):f}")
This version uses while abs(mean ** 2 - S) > e to check whether an estimate is within e of the correct answer.
x 5/x Mean
2.333333 1.666667 2.333333
2.238095 2.142857 2.238095
2.236069 2.234043 2.236069
The square root of 5 is close to 2.236069
x 64/x Mean
17.234615 1.969231 17.234615
10.474036 3.713457 10.474036
8.292192 6.110347 8.292192
8.005148 7.718104 8.005148
8.000002 7.994855 8.000002
8.000000 7.999998 8.000000
The square root of 64 is close to 8.000000
>>>
Depending on your level of experience, the Babylonian Square Root Algorithm may seem a little complex and hard to understand, or you may find it straight-forward. If it is hard for you, one tip is to focus on just one small aspect of the algorithm at a time until you understand that part, then do the same for the other parts. It is OK to forget the big picture temporarily. Either way, adding this algorithm to your knowledge database is going to help to develop your mastery of algorithmic thinking.
I hope you found this article interesting. If so, please share on social media, and also consider joining the Compucademy mailing list using one of the forms on this page.
Happy computing!