## Exponentiation by Squaring

Posted by sanstechbytes on October 7, 2011

To compute the value of a raised to the power of b (a to power b) , Math.pow(a, b) or some appropriate library function (depending on which language we’re talking about) is often used, which, of course, is optimized. Another efficient approach is Exponentiation by Squaring using recursion. For the underlying idea behind it, read here.

Although optimization achieved with this approach doesn’t appear to be significant for smaller integer exponents, it’s worth considering this for bigger integer exponents in your exponentiation code.

See the code (in Java) below:

The time complexity is ~ O(c log n): Takes O(log n) for squaring’s and O(log n) for multiplications.

class ExponentiationTest {

public static void main(String[] args) {

// TODO Auto-generated method stub

double a = 2, b = -10; //

double pow = powerWithRecurSquaring(a, b);

if (b < 0) {

pow = 1 / pow;

}

System.out.println(a + ” to the power of ” + b + ” = ” + pow);

}

// a power b, runs in ~ O(2 log b) time

public static double powerWithRecurSquaring(double a, double b) {

if (b < 0) {

b = -b; // b = Math.abs(b);

} else if (b == 0) {

return 1;

} else if (b == 1) {

return a;

} else if (b == 2) {

return a * a;

} else if (b % 2 == 0) {

return powerWithRecurSquaring(powerWithRecurSquaring(a, b / 2), 2);

}

return powerWithRecurSquaring(a, b – 1) * a;

}

}

## chinmaylokesh said

Nice Post. I recommend using the sourcecode tags and you can display the code with indentations.

## sanstechbytes said

@Chinmay: Thanks for the feedback :).