public class Pow {
public static void main(String $[]){
System.out.println(pow(2,9));
}
public static double pow(double base, int power){
if (power == 0)
return 1;
//even
if((power&1)==0)
return pow(base*base,power/2);
//odd
return base*pow(base,power-1);
}
}
xn = (x2)n/2 if n is even
xn = x*xn-1 if n is odd
Point of using this approach is to compute the power in log(n) because it is dividing the power by two when its even.
CLICK HERE to find out more related problems solutions.