The Most Efficient Way to Implement an Integer Based Power Function

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:

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:

In case the exponential part $\boldsymbol{X}$ is an even number, then $\boldsymbol{N^X}$ is equal to $\boldsymbol{(N^2)^{\frac{X}{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:

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.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex