This lab requires the use of the various loop constructs that have been discussed in lecture.

Read the submission requirements below -- they are different from previous labs!

Input

The input to your program is the number for which the user wants to find the square root, a guess for the square root, and the desired accuracy of the final result. You should validate the number by making sure it is legal to take the square root of it. You should also validate that the desired accuracy is greater than zero.

Processing

An early method of approximating square roots was the Newton-Raphson method. This method consisted of starting with an approximation to the square root of a number and then getting successively better approximations until the desired degree of accuracy was achieved.

Each new guess is defined to be:

newGuess = (oldGuess + number / oldGuess) * .5

So, if the number entered were 34 and the first approximation were 5, the second and third approximations would be:

(5 + 34 / 5) * .5   =   5.9
(5.9 + 34/5.9)*.5   =   5.83135593...

We can get as close to the actual square root as we want by defining a tolerance value that represents how much error we are willing to tolerate in our answer. Letting this value be named desiredAccuracy, we would keep computing new approximations until  | newGuess - oldGuess | < desiredAccuracy. You can compute absolute values with the Java library function Math.abs().

Output

Output each successive approximation, including the initial guess, the final approximation, the actual square root as computed by Math.sqrt(), and the absolute value of the difference between the final approximation and the sqrt()-computed value. Each output value should have an appropriate label preceding it in the output, e.g.:

Approximation #2: 5.9

Sample Run

Square Root Approximation

Enter the number to take the square root of: 34.0
Enter the first approximation: 5.0
Enter the desired accuracy: .000001

Approximation #1: 5.0
Approximation #2: 5.9
Approximation #3: 5.83135593220339
Approximation #4: 5.830951908842575
Approximation #5: 5.830951894845301

Final approximation = 5.830951894845301
Actual root according to Math.sqrt() = 5.830951894845301
Error in approximation = 0.0

Note: this problem will use the caret (^) to indicate exponentiation. For example, 4^2 = 16.

Input

The input is a single number, n, which must be >= 2. You should validate this input. After each computation, you will also need to prompt the user about quitting. You may ask for yes or no, Y or N, or some other values -- it's up to you -- but you must validate the input.

Processing

To help you, here is pseudocode for an algorithm that performs prime factorization. Recall that the left arrow (<-) is pseudocode for assignment.

Prime-Factor(n)
    test-factor <- 2
    do until n = 1
        if n is divisible by test-factor
            p <- highest power of test-factor that evenly divides n
            output factor and power
            n <- n / test-factor^p
        test-factor <- test-factor + 1

You should implement this algorithm as a method. The algorithm also suggests that you'll need two other methods:

• boolean isDivisibleBy(int num, int factor): yield whether num is evenly divisible by factor
• int highestPower(int num, int factor): yield the highest power p of factor such that factor^p evenly divides num

Output

Print the prime factorization as a product of exponentiations. 

Sample Run

Prime Factorization
-------------------

Enter the number to factor: 0
Number must be greater than 1.

Enter the number to factor: 2
The prime factorization of 2 is the product of:
    2^1

Another number (yes or no)? maybe
You must answer yes or no.
Another number (yes or no)? yes

Enter the number to factor: 123456789
The prime factorization of 123456789 is the product of:
    3^2
    3607^1
    3803^1

Another number (yes or no)? yes

Enter the number to factor: 24
The prime factorization of 24 is the product of:
    2^3
    3^1

Another number (yes or no)? no
Bye.

Extra Credit

For a small amount of extra credit, you may:

• Print "<num> is prime" instead of printing its factorization
• Print the factorization on one line, eliminating unnecessary exponents, e.g.: "24 = 2^3 * 3"

Your folder should contain exactly the following files:

• Lab6
  • SquareRoot.java
  • PrimeFactorization.java

It is our hope that having to submit fewer files will mean fewer errors and thus improve your grades on labs.

You will submit your lab using FTP.