Implement sqrt method using the approximation approach. Cannot exit loop even the condition is false

Question

I am so close to complete my practical question, just stuck at don't know why I cannot exit the loop after getting correct result.

The question ask to implement sqrt method using the approximation approach.

1. Let num is the number to apply sqrt method.
2. For the num> 1, lowerLimit = 1 and upperLimit = number
3. Then find the midpoint of lowerLimit and upperLimit which is (lowerLimit+upperLimit)/2
4. Square the midpoint, squareMidpoint = Math.pow(midpoint, 2)
5. If the squareMidpoint > num, upperLimit = midpoint, else lowerLimit= midpoint.
6. Repeat third step again until get num with 8 significant digits.

From step 1 to step 5, I think I did correctly since the output is correct.

I actually don't understand step 6 well.

My problem is if the num = 4, the program keep printing 2 forever.

Here is my code:

import java.lang.Math; 
public class p2q4 {

    public static void main(String[] args) {
        
        //Implement the sqrt method using the approximation approach
        
        //initialized lowerLimit and upperLimit
        double lowerLimit = 0, upperLimit = 0;
        
        //num is the number to square root.
        double num = 5;
        
        //For number greater than one,
        if (num > 1) {
            lowerLimit = 1; //lower limit to one
            upperLimit = num; //upper limit to the number
        }

        double squareMidpoint;
        double midpoint;

        do {
            //Determine the midpoint between the lower and upper limits
            midpoint = (lowerLimit + upperLimit) / 2;
            
            //Evaluate the square of the midpoint
            squareMidpoint = Math.pow(midpoint, 2);

            //If the square of the midpoint is greater than the number
            if (squareMidpoint > num) {
                //upper limit to the midpoint
                upperLimit = midpoint;
            } else {
                //lower limit to the midpoint
                lowerLimit = midpoint;
            }
            
            //for debugging purpose
            System.out.printf("midpoint=%f  squareMidpoint=%f upperLimit=%f lowerLimit=%f upperLimit/lowerLimit=%f\n", midpoint, squareMidpoint, upperLimit, lowerLimit, upperLimit/lowerLimit);

          
        //even though upperLimit/lowerLimit is '1' but still keep looping
        } while (upperLimit/lowerLimit != 1); //I not sure this condition is correct.
        
        //Output
        System.out.printf("x = %.0f, root = %f\n", num, midpoint);
    }
}

Here is my practical question:

Instead of using the sqrt method in the Math class, you have been asked to implement the sqrt method using the approximation approach described below:

For numbers greater than one, the square root method must initially set a lower limit to one and an upper limit to the number (since the square root of the number always lies between one and the number).

It must then determine the midpoint between the lower and upper limits and evaluate the square of the midpoint. If the square of the midpoint is greater than the number, the square root method must move the upper limit to the midpoint and similarly if the square of the midpoint is less than the number, it must move the lower limit to the midpoint.

After moving the appropriate limit, the square root method must evaluate a new midpoint and repeat the process until the desired precision is obtained.

The required precision for double precision floating point numbers is 8 significant digits. The precision at any iteration can be determined by dividing the difference between the limits by the lower limit.

When this is less than 1/108 any number between the limits will be an estimate of the square root of the number to the required precision. To minimize the error, the square root method should return the midpoint between the final limits that satisfy the precision requirement.

The square root method must return exact values for the special cases of zero and one.

If an application attempts to calculate the square root of a negative number, the square root method should display an appropriate message and terminate the program.

Any help is appreciated!

Answer 1

If you print upperLimit/lowerLimit with more significant digits, you'll see that it gets as small as 1.0000000000000002, but never reaches 1, which is why your loop never ends.

Instead of staying in the loop as long as:

upperLimit/lowerLimit != 1

you should change the condition to:

while (upperLimit - lowerLimit > 0.0000000001)

which will exit the loop when the limits get close enough to each other.

That's what step #6 means by "8 significant digits" - your approximation should get the first 8 significant digits correct.