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

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

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) --

推荐阅读：
一乘二分之一加二乘三分之一加…九十九乘一百分之一加一百乘一百零一分之一等于多少？求答题过程和答案。　 为什么所有剩下的钱加起来是51元？　 十二个乒乓球特征相同，其中只有一个重量异常　 某银行有两种储蓄计划——单利和复利的问题　 大院里养了三种动物。每只小山羊戴3个铃铛，每只狗戴1个铃铛　 某本书正文所标注的页码共用了2989个阿拉伯数字，问这本书的正文一共有多少页？　 有两棵古槐树，500年前有个学者说　 高中生儿童节作文　 勿以恶小而为之勿以善小而不为　 美丽的长岛作文　
评论列表
添加评论