CMPS 144L Lab Activity
Exponentiation, Recursively

An efficient approach to computing a (real number) base x raised to a (nonnegative integer) power n follows from this recursive characterization of xn:

xn = { 1   if n = 0
(x2)n/2   if n>0 and n is even
xn-1 · x   otherwise

Using this as a model, supply the body of the xToTheNRec() method in the ExponentiationTester Java application that is provided. (Alternatively, or in addition, supply the body of xToTheNRecNarrated(), which computes the same function but which, in doing so, narrates its own execution by printing messages reporting its incoming parameter values and outgoing result.)

Note: Obviously, the instructions in the previous paragraph preclude the use of the Math.pow() in your solution. End of note.

Use the application to test your method for correctness. (Make sure to have the main() method call the version of the method that you worked on, rather than the other one.) Entering a negative exponent at the prompt will cause the program to terminate.

For each x and n that the user enters, the program will display the value computed by your method as well as that computed by the Math.pow() method. If the two values are not very close, it is a strong indication that your method is in error.

The program also displays the number of multiplication operations performed by your method. (Well, you are responsible for updating the relevant variable appropriately within your method to keep an accurate count.) If your method is a faithful implementation of the recursive equation given above, the number of multiplications should be at most 2×lg(n) (i.e., twice the logarithm, to the base 2, of the exponent). (For example, with an exponent of 1000, the number of multiplications should be at most 20.1) Compare that to n−1, which is the number of multiplications that you would perform by following the "naive" approach.

Here is an example run of the program that makes use of the xToTheNRecNarrated() method: 

$ java ExponentiationTester
Enter a base (real number): 2.0
Enter an exponent (integer): 10
Received x:2.0; n:10
   Received x:4.0; n:5
      Received x:16.0; n:2
         Received x:256.0; n:1
            Received x:65536.0; n:0
            Returning 1.0 having received x:65536.0; n:0
         Returning 256.0 having received x:256.0; n:1
      Returning 256.0 having received x:16.0; n:2
   Returning 1024.0 having received x:4.0; n:5
Returning 1024.0 having received x:2.0; n:10

Your method produced 1024.0
Math.pow() produced  1024.0
Your method performed 6 multiplications.

Enter a base (real number): 0
Enter an exponent (integer): -1

Footnote

[1] However, if you test a large exponent such as 1000, use a base with a very small absolute value (2 or less, say) or else the result will be Infinity, due to the fact that the mathematically correct result will be of a magnitude larger than any that can be represented using the double data type.