Compute x to the power of y

Problem

In this post, we wish to calculate \(x^y\). 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 inputs x and y returns \(x^y\).

By definition, \(x^y\) 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: $$(a^m)^n = a^{mn}$$
• Product of like bases: $$a^ma^n = a^{m+n}$$

Let’s consider the following problem: \(1.1^{20}\). 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.

So what is the pattern here? Recursion! The pattern here looks like the following: \(pow(a, n) = \begin{cases} 1, & \text{$n = 0$} \\ pow(a, n/2)^2, & \text{if $n$ is even}\\ pow(a, n/2)^2 * a, & \text{if $n$ is odd} \end{cases}\)

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:
\(x^{10} = x^{(1010)_2} = x^{(101)_2 + (101)_2} = x^{(101)_2} * x^{(101)_2} = x^5 * x^5\)

\(x^{5} = x^{(101)_2} = x^{(100)_2 + (1)_2} = x^{(100)_2} * x^{(1)_2} = x^{(10)_2} * x^{(10)_2} * x^{(1)_2} = x^2 * x^2 * x\)

So to generalize, if the LSB of y is 0 (== even), the result is \((x^{y/2})^2\); otherwise, \(x * (x^{y/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