Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

1. Overview

In this tutorial, we’ll talk about the most efficient way to implement an integer-based power function.

Firstly, we’ll define the problem. Then we’ll give an example to explain it.

Secondly, we’ll present two different approaches to solving this problem.

2. Defining the Problem

Given two positive integers N and X, we need to compute N^X.

Let’s take a look at the following examples:

  • N = 1, X = 20 \Rightarrow 1^{20} = 1.
  • N = 124, X = 0 \Rightarrow 124^{0} = 1.
  • N = 2, X = 5 \Rightarrow 2^{5} = 32.

Recall that N^X equals N multiplied by itself X times.

3. Loop Approach

3.1. Main Idea

The main idea in this approach is to transform the power operation into a series of multiplication operations. For example, N^4 for an example is equal to N \times N \times N \times N (N multiplied by itself 4 times).

We’ll use for loop to multiply N by itself X times to solve our problem.

3.2. Algorithm

Let’s take a look at the implementation:

Rendered by QuickLaTeX.com

First, we declare result as a variable to store the answer, and its initial value equals 1. The reason we start by 1 is that any number to the power of zero equals one. Second, we start a for loop that has X iterations, in each iteration, we multiply N by the current result.

In the end, the result will be equal to N^X.

3.3. Complexity

The complexity of this algorithm is \boldsymbol{O(X)}, where X is the exponential part in our problem. The reason behind this complexity is that we’re using a for loop to do X operations.

4. Fast Power Approach

4.1. Main Idea

In this approach, we’ll use one of the power properties. Recall that (N^a)^b is equal to N^{a \times b}. So, each time we can square the current base N and divide the power by two. We have two cases to handle:

  1. In case the exponential part \boldsymbol{X} is an even number, then \boldsymbol{N^X} is equal to \boldsymbol{(N^2)^{\frac{X}{2}}}.
  2. On the other hand, if \boldsymbol{X} is an odd number, then \boldsymbol{N^X} is equal to \boldsymbol{N \times (N^2)^{\frac{X - 1}{2}}}.

At the end, when the power becomes equal to zero, the result will be equal to the answer to the problem.

4.2. Algorithm

Let’s take a look at the implementation:

Rendered by QuickLaTeX.com

Initially, we declare result as a variable to store the answer. We set its initial value to 1 since any number to the power of zero is equal to one. Next, as long as the power X is greater than zero, we check whether the power is odd. If so, we multiply the result by the base N and decrease the power X by one.

After this step, the X value will be even. So, we divide the power by two and square the base N. We keep repeating this process until the power X becomes equal to zero.

Finally, we return result, which is equal to N^X.

4.3. Complexity

The complexity of this algorithm is \boldsymbol{O(Log_2(X))}, where X is the exponential part.

The reason behind this complexity is that in each iteration, we divide the power X by two. So, in total, we have Log_2(X) iterations inside the while loop.

5. Conclusion

In this article, we presented the most efficient way to implement an integer-based power function.

First, we provided an example to explain the problem. Then we gave two different approaches to solving it and walked through their implementations.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!