Skip to main content

Babylonian method for square root

The Babylonian method, also known as the Heron's method, is an ancient technique to approximate the square root of a number. It's an iterative algorithm that refines an initial guess for the square root of a given number until it reaches a desired level of precision. This method is especially interesting because it demonstrates how ancient civilizations developed mathematical techniques to solve complex problems.

Problem Statement

The problem is to find an efficient way to calculate the square root of a given positive number. The square root of a number x is a value y such that y multiplied by itself equals x. Mathematically, y = √x.

For example, if we want to find the square root of 64, we are looking for a value y such that y × y = 64. In this case, the square root of 64 is 8.

Idea to Solve the Problem

The Babylonian method for finding the square root of a number involves iterative refinement. The basic idea is to start with an initial guess for the square root and then iteratively update the guess to get closer to the actual square root.

Let's consider an example to understand the process better. Suppose we want to find the square root of x using an initial guess y0. We can refine our guess using the following formula:

y1 = (y0 + x / y0) / 2

Here, y1 is a better approximation of the square root than y0. We can repeat this process iteratively:

y2 = (y1 + x / y1) / 2 y3 = (y2 + x / y2) / 2 ...

The iterations continue until the difference between consecutive guesses becomes smaller than a specified precision value.

Pseudocode

function findSquareRoot(num)
    a = num
    b = 1.0
    precision = 0.000001
    
    while (a - b) > precision
        a = (a + b) / 2.0
        b = num / a
    
    return a

Algorithm Explanation

  1. Initialize two variables, a and b, both initially set to the given number num and 1.0 respectively. Also, define a precision value that specifies the desired level of accuracy (e.g., 0.000001).

  2. Enter a loop that continues as long as the difference between a and b is greater than the defined precision. This loop is responsible for iteratively refining the guess.

  3. Within the loop, update the value of a by taking the average of a and b. This update brings a closer to the actual square root.

  4. Update the value of b by dividing num by the new value of a. This step ensures that b remains inversely proportional to a, allowing the iteration to converge towards the square root.

  5. Once the loop exits (i.e., the difference between a and b becomes smaller than the precision), a holds a close approximation of the square root of num.

  6. Return the value of a as the estimated square root of num.

Code Solution

// C program
// babylonian method for square root
#include <stdio.h>

void findSquareRoot(double num)
{
	double a = num;
	double b = 1.0;
	// Here precision (0.000001)
	while ((a - b) > 0.000001)
	{
		a = (a + b) / 2.0;
		b = num / a;
	}
	// Display given number
	printf("\n Given Number : %lf", num);
	// Display the calculate square root
	printf("\n Square Root  : %lf\n", a);
}
int main(int argc, char
	const *argv[])
{
	// Test
	findSquareRoot(64);
	findSquareRoot(10.3);
	findSquareRoot(17.50);
	return 0;
}

Output

 Given Number : 64.000000
 Square Root  : 8.000000

 Given Number : 10.300000
 Square Root  : 3.209361

 Given Number : 17.500000
 Square Root  : 4.183300
// Java program
// Babylonian method for square root
public class SquareRoot
{
	public void findSquareRoot(double num)
	{
		double a = num;
		double b = 1.0;
		// Here precision (0.000001)
		while ((a - b) > 0.000001)
		{
			a = (a + b) / 2.0;
			b = num / a;
		}
		// Display given number
		System.out.print("\n Given Number : " + num);
		// Display the calculate square root
		System.out.print("\n Square Root : " + a + "\n");
	}
	public static void main(String[] args)
	{
		SquareRoot task = new SquareRoot();
		// Test
		task.findSquareRoot(64);
		task.findSquareRoot(10.3);
		task.findSquareRoot(17.50);
	}
}

Output

 Given Number : 64.0
 Square Root : 8.00000000000017

 Given Number : 10.3
 Square Root : 3.209361314240489

 Given Number : 17.5
 Square Root : 4.183300132670613
// Include header file
#include <iostream>
using namespace std;

// C++ program
// Babylonian method for square root

