### Vinay Singh

#### Latest posts by Vinay Singh (see all)

- Sorting non boundary elements - February 19, 2016
- Circular Prime – Solution of ISC Computer Practical 2016 - February 18, 2016
- Array Pattern - February 15, 2016

In this post we would see some ways to compute a^{b}, where a and b are positive integers. That is, we would implement our own power function, available in most programming language as pow().

The simplest solution of power problem is a^{b}=a × a × … b times. The Java program to raise a to the power b is as follows:

class Power{ public static int pow( int a, int b ){ int ans=1; for( int i=1 ; i<= b ; i++ ){ ans *= a ; } return ans; } public static void main( String args[] ){ System.out.println( pow( 2, 0 ) ); System.out.println( pow( 2, 1 ) ); System.out.println( pow( 2, 2 ) ); System.out.println( pow( 2, 3 ) ); System.out.println( pow( 2, 4 ) ); System.out.println( pow( 2, 5 ) ); } }

The above program to raise a to the power of b would give correct answer, but the fact is that it’s the worst method to do the same. The above can also be implemented using recursion as follows:

class Power{ public static int pow(int a, int b){ if(b==0) return 1; else if(b==1) return a; else return a * pow( a, b-1 ); } public static void main( String args[] ){ System.out.println( pow( 2, 0 ) ); System.out.println( pow( 2, 1 ) ); System.out.println( pow( 2, 2 ) ); System.out.println( pow( 2, 3 ) ); System.out.println( pow( 2, 4 ) ); System.out.println( pow( 2, 5 ) ); } }

Notice that a^{b} is equal to (a^{b/2} × a^{b/2} ) for even powers and (a^{(b-1)/2} × a^{(b-1)/2} × a) for odd powers. For example, 2^{6} is equal to 2^{3} × 2^{3} and 2^{5} is equal to 2^{2} × 2^{2} × 2. The Java program to raise positive integer a to the power of positive integer be would be as follows:

class Power{ public static int pow(int a, int b){ int ans=1, half=b/2; for(int i=1; i<= half ; i++){ ans *= a*a ; } if(b%2==1) ans *= a; return ans; } public static void main( String args[] ){ System.out.println( pow( 2, 0 ) ); System.out.println( pow( 2, 1 ) ); System.out.println( pow( 2, 2 ) ); System.out.println( pow( 2, 3 ) ); System.out.println( pow( 2, 4 ) ); System.out.println( pow( 2, 5 ) ); } }

The above program is substantially more efficient than the earlier version ( Complexity O(N) vs complexity O(ln N) ). The above logic can also be implemented using recursion as follows:

class Power{ public static int pow(int a, int b){ if(b==0) return 1; if(b%2==0) return pow( a, b/2 ) * pow( a, b/2 ); else return a * pow( a, b/2 ) * pow( a, b/2 ); } public static void main( String args[] ){ System.out.println( pow( 2, 0 ) ); System.out.println( pow( 2, 1 ) ); System.out.println( pow( 2, 2 ) ); System.out.println( pow( 2, 3 ) ); System.out.println( pow( 2, 4 ) ); System.out.println( pow( 2, 5 ) ); } }

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement. Please understand that recursive counter part of iterative methods are given for informational purposes only. The use of recursive functions is avoided in reality due to performance and memory issues which may arise if input is higher on the side.