3.4 Fast Exponentiation

Even though calculating the exponentiation can be done in linear time of the value of exponent, computation of large integer powers of a number still takes too much time, a better way for fast computation is to make use of binary exponentiation based on the square-and-multiply algorithm.

The key observation in binary exponentiation is that, assume the exponent n is even integer, then to compute xn it is equivalent to (xn/2)2, such recurrence relation can be used to form the recursive algorithm to compute xn for an integer n by using squaring-and-multiplication.

Time Complexity
The time complexity strictly depends on the number of multiplications, since for each recursive step the problem size is reduced by half, so by the master theorem the time complexity is O(log n)

Pseudo Code

pow( x, n )
   if n < 0 then
       return 1 / pow( x, -n );
   else if n == 0 then
       return 1;
   else if n == 1 then
       return x;
   else if n > 1 then
       if n is even then
           tmp = pow( x, n/2 );
           return tmp * tmp;
       else if n is odd then
           tmp = pow( x, (n-1)/2 );
           return tmp * tmp * x;
       end if
   end if
© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk