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