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 squareandmultiply algorithm.
The key observation in binary exponentiation is that, assume the exponent n is even integer, then to compute x^{n} it is equivalent to (x^{n/2})^{2}, such recurrence relation can be used to form the recursive algorithm to compute x^{n} for an integer n by using squaringandmultiplication.
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, (n1)/2 ); return tmp * tmp * x; end if end if

