Compute x to the power of y
03 Dec 2019 | 5 minutes to readProblem
In this post, we wish to calculate xy. This seems like a pretty simple problem to solve! Let’s formulate the problem first:
We want function
power(x, y)
that accepts two integer inputsx
andy
returns xy.
By definition, xy is described as the following:
if y is positive:
power(x,y) == x * x * ... * x
(where there are y number of x's)
ex. power(2, 3) == 2 * 2 * 2 == 8
if y is 0:
power(x,y) == 1
ex. power(1000, 0) == 1
if y is negative:
power(x,y) == 1/x * 1/x * ... * 1/x
(where there are y number of (1/x)'s)
ex. power(2, -3) == (1/2) * (1/2) * (1/2)
== (1/8)
== 1/(power(2, 3))
Solution
Let’s assume that there is no overflow and underflow.
Brute-force Approach
Let’s start with considering y >= 0
case only, the simplest approach is multiplying x
by itself y-1
times.
def power(x,y):
result = 1.0
for i in range(y):
result *= x
return result
The time complexity of such algorithm is O(y)
since we perform y-1
multiplications. Hence, the algorithm will get slower as we increase the value of y
.
Recursive Approach
The above solution will perform well for small value of y
. However, the run time will grow linearly with the size of y
. The key idea to improve this algorithm is to reduce the number of multiplication required.
Exponential Properties
Here are some exponential properties that we will use in this post.
- Power to power: (am)n=amn
- Product of like bases: aman=am+n
Let’s consider the following problem: 1.120. Using out brute-force algorithm, we would need to perform 19 multiplcations. However, using the exponential property, we can breakdown the problem like this, $(1.1^{10})^2$, then we only need to calcualte 9+1=10 calculations only! By expanding this further, we can reduce the multiplication down to 5.
(1.110)2=(((1.15))2)2=((1.1∗(1.12)2)2)2So what is the pattern here? Recursion! The pattern here looks like the following: pow(a,n)={1,n=0pow(a,n/2)2,if n is evenpow(a,n/2)2∗a,if n is odd
Not let’s code this:
def power(x,y):
if y == 0:
return 1
temp = power(x, int(y/2))
if y % 2 == 0:
return temp * temp
else:
return x * temp * temp
Notice that we are using temp
variable to not perform power(x, int(y/2))
twice. The run time of this is O(log(y))
as we are dividing y
into its half at every iteration.
To support negative y
, we can modify it like the following:
def power(x,y):
if y < 0:
x, y = 1.0 / x, -y
if y == 0:
return 1
temp = power(x, int(y/2))
if y % 2 == 0:
return temp * temp
else:
return x * temp * temp
Binary Expression Approach
This is the solution provided by Elements of Programming Interviews
book. I will write down the solution here first.
def power(x, y):
result, pow = 1.0, y
if y < 0:
pow, x = -pow, 1.0 / x
while pow:
if pow & 1:
result *= x;
x, pow = x * x, pow >> 1
return result
The idea behind is same as recursive approach; however it utilizes binary representation of y
and product of like bases exponential property. Let’s consider the following expresions:
x10=x(1010)2=x(101)2+(101)2=x(101)2∗x(101)2=x5∗x5
x5=x(101)2=x(100)2+(1)2=x(100)2∗x(1)2=x(10)2∗x(10)2∗x(1)2=x2∗x2∗x
So to generalize, if the LSB of y is 0
(== even), the result is (xy/2)2; otherwise, x∗(xy/2)2
Conclusion
By using mathematical property, we were able to reduce the time complexity through recusive approach!
References
- https://studentsuccess.asu.edu/sites/default/files/exponentialandlogrithmicproperties.pdf