class SquareRoot
{
	public: void findSquareRoot(double num)
	{
		double a = num;
		double b = 1.0;
		// Here precision (0.000001)
		while ((a - b) > 0.000001)
		{
			a = (a + b) / 2.0;
			b = num / a;
		}
		// Display given number
		cout << "\n Given Number : " << num;
		// Display the calculate square root
		cout << "\n Square Root : " << a << "\n";
	}
};
int main()
{
	SquareRoot task = SquareRoot();
	// Test
	task.findSquareRoot(64);
	task.findSquareRoot(10.3);
	task.findSquareRoot(17.50);
	return 0;
}

Output

 Given Number : 64
 Square Root : 8

 Given Number : 10.3
 Square Root : 3.20936

 Given Number : 17.5
 Square Root : 4.1833
// Include namespace system
using System;
// C# program
// Babylonian method for square root
public class SquareRoot
{
	public void findSquareRoot(double num)
	{
		double a = num;
		double b = 1.0;
		// Here precision (0.000001)
		while ((a - b) > 0.000001)
		{
			a = (a + b) / 2.0;
			b = num / a;
		}
		// Display given number
		Console.Write("\n Given Number : " + num);
		// Display the calculate square root
		Console.Write("\n Square Root : " + a + "\n");
	}
	public static void Main(String[] args)
	{
		SquareRoot task = new SquareRoot();
		// Test
		task.findSquareRoot(64);
		task.findSquareRoot(10.3);
		task.findSquareRoot(17.50);
	}
}

Output

 Given Number : 64
 Square Root : 8.00000000000017

 Given Number : 10.3
 Square Root : 3.20936131424049

 Given Number : 17.5
 Square Root : 4.18330013267061
<?php
// Php program
// Babylonian method for square root
class SquareRoot
{
	public	function findSquareRoot($num)
	{
		$a = $num;
		$b = 1.0;
		// Here precision (0.000001)
		while (($a - $b) > 0.000001)
		{
			$a = (($a + $b) / 2.0);
			$b = ($num / $a);
		}
		// Display given number
		echo "\n Given Number : ". $num;
		// Display the calculate square root
		echo "\n Square Root : ". $a ."\n";
	}
}

function main()
{
	$task = new SquareRoot();
	$task->findSquareRoot(64);
	$task->findSquareRoot(10.3);
	$task->findSquareRoot(17.50);
}
main();

Output

 Given Number : 64
 Square Root : 8.0000000000002

 Given Number : 10.3
 Square Root : 3.2093613142405

 Given Number : 17.5
 Square Root : 4.1833001326706
// Node Js program
// Babylonian method for square root
class SquareRoot
{
	findSquareRoot(num)
	{
		var a = num;
		var b = 1.0;
		// Here precision (0.000001)
		while ((a - b) > 0.000001)
		{
			a = ((a + b) / 2.0);
			b = (num / a);
		}
		// Display given number
		process.stdout.write("\n Given Number : " + num);
		// Display the calculate square root
		process.stdout.write("\n Square Root : " + a + "\n");
	}
}

function main()
{
	var task = new SquareRoot();
	// Test
	task.findSquareRoot(64);
	task.findSquareRoot(10.3);
	task.findSquareRoot(17.50);
}
main();

Output

 Given Number : 64
 Square Root : 8.00000000000017

 Given Number : 10.3
 Square Root : 3.209361314240489

 Given Number : 17.5
 Square Root : 4.183300132670613
#  Python 3 program
#  Babylonian method for square root
class SquareRoot :
	def findSquareRoot(self, num) :
		a = num
		b = 1.0
		#  Here precision (0.000001)
		while ((a - b) > 0.000001) :
			a = ((a + b) / 2.0)
			b = (num / a)
		
		#  Display given number
		print("\n Given Number : ", num, end = "")
		#  Display the calculate square root
		print("\n Square Root : ", a )
	

def main() :
	task = SquareRoot()
	#  Test
	task.findSquareRoot(64)
	task.findSquareRoot(10.3)
	task.findSquareRoot(17.50)

if __name__ == "__main__": main()

Output

 Given Number :  64
 Square Root :  8.00000000000017

 Given Number :  10.3
 Square Root :  3.209361314240489

 Given Number :  17.5
 Square Root :  4.183300132670613
#  Ruby program
#  Babylonian method for square root
class SquareRoot 
	def findSquareRoot(num) 
		a = num
		b = 1.0
		#  Here precision (0.000001)
		while ((a - b) > 0.000001) 
			a = (a + b) / 2.0
			b = num / a
		end

		#  Display given number
		print("\n Given Number : ", num)
		#  Display the calculate square root
		print("\n Square Root : ", a ,"\n")
	end

end

def main() 
	task = SquareRoot.new()
	#  Test
	task.findSquareRoot(64)
	task.findSquareRoot(10.3)
	task.findSquareRoot(17.50)
end

main()

Output

 Given Number : 64
 Square Root : 8.00000000000017

 Given Number : 10.3
 Square Root : 3.209361314240489

 Given Number : 17.5
 Square Root : 4.183300132670613

// Scala program
// Babylonian method for square root
class SquareRoot
{
	def findSquareRoot(num: Double): Unit = {
		var a: Double = num;
		var b: Double = 1.0;
		// Here precision (0.000001)
		while ((a - b) > 0.000001)
		{
			a = ((a + b) / 2.0);
			b = (num / a);
		}
		// Display given number
		print("\n Given Number : " + num);
		// Display the calculate square root
		print("\n Square Root : " + a + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SquareRoot = new SquareRoot();
		// Test
		task.findSquareRoot(64);
		task.findSquareRoot(10.3);
		task.findSquareRoot(17.50);
	}
}

Output

 Given Number : 64.0
 Square Root : 8.00000000000017

 Given Number : 10.3
 Square Root : 3.209361314240489

 Given Number : 17.5
 Square Root : 4.183300132670613
// Swift 4 program
// Babylonian method for square root
class SquareRoot
{
	func findSquareRoot(_ num: Double)
	{
		var a: Double = num;
		var b: Double = 1.0;
		// Here precision (0.000001)
		while ((a - b) > 0.000001)
		{
			a = (a + b) / 2.0;
			b = num / a;
		}
		// Display given number
		print("\n Given Number : ", num, terminator: "");
		// Display the calculate square root
		print("\n Square Root : ", a );
	}
}
func main()
{
	let task: SquareRoot = SquareRoot();
	// Test
	task.findSquareRoot(64);
	task.findSquareRoot(10.3);
	task.findSquareRoot(17.50);
}
main();

Output

 Given Number :  64.0
 Square Root :  8.00000000000017

 Given Number :  10.3
 Square Root :  3.20936131424049

 Given Number :  17.5
 Square Root :  4.18330013267061
// Kotlin program
// Babylonian method for square root
class SquareRoot
{
	fun findSquareRoot(num: Double): Unit
	{
		var a: Double = num;
		var b: Double = 1.0;
		// Here precision (0.000001)
		while ((a - b) > 0.000001)
		{
			a = (a + b) / 2.0;
			b = num / a;
		}
		// Display given number
		print("\n Given Number : " + num);
		// Display the calculate square root
		print("\n Square Root : " + a + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: SquareRoot = SquareRoot();
	// Test
	task.findSquareRoot(64.0);
	task.findSquareRoot(10.3);
	task.findSquareRoot(17.50);
}

Output

 Given Number : 64.0
 Square Root : 8.00000000000017

 Given Number : 10.3
 Square Root : 3.209361314240489

 Given Number : 17.5
 Square Root : 4.183300132670613

Time Complexity

The time complexity of the Babylonian method for finding the square root is primarily determined by the number of iterations needed for the algorithm to converge to the desired precision. In each iteration, we perform simple arithmetic operations.

Since the number of iterations required depends on the initial guess and the precision level, it's generally challenging to provide a precise time complexity analysis. However, the Babylonian method is known for its rapid convergence, which means that it usually requires a small number of iterations to reach a high level of accuracy.

In practical terms, the Babylonian method's time complexity can be considered to be approximately O(log N), where N is the number of bits used to represent the input number. This is due to the rapid convergence of the method.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment