Lab12a Square Root

Objectives

• Write a Java program that calculates square root of a number
• Use an iterative heuristic algorithm

Background

You know that you can use the Math.sqrt method in Java to compute the square root. But how does Math.sqrt work? Any computer can only add, subtract, multiply and divide so how does a calculator or a computer figure out sqrt, sin, cos and other things like integrals and derivatives?

It basically uses a guess and check method. It makes a guess, checks it and determines how far off the guess is, and then it has to make a better guess. It keeps repeating this until the answer is close enough. Close enough means 6-9 digits are correct.

Algorithm

Lets illustrate this with a example of writing a Java program to calculate square root of a number.

If the number is negative, there is no answer.

If the number is zero, then the answer is zero. If the number is 1, then answer is 1.

If the number is larger than 1, then the square root is some number between 1 and the number

And if the number is smaller than 1, then the square root is between the number and 1.

1. We have a lower bound and an upper bound. If the number is 5, the lower bound is 1 and the upper bound is 5.

2. Calculate the midpoint of this interval mid = (lower + upper) / 2.0

3. Compare to the number.

• if mid^2 > number then change the upper bound to mid
• if mid^2 < number then change the lower bound to mid
• if mide^2 == number then we are very lucky to have to found the answer.

4. Check if we have 6 significant digits of answer.

• if upper - lower < 1.0 x 10^-6 then we are done. Use either upper or lower as answer
• Otherwise, you need to go back to step 2 and repeat.

Convert the above pseudo code into a Java program that

• Prompts the user for a double number
• Check if the number is negative, 0 or 1
• Calculate an estimate for the square root
• Displays the answer, the number of iterations it took
• Compare the answer with the result Math.sqrt routine

The above algorithm is not the fastest (least number of iterations) to find the square root. You can take a course in scientific numerical computing that teaches you better techniques at a four year university. But this example demonstrates the basic idea as to how calculators and computers compute these mathematical functions.