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 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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 ) ) |