Square root approximations, implemented two ways

Question

Which version is more efficient in calculating the square root ?

There are 2 versions I have written to calculate square root programatically. Note reqs strictly state not using library functions ?

This is puzzling, the first method takes one extra iteration over the 2nd one but returns the more accurate answer of 3.00.

Why does it take an extra iteration ?

• So, which one is more efficient ?
• Do you find any bugs in this code ?
• When will it overflow ?
• Do both approaches seem logical, one is trying to calculate the difference between square of approximation and actual number, whereas other trying to bisect the interval. Would you pick one over the other ?

public void squareRoot()
{
 double n = 9;
 double epsilon = 0.001;
 double guess = n*n;
 double low = 0;
 double high = n;
 int cnt=0;
 while(Math.abs(guess*guess-n)>epsilon)
 {
 guess = (low + high)/2;
 if(guess*guess>n)
 high = guess;
 else 
 low = guess;
 cnt+=1;
 System.out.println("Low:"+low+"high:"+high+"guess:"+guess+"cnt:"+cnt);
 }
 if(guess*guess-n<epsilon)
 {
 System.out.println("The square root is:"+guess);
 }
}
public void anotherSquareRoot()
{
 double n = 9;
 double epsilon = 0.001;
 double guess = n*n;
 double low = 0;
 double high = n;
 int cnt=0;
 while(high-low>epsilon)
 {
 guess = (low + high)/2;
 if(guess*guess>n)
 high = guess;
 else 
 low = guess;
 cnt+=1;
 System.out.println("Low:"+low+"high:"+high+"guess:"+guess+"cnt:"+cnt);
 }
 if(guess*guess-n<epsilon)
 {
 System.out.println("The square root is:"+guess);
 }
} 

Answer 1

In version 1, you are testing the difference of the square is within 0.001.

The square root of 9.001 is 3.000167

In version 2, you are testing the difference of the square root part. When you square it, the error becomes bigger.

The square of 3.001 is 9.006001

One error:

You need to get rid of the

if(guess*guess-n<epsilon)

at the end of version 2, it will not print for positive differences> 0.001 e.g. for 3.001 9.006001 is 0.00601 bigger.

• Phoenix: Which one is more correct ?
• parkydr: It depends on your requirements. The only one you have stated is no library functions and version 1 uses Math.abs (although it would be easy to implement yourself) so version 2 is more correct. If you want better accuracy, version 1 is better.
• Phoenix: Y is square of the error a better solution ?
• parkydr: I'm not saying one is better, just different but if I had to choose, I would choose version 2 as it gives you the square root within the error you have specified and uses subtraction, which will be faster than squaring and taking the absolute.

Answer 2

There are some fairly bizarre things which are present in both.

• Neither of them takes a parameter
• Both of them start with double guess = n*n; and then proceed to square the guess again. This is never going to be useful.
• They use unguided binary chop for a nonlinear function

I would use a Taylor expansion to three or four terms to get a starting point and then Newton-Raphson should home in very fast.