If we want to compute 
, we can have a naive implementation by multiplication of base number x.
1 2 3 4 5 | def pow(x, n): r = 1 for _ in xrange(n): r *= x return r |
def pow(x, n):
r = 1
for _ in xrange(n):
r *= x
return rThis is a O(n) approach, and based on the following, we can reduce the time complexity to 
.
It can thus be implemented by recursive function.
1 2 3 4 5 6 | def pow(x, n): if n == 1: return x if n % 2 == 0: return pow(x * x, n // 2) return x * pow(x * x, (n - 1) // 2) |
def pow(x, n):
if n == 1:
return x
if n % 2 == 0:
return pow(x * x, n // 2)
return x * pow(x * x, (n - 1) // 2)Or, a more efficient non-recursive approach can be developed/implemented as such.
1 2 3 4 5 6 7 8 9 | def pow(x, n): r = 1 while n > 0: if n % 2 == 1: r *= x n -= 1 x *= x n //= 2 return r |
def pow(x, n):
r = 1
while n > 0:
if n % 2 == 1:
r *= x
n -= 1
x *= x
n //= 2
return rWe can repeatedly reduce the N to either decrement one (if it is odd) or half (it is even). It takes roughtly O(LogN) to reduce N to 1.
References:
[1] http://en.wikipedia.org/wiki/Exponentiation_by_squaring
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
320 wordsloading...
Last Post: GCD, Greatest Common Divisor
Next Post: Codeforces: E. Mishap in Club
