Bakhshali Approximation is a mathematical method of finding an approximation to a square root of a number. It is equivalent to two iterations of Babylonian Method.
Algorithm:
To calculate sqrt(S). Step 1: Calculate nearest perfect square to S i.e (N2). Step 2: Calculate d = S - (N2) Step 3: Calculate P = d/(2*N) Step 4: Calculate A = N + P Step 5: Sqrt(S) will be nearly equal to A - (P2/2*A)
Below is the implementation of above steps.
Implementation:
C++
//This program gives result approximated to 5 decimal places.#include <iostream>float sqroot(float s){ int pSq = 0; //This will be the nearest perfect square to s int N = 0; //This is the sqrt of pSq // Find the nearest perfect square to s for (int i = static_cast<int>(s); i > 0; i--) { for (int j = 1; j < i; j++) { if (j*j == i) { pSq = i; N = j; break; } } if (pSq > 0) break; } float d = s - pSq; //calculate d float P = d/(2.0*N); //calculate P float A = N+P; //calculate A float sqrt_of_s = A-((P*P)/(2.0*A)); //calculate sqrt(S). return sqrt_of_s;}// Driver program to test above functionint main(){ float num = 9.2345; float sqroot_of_num = sqroot(num); std::cout << "Square root of "<<num<<" = "<<sqroot_of_num; return 0;} |
Java
// Java program gives result approximated// to 5 decimal places.class GFG { static float sqroot(float s) { // This will be the nearest perfect square to s int pSq = 0; //This is the sqrt of pSq int N = 0; // Find the nearest perfect square to s for (int i = (int)(s); i > 0; i--) { for (int j = 1; j < i; j++) { if (j*j == i) { pSq = i; N = j; break; } } if (pSq > 0) break; } // calculate d float d = s - pSq; // calculate P float P = d/(2.0f*N); // calculate A float A = N+P; // calculate sqrt(S). float sqrt_of_s = A-((P*P)/(2.0f*A)); return sqrt_of_s; } // Driver program public static void main (String[] args) { float num = 9.2345f; float sqroot_of_num = sqroot(num); System.out.print("Square root of "+num+" = " + Math.round(sqroot_of_num*100000.0)/100000.0); }}// This code is contributed by Anant Agarwal. |
Python3
# This Python3 program gives result# approximated to 5 decimal places.def sqroot(s): # This will be the nearest # perfect square to s pSq = 0; # This is the sqrt of pSq N = 0; # Find the nearest # perfect square to s for i in range(int(s), 0, -1): for j in range(1, i): if (j * j == i): pSq = i; N = j; break; if (pSq > 0): break; d = s - pSq; # calculate d P = d / (2.0 * N); # calculate P A = N + P; # calculate A # calculate sqrt(S). sqrt_of_s = A - ((P * P) / (2.0 * A)); return sqrt_of_s;# Driver Codenum = 9.2345;sqroot_of_num = sqroot(num);print("Square root of ", num, "=", round((sqroot_of_num * 100000.0) / 100000.0, 5));# This code is contributed by mits |
C#
// C# program gives result approximated// to 5 decimal places.using System;class GFG { static float sqroot(float s) { // This will be the nearest // perfect square to s int pSq = 0; //This is the sqrt of pSq int N = 0; // Find the nearest perfect square to s for (int i = (int)(s); i > 0; i--) { for (int j = 1; j < i; j++) { if (j * j == i) { pSq = i; N = j; break; } } if (pSq > 0) break; } // calculate d float d = s - pSq; // calculate P float P = d / (2.0f * N); // calculate A float A = N + P; // calculate sqrt(S). float sqrt_of_s = A-((P * P) / (2.0f * A)); return sqrt_of_s; } // Driver Code public static void Main () { float num = 9.2345f; float sqroot_of_num = sqroot(num); Console.Write("Square root of "+num+" = "+ Math.Round(sqroot_of_num * 100000.0) / 100000.0); }}// This code is contributed by Nitin Mittal. |
PHP
<?php// This PHP program gives result// approximated to 5 decimal places.function sqroot($s){ // This will be the nearest // perfect square to s $pSq = 0; //This is the sqrt of pSq $N = 0; // Find the nearest // perfect square to s for ($i = intval($s); $i > 0; $i--) { for ($j = 1; $j < $i; $j++) { if ($j * $j == $i) { $pSq = $i; $N = $j; break; } } if ($pSq > 0) break; } $d = $s - $pSq; //calculate d $P = $d / (2.0 * $N); //calculate P $A = $N + $P; //calculate A //calculate sqrt(S). $sqrt_of_s = $A - (($P * $P) / (2.0 * $A)); return $sqrt_of_s;}// Driver Code$num = 9.2345;$sqroot_of_num = sqroot($num);echo "Square root of ". $num ." = " . round(($sqroot_of_num * 100000.0) / 100000.0, 5);// This code is contributed by Sam007?> |
Javascript
<script>// javascript program gives result approximated// to 5 decimal places.{function sqroot(s){ // This will be the nearest perfect square to s var pSq = 0; // This is the sqrt of pSq var N = 0; // Find the nearest perfect square to s for (i = parseInt(s); i > 0; i--) { for (j = 1; j < i; j++) { if (j*j == i) { pSq = i; N = j; break; } } if (pSq > 0) break; } // calculate d var d = s - pSq; // calculate P var P = (d/(2.0*N)); // calculate A var A = N+P; // calculate sqrt(S). var sqrt_of_s = A-((P*P)/(2.0*A)); return sqrt_of_s;} // Driver program var num = 9.2345;var sqroot_of_num = sqroot(num);document.write("Square root of "+num+" = " + (Math.round(sqroot_of_num*100000.0)/100000.0).toFixed(6));// This code is contributed by Princi Singh </script> |
Output :
Square root of 9.2345 = 3.03883
Illustration:
find sqrt(9.2345) S = 9.2345 N = 3 d = 9.2345 – (3^2) = 0.2345 P = 0.2345/(2*3) = 0.0391 A = 3 + 0.0391 = 3.0391 therefore, sqrt(9.2345) = 3.0391 – (0.0391^2/(2*0.0391)) = 3.0388
Important Points:
- Used to find approximation to a square root.
- Requires the value of nearest perfect square of the number whose square root is needed to be calculated.
- More efficient for floating point numbers than integers as it finds approximation.
Reference:
https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Bakhshali_approximation
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
