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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#======================================================================
# 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