Skip to content

Instantly share code, notes, and snippets.

@0x000000AC
Created June 2, 2012 12:12
Show Gist options
  • Save 0x000000AC/2858078 to your computer and use it in GitHub Desktop.
Save 0x000000AC/2858078 to your computer and use it in GitHub Desktop.
Babylonian Algorithm for Square Roots in Java
/* The reason I created this was two-fold. 1. To learn Java 2. To learn about numerical analysis and numerical methods of arithmetic.
This code shows that the Babylonian Method of computing square roots is as accurate as the Java numerical method using sqrt() after as few
as 10 iterations for numbers within the limits of a double. I'm certain that it can be improved (and I have no vanity of authorship i.e., I welcome
criticism aaron.paul.clark@gmail.com). I love learning and sharing what I find, if you have some math-related code you're itching to share please
let me know!
There are numerous methods for computing square roots (http://en.wikipedia.org/wiki/Methods_of_computing_square_roots).
"The basic idea is that if x is an overestimate to the square root of a non-negative real number S then S/x will be an underestimate and so the average
of these two numbers may reasonably be expected to provide a better approximation."
"This is a quadratically convergent algorithm, which means that the number of correct digits of the approximation roughly doubles with each iteration."
Steps:
1. Begin with an arbitrary positive starting value x0 (the closer to the actual square root of S, the better).
2. Let xn+1 be the average of xn and S / xn (using the arithmetic mean to approximate the geometric mean).
3. Repeat step 2 until the desired accuracy is achieved.
One day I found myself asking how square roots are computed and then travelled down the rabbit hole.
*/
import java.io.*;
import static java.lang.Math.*;
public class BabylonianSqrt5 {
public static void main(String[] args) {
//Prompt the user to input the integer they wish to square.
//S is the variable the user input will be stored to
System.out.print("Enter the integer you wish to square: ");
BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
String S = null;
try {
S = br.readLine();
} catch (IOException e) {
System.out.println("Error!");
System.exit(1);
}
//Input is now saved in the variable "S" The Babylonian Method of finding square-roots is employed
//We need to find out how many digits long the user input S is. This code section takes care of that and stores
//the result to the int SigFigs. This int will be used in the next section of the code to approximate a starting
//value (seed value) that will be iterated 9 additional times to come to a result.
int SigFigs = 0;
for (int i = 0, len = S.length(); i < len; i++) {
if (Character.isDigit(S.charAt(i))) {
SigFigs++;
}
}
//This is the next section will set up either using 2*10^n or 6*10^n based on if S is an even or odd amount of digits long
// If even, the 6*10^n method will be used. If odd, 2*10^n will be used. n in this case is the log of the SigFigs divided
// by log 2 -- this will give n.
if (SigFigs % 2 == 0) //modulus is used here to see if the string is even/odd. The idea here is that if something is even, it's divisible by 2 and will use the 6*10^n method etc.
{
//Stuff here for 6*10^n My variables are kind of random letters. Sorry.
double V = log(SigFigs)/log(2);
double G = Math.round(V); // The division isn't always a round integer, so Math.round is used.
double R = Integer.parseInt(S);
double x0 = 6*(Math.pow(10,G));
double x1 = (0.5)*((x0)+(R/x0));
double x2 = (0.5)*((x1)+(R/x1));
double x3 = (0.5)*((x2)+(R/x2));
double x4 = (0.5)*((x3)+(R/x3));
double x5 = (0.5)*((x4)+(R/x4));
double x6 = (0.5)*((x5)+(R/x5));
double x7 = (0.5)*((x6)+(R/x6));
double x8 = (0.5)*((x7)+(R/x7));
double x9 = (0.5)*((x8)+(R/x8));
double x10 = (0.5)*((x9)+(R/x9));
String str = Double.toString(x10);
System.out.println("Square root of " + S + " by the Babylonian Guess/iteration method is approximately " +str);
}
else
{
//stuff here fo 2*10^n
double V = log(SigFigs)/log(2);
double G = Math.round(V);
double R = Integer.parseInt(S);
double x0 = 2*(Math.pow(10,G));
double x1 = (0.5)*((x0)+(R/x0));
double x2 = (0.5)*((x1)+(R/x1));
double x3 = (0.5)*((x2)+(R/x2));
double x4 = (0.5)*((x3)+(R/x3));
double x5 = (0.5)*((x4)+(R/x4));
double x6 = (0.5)*((x5)+(R/x5));
double x7 = (0.5)*((x6)+(R/x6));
double x8 = (0.5)*((x7)+(R/x7));
double x9 = (0.5)*((x8)+(R/x8));
double x10 =(0.5)*((x9)+(R/x9));
String str = Double.toString(x10);
System.out.println("Square root of " + S + " is approximately " +str);
}
//Section to show Java's own approximation of the squre root of the user's input.
double M = Integer.parseInt(S);
double B = sqrt(M);
System.out.println("Compare this to the java Sqrt() function result: " + B);
}
}
@ManishaJalota
Copy link

This is a very complex hardcored program

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment