实现基于整数的幂函数的最有效方法

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 and , we need to compute N^X .

Let’s take a look at the following examples:

, $\Rightarrow$ $1^{20} = 1$ .
, $\Rightarrow$ $124^{0} = 1$ .
, $\Rightarrow$ $2^{5} = 32$ .

Recall that N^X equals multiplied by itself 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$ ( multiplied by itself times).

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

3.2. Algorithm

Let’s take a look at the implementation:

algorithm LoopApproach(N, X):
    // INPUT
    //    N = the base number
    //    X = the exponent
    // OUTPUT
    //    N^X = N raised to the power of X

    result <- 1

    for i <- 1 to X:
        result <- result * N

    return result

First, we declare result as a variable to store the answer, and its initial value equals . 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 iterations, in each iteration, we multiply 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 is the exponential part in our problem. The reason behind this complexity is that we’re using a for loop to do operations.

4. Fast Power Approach

4.1. Main Idea

In this approach, we’ll use one of the power properties. R****ecall that is equal to $N^{a \times b}$ . So, each time we can square the current base 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:

algorithm FastPowerApproach(N, X):
    // INPUT
    //    N = the base number
    //    X = the exponent
    // OUTPUT
    //    N^X = the result of N raised to the power X

    result <- 1 
    while X > 0:
        if X mod 2 != 0:
            result <- result * N
            X <- X - 1

        X <- X / 2
        N <- N * N

    return result

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

After this step, the value will be even. So, we divide the power by two and square the base . We keep repeating this process until the power 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 is the exponential part.

The reason behind this complexity is that in each iteration, we divide the power 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.

Persistence

REST

Security