Complete the xToN() method in the Java class Exponentiate. Provided with parameters x (of type double) and n (of type int but required to be nonnegative), its purpose is to compute xn (i.e., x raised to the power n).
The intent is for the method to compute its result based upon the following characterization of exponentiation:
| xn = { | 1 | if n = 0 | (1) |
| (x2)n/2 | if n>0 ∧ n is even | (2) | |
| xn−1 · x | if n>0 ∧ n is odd | (3) | |
Consider this example, which shows a calculation of 211 in accord with the above:
| 211 | ||
| = | 210 · 2 | by (3) |
| = | 45 · 2 | by (2) |
| = | 44 · 4 · 2 | by (3) |
| = | 162 · 4 · 2 | by (2) |
| = | 2561 · 4 · 2 | by (2) |
| = | 2560 · 256 · 4 · 2 | by (3) |
| = | 1 · 256 · 4 · 2 | by (1) |
| = | 2048 | by multiplication |
Notice that each row is of the form xn · f, where that expression is equal to 211. (Think of the value of the missing f in the first row as being 1.)
The loop in the xToN() method that you are to complete is intended to be consistent with this calculation. That is, where X and N are the values of the arguments passed to the method via its formal parameters x and n, the loop invariant is to be xn · f = XN, where the values of x, n, and (local variable) f change from iteration to iteration as illustrated. (Note that because computer arithmetic on real numbers is not exact, the method that tests the loop invariant checks to see whether xn∣f is "almost equal" to XN, where Java's Math.pow() method is used to carry out the exponentiations.)
To ensure that the code you supply conforms to the intended loop invariant, there are assert statements to verify that the invariant is true immediately before and after each loop iteration. (If, when an assert statement is executed, the condition specified in the statement evaluates to false, an exception is thrown.)
By default, assertions are disabled in Java, which means that they have no effect. To enable them, follow these instructions.
Provided within the class is a main() method intended to be used for testing purposes. Here is a sample run, with user input shown in boldface:
$ java Exponentiate Welcome to the Exponentiate program. Enter x: 2.0 Enter (nonnegative) exponent n: 11 x:2.000000, n:11, f:1.000000 x:2.000000, n:10, f:2.000000 x:4.000000, n:5, f:2.000000 x:4.000000, n:4, f:8.000000 x:16.000000, n:2, f:8.000000 x:256.000000, n:1, f:8.000000 x:256.000000, n:0, f:2048.000000 Your method says 2.000000 to the 11th power = 2048.000000 Math.pow() says 2.000000 to the 11th power = 2048.000000 Goodbye. |