Algorithms to Compute the Math Power(a, n) in logarithm Complexi

  • 时间：2020-10-11 15:17:18
  • 分类：网络文摘
  • 阅读：155 次

Implement pow(x, n), which calculates x raised to the power n (xn). Example 1:

Input: 2.00000, 10
Output: 1024.00000
Example 2:

Input: 2.10000, 3
Output: 9.26100
Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]

Bruteforce Algorithms to Compute the Math Power(a, n)

The most straightforward solution is to iteratively multiple the answer n times of a i.e. a^n. This requires O(N) time and O(1) space.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 1 or n == 0:
            return 1
        if n < 0:
            return 1.0/self.myPow(x, -n)
        res = 1
        for i in range(n):
            res *= x
        return res        
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 1 or n == 0:
            return 1
        if n < 0:
            return 1.0/self.myPow(x, -n)
        res = 1
        for i in range(n):
            res *= x
        return res

Please note that we have turned the negative power a^(-n) to 1.0/(a^n). Given n is a large number e.g. 2^(31), this algorithm will time out.

Algorithms to Compute the Math Power(a, n) in logarithm Complexity using Divide and Conquer

The optimal solution is to apply the divide and conquer technique. If we want to compute a^n, we can divide this into two cases. When n is odd, the answer is a^(n-1)*a, and when n is even, the answer is (a^(n//2))^2.

This algorithm gives us the O(logN) time. You can implement this algorithm using Recursion:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 1 or n == 0:
            return 1
        if n < 0:
            return 1.0/self.myPow(x, -n)
        if n % 2 == 0:
            a = self.myPow(x, n // 2)
            return a * a
        return self.myPow(x, n - 1) * x
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 1 or n == 0:
            return 1
        if n < 0:
            return 1.0/self.myPow(x, -n)
        if n % 2 == 0:
            a = self.myPow(x, n // 2)
            return a * a
        return self.myPow(x, n - 1) * x

Alternatively, the iterated approach works just fine (more code, but saving the cost of Recursive calls, removing the stack overflows):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 1 or n == 0:
            return 1
        if n < 0:
            return 1.0/self.myPow(x, -n)
        res = 1
        while n > 1:
            if n % 2 == 0:
                x *= x
                n //= 2
            else:
                res = res * x
                n -= 1
        return res * x
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 1 or n == 0:
            return 1
        if n < 0:
            return 1.0/self.myPow(x, -n)
        res = 1
        while n > 1:
            if n % 2 == 0:
                x *= x
                n //= 2
            else:
                res = res * x
                n -= 1
        return res * x

C++ Implementation of Computing the Power(a, n)

Iterative approach and handling the negative cases quite well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    double pow(double x, int n) {
        //  check the sign of n
        bool plus = n >= 0;
        n = plus ? n : -n;
        double r = 1;
        while (n > 0) {
            // if odd
            if (n & 1 == 1) {
                r *= x;
            }
            // reduce the exponential to its half
            n /= 2;
            // square the base
            x *= x;
        }
        // if n < 0, should return 1.0/x^n
        return plus ? r : 1.0 / r;
    }
};
class Solution {
public:
    double pow(double x, int n) {
        //  check the sign of n
        bool plus = n >= 0;
        n = plus ? n : -n;
        double r = 1;
        while (n > 0) {
            // if odd
            if (n & 1 == 1) {
                r *= x;
            }
            // reduce the exponential to its half
            n /= 2;
            // square the base
            x *= x;
        }
        // if n < 0, should return 1.0/x^n
        return plus ? r : 1.0 / r;
    }
};

Same iterative approach, however handle the negative cases via calling itself recursively. Also, please note that we negative n, which means that we have to handle the overflow manually or giving it a larger int64_t type. i.e. negate -2147483648 will cause integer overflow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    double myPow(double x, int64_t n) {
        if (n == 0) return 1;
        if (x == 1) return 1;
        if (n < 0) return 1.0 / myPow(x, -n);
        double res = 1;
        while (n > 1) {
            if (n % 2 == 0) {
                x = x * x;
                n /= 2;
            } else {
                res = res * x;
                n --;
            }
        }
        return res * x;
    }
};
class Solution {
public:
    double myPow(double x, int64_t n) {
        if (n == 0) return 1;
        if (x == 1) return 1;
        if (n < 0) return 1.0 / myPow(x, -n);
        double res = 1;
        while (n > 1) {
            if (n % 2 == 0) {
                x = x * x;
                n /= 2;
            } else {
                res = res * x;
                n --;
            }
        }
        return res * x;
    }
};

Last but not least, recursive implementation in C++ (shorter/concise code with Recursion):

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    double myPow(double x, int64_t n) {
        if (n == 0) return 1;
        if (x == 1) return 1;
        if (n < 0) return 1.0 / myPow(x, -n);
        if (n % 2 == 0) {
            double a = myPow(x, n / 2);
            return a * a;
        } 
        return x * myPow(x, n - 1);
    }
};
class Solution {
public:
    double myPow(double x, int64_t n) {
        if (n == 0) return 1;
        if (x == 1) return 1;
        if (n < 0) return 1.0 / myPow(x, -n);
        if (n % 2 == 0) {
            double a = myPow(x, n / 2);
            return a * a;
        } 
        return x * myPow(x, n - 1);
    }
};

Have you got a better solution/implementation to compute the Math Power(a, n)? Leave comments below to share!

--EOF (The Ultimate Computing & Technology Blog) --

推荐阅读：
这道初中数学题并不难，关键是因式分解变形　 田忌赛马　 上帝也责怪我妄自尊大　 勒布朗先生　 被称为墙头草的数学大师　 专心致志、持之以恒的高斯　 没有捷径可走　 计算机向π值的挑战　 爱因斯坦与数学速算　 悖论破解法　
评论列表
添加评论