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
-
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).
-
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.
-
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.
-
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.
-
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.
-
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.
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