Efficiently implementing the power function

Intro

If you're serious about improving your programming skills, consider subscribing to my newsletter, it's free and keeps you updated with my latest python and programming tips.

The goal of this article is to showcase the difference between an efficient code and an inefficient one, I'll use the power function as an example but this can be applied to more things. I'll also introduce the notion of divide and conquer, but I'll explain it deeper in another article.

Writing the power function

Let's start by writing the power function as we would all have done the first time:

def power(n, p):
    """
    returns n to the power of p
    only works for whole positive values of p
    """
    result = 1
    for i in range(p):
        result *= n
    return result

Alright, nothing too weird for now, just a standard function, let's test it out a bit:

print(power(2, 0))
print(power(5, 10))
print(power(30, 100))

Output:

1
9765625
5153775207320113310364611297656212727021075220010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

And now, let's try:

print(power(2,1_000_000_000)

Output: It's still loading
Okay, maybe a billion is a big number, but at the end of this article, we'll be able to calculate 2 to the power of a billion.

Time complexity and problems

The problem with this function is its O(N) time complexity (read this if you want to know more about the big O notation). We can write some code to observe this (although the result yields a curve looking more like a squared complexity):

n_points = [10, 30, 100, 300, 1_000, 3_000, 10_000, 30_000, 100_000, 300_000, 500_000, 1_000_000, 30_000_000]
time_measured = list()
for n in n_points:
    t_start = time.perf_counter()
    power(2, n)
    t_end = time.perf_counter()
    time_measured.append(t_end-t_start)
plt.plot(n_points, time_measured, label="normal power function")

plt.title("time efficiency of the power function")
plt.xlabel("power")
plt.ylabel("time taken in seconds")
plt.legend()
plt.show()

Result:

Now, if we observe the results, to get 2 to the power of 10⁵ takes about 0.1 seconds, and to get 2 to the power of 10⁶ takes about 14 seconds, this is pretty problematic, so we'll have to come up with a more efficient way of implementing this function if we want to get to higher powers.

New algorithm

The new algorithm is based on the divide and conquer strategy, which consists in dividing problems into smaller, faster problems.
For instance, calculating 2¹⁰ is the same as calculating 2⁵×2⁵, and calculating 2⁵ is the same as calculating 2×2²×2²

We'll use a recursive function to achieve this:

def power_eff(n, p):
    """
    returns n to the power of p
    only works for whole positive values of p
    is recursive
    """
    if p==0: 
        return 1
    if p%2: #if the power is odd
        return n * power_eff(n, p//2) * power_eff(n, p//2)
    #this only runs if the power is even and not equal to 0  
    return power_eff(n, p//2) * power_eff(n, p//2)

Comparing results

Such a function, (classic divide and conquer) has an O(log(N)) time complexity which is more efficient than the previous version of this function, but let's see it by comparing it:

n_points = [10, 30, 100, 300, 1_000, 3_000, 10_000, 30_000, 100_000, 300_000, 500_000, 1_000_000, 3_000_000]
time_measured = list()
for n in n_points:
    t_start = time.perf_counter()
    print(n)
    power_eff(2, n)
    t_end = time.perf_counter()
    time_measured.append(t_end-t_start)
plt.plot(n_points, time_measured, label="efficient power function")

time_measured = list()
for n in n_points:
    t_start = time.perf_counter()
    print(n)
    power(2, n)
    t_end = time.perf_counter()
    time_measured.append(t_end-t_start)
plt.plot(n_points, time_measured, label="normal power function")

plt.title("time efficiency of the power function")
plt.xlabel("power")
plt.ylabel("time taken in seconds")
plt.legend()
plt.show())

Result:

Now, let's add a couple of points and only run the efficient power function:

n_points = [10, 30, 100, 300, 1_000, 3_000, 10_000, 30_000, 100_000, 300_000, 500_000, 1_000_000, 30_000_000, 100_000_000, 300_000_000, 1_000_000_000]
time_measured = list()
for n in n_points:
    t_start = time.perf_counter()
    power_eff(2, n)
    t_end = time.perf_counter()
    time_measured.append(t_end-t_start)
plt.plot(n_points, time_measured, label="efficient power function")

plt.title("time efficiency of the power function")
plt.xlabel("power")
plt.ylabel("time taken in seconds")
plt.legend()
plt.show()

Result:

Just by using a different method, we were able to drastically reduce the time efficiency of our function!