Problem: Write a routine to find the square root of any given number N.
Solution: Square root can be found if we observe the following:
If x is larger than the exact square root of of N, then N/x will be smaller than the exact square root of N
So, if we start with x as an approximation of the square root, then a better approximation can be obtained by xbetter = x + N/x
The above relation is repeatedly used unless the error between N and x2 becomes acceptable.
public class SquareRoot {
static double squareRoot (double n)
{
double x = n/2;
double sq = x*x;
while ( Math.abs(n - sq) > 0.00001)
{
x = (x + n/x) / 2;
sq = x*x;
}
return x;
}
static java.text.DecimalFormat df = new DecimalFormat ("###.####");
public static void main(String[] args)
{
for (int i=1; i<100; i++)
{
double d = Math.random()*(i);
System.out.println ( "squareRoot(" + df.format(d) + ") = " +
df.format(squareRoot(d)));
}
}
}
Basically, if x becomes too lower than sqrt(N), then N/x helps to pull it towards sqrt(N).
Similarly, N/x pulls x down if it becomes too large than sqrt(N).
Together, both x and N/x converge to get as close to sqrt(N) as possible.
Since both strive to converge towards sqrt(N), their sum is expected to converge towards 2*sqrt(N).
That's why we divide by 2 in (x + N/x)/2
This method is an example of the Bisection Method used to find solution
for any continuous function f(x).
