power

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⁶ is equal to 2³ × 2³ and 2⁵ is equal to 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.