Power(base, exponent)
by Isai Damier, Android Engineer @ Google

#======================================================================
# Author: Isai Damier
# Title: Power(base, exponent)
# Project: geekviewpoint
# Package: algorithms
#
# Statement: Compute base x raised to exponent n: x^n
#
# Sample Input: 3^11
# Sample Output: 177147
#
# Time Complexity of Solution:
#   Best = Average = Worst = O(Time) = O(log n),
#
# Technical Details:
#   Instead of multiplying x by itself n times using a for-loop,
#   we continually divide the exponent by two (think binary search)
#   hence reducing the time complexity to O(log n) instead of O(n).
#   We demonstrate by manually solving for 3^11.
#
#   3^11 = 3^5 * 3^5 * 3
#   3^5 = 3^2 * 3^2 * 3
#   3^2 = 3 * 3 = 9
#
#  Therefore, we perform five multiplications instead of eleven:
#  3*3=9; 993 = 243; 243*243*3 = 177147
#====================================================================== 
 def pow( base, exponent ):
    if 1 == exponent:
        return base

    result = pow( base, exponent / 2 )
    if 0 == ( exponent & 1 ):
        return result * result
    return result * result * base

import unittest
from algorithms import numbers as algorithm

class Test( unittest.TestCase ):

  def testPow( self ):
    x = 2;
    n = 11;
    self.assertEquals( int ( x ** n ), algorithm.pow( x, n ) )
    x = 3
    n = 7
    self.assertEquals( int ( x ** n ), algorithm.pow( x, n ) )
    x = 5
    n = 4
    self.assertEquals( int ( x ** n ), algorithm.pow( x, n ) )
    x = 4
    n = 6
    self.assertEquals( int ( x ** n ), algorithm.pow( x, n ) )