Square Root Estimation Algorithms

square-rootCalculating the square value of a number is a very straightforward
process which consists of multiplying this number by itself. For instance:

152 = 15 x 15 = 225

The reverse operation which consists of calculating the square root of a number is not so easy without using the square root function of a calculator. In this blog post we will investigate how to accurately calculate the square root of a number using Python and we will then implement and compare two methods that were used a few centuries ago to estimate the square root value of any given number:

  • The Babylonian Method,
  • The Bakhshali Method.

Exponentiation

High level programming languages such as Python have an arithmetic operator to raise a number to the power of an exponent.

In pseudocode the exponentiation operator is the ^ operator.
For instance: 32 appears as 3^2 when using pseudocode.

In Python, the exponentiation operator is **. e.g.:

Square Root = To the power of half

We can easily calculate the square root of a number in a computer program using the exponentiation operator knowing that:

√x = x½ = x0.5

So in Python:

The Babylonian method

Procedures for calculating/estimating square roots have been known since at least the period of ancient Babylon in the 17th century BCE. Heron’s method (aka Babylonian method) from first century Egypt was the first ascertainable algorithm for computing square root.

This approach is based on estimating the limit of the following convergent sequence:
babylonian-square-root

To implement the Babylonian method of estimating a square root we will use the following algorithm:
square-root-flowchart

Python Code

Use the above flowchart to complete the code below:

The Bakhshali method

This method for finding an approximation to a square root was described in an ancient Indian mathematical manuscript called the Bakhshali manuscript. It uses a similare approach the Babylonian method using a different convergent series as described below:

bakhshali-square-root

Your task is to adapt your Python script to implement the Bakhshali method and compare how both series perform to estimate a square root value using a fixed number of iterations.

Share Button