2.6 Integer Exponentiation

---

 

	Java Number Cruncher: The Java Programmer's Guide to Numerical Computing By Ronald  Mak
	Table of Contents
	Chapter  2.   How Wholesome Are the Integers?

---

2.6 Integer Exponentiation

Unlike such languages as FORTRAN, Java does not have an exponentiation operator. We conclude this chapter with a static method that returns the double value of x ⁿ , where x is any double value, and n is an int value. If the value of n is 0, the method returns 1. It does not check for overflow.

Table 2-3. The sign of the remainder operation's result.

Operand 1	Operand 2	% Result
+	+	+
-	+	-
+	-	+
-	-	-

Suppose the value of n is 13. A straightforward computation would be to multiply the value of x 12 times:

But that involves 12 multiplications. This is not an efficient algorithm whenever the value of n is large.

We can partition 13 into the sum of powers of 2. Because 13 = 8 + 4 + 1,

If we look at 1101, the binary encoding of 13, we can devise a more efficient algorithm. For each bit in the binary encoding of n, we repeatedly square the value of x, and so we compute x ¹ , ( x ¹ ) ² = x ² , ( x ² ) ² = x ⁴ , and ( x ⁴ ) ² = x ⁸ . We then multiply together the power of x corresponding to each 1 bit to give us x ⁸ x ⁴ x ¹ . This involves a total of five multiplications. The savings in multiplications is greater with larger values of n.

Listing 2-3a shows class IntPower with a static method raise() that computes and returns the value of x ⁿ . It is the first of several useful classes that we'll define in the numbercruncher.mathutils package.

Listing 2-3a Class IntPower for doing integer exponentiation.

 package numbercruncher.mathutils; /**  * Raise a double value to an integer power.  */ public final class IntPower {     /**      * Compute and return x^power.      * @param x      * @param power the integer power      * @return x^power      */     public static double raise(double x, int exponent)     {         if (exponent < 0) return 1/raise(x, -exponent);         double power = 1;         // Loop to compute x^exponent.         while (exponent > 0) {             // Is the rightmost exponent bit a 1?             if ((exponent & 1) == 1) power *= x;             // Square x and shift the exponent 1 bit to the right.             x *= x;             exponent >>= 1;         }         return power;     } } 

Program 2 C3 is a short program that tests class IntPower by comparing its raise() method to java.lang.Math.pow(). See Listing 2-3b.

Listing 2-3b A test program for class IntPower.

 package numbercruncher.program2_3; import numbercruncher.mathutils.IntPower; /**  * PROGRAM 2-3: Test Class IntPower  *  * Test the IntPower class.  */ public class TestIntPower {     public static .void main(String args[])     {         System.out.println(IntPower.raise(2, 5)   + " " +                            Math.pow(2, 5));         System.out.println(IntPower.raise(2, -5)  + " " +                            Math.pow(2, -5));         System.out.println(IntPower.raise(2, 0)   + " " +                            Math.pow(2, 0));         System.out.println(IntPower.raise(2.5, 5) + " " +                            Math.pow(2.5, 5));         System.out.println();         System.out.println(IntPower.raise(-2, 5)   + " " +                            Math.pow(-2, 5));         System.out.println(IntPower.raise(-2, -5)  + " " +                            Math.pow(-2, -5));         System.out.println(IntPower.raise(-2, 0)   + " " +                            Math.pow(-2, 0));         System.out.println(IntPower.raise(-2.5, 5) + " " +                            Math.pow(-2.5, 5));     } } 

Output:

 32.0 32.0 0.03125 0.03125 1.0 1.0 97.65625 97.65625 -32.0 -32.0 -0.03125 -0.03125 1.0 1.0 -97.65625 -97.65625 

---

Top