[Leetcode][50. Pow(x, n)] The Illustration of Fast Power Algorithm - Exponentiation by Squaring or Binary Exponentiation

By Long Luo

This article is the solution of Problem 50. Pow(x, n).

50. Pow(x, n)

Medium

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
 
Constraints:
-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4

We know how to find 2.0 raised to the power 10. The easiest way is to multiply 10 times 2.0 by loop, but what if we have to find 2.0 raised to the power very large number such as 10000 or more?

We will discuss how to find the solution of such problems by using an fast, efficient algorithm.

Brute Force

We multiply $a$ to itself $b$ times. That is, $a^b = a \times a \times a \times ... \times a (b occurrences of a)$.

A simple java implementation of that would be:

public static double myPow(double x, int n) {
    if (n == 0 || x == 1) {
        return 1;
    } else if (x == 0) {
        return 0;
    }

    double ans = x;
    boolean isNegative = false;
    long nLong = n;
    if (nLong < 0) {
        nLong = -nLong;
        isNegative = true;
    }

    for (int i = 1; i < nLong; i++) {
        ans = ans * x;
    }

    if (isNegative) {
        ans = 1 / ans;
    }

    return ans;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Exponentiation by Squaring

Exponentiation by Squaring can help us in finding the powers of large positive integers. The key is to the divide the power in half at each step.

The following recursive approach expresses the same idea:

$a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{if } n > 0 \text{ and } n \text{ even}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{if } n > 0 \text{ and } n \text{ odd}\\ \end{cases}$

Let’s take an example:

3 ^ 10 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3
// Try to divide the power by 2
3 ^ 10 = (3 * 3) * (3 * 3) * (3 * 3) * (3 * 3) * (3 * 3)
3 ^ 10 = ((3 * 3) ^ 5)
3 ^ 10 = 9 ^ 5

Effectively, power is divided by $2$ and base is multiplied to itself. So we can write $3^10 = 9^5$.

Now, our problem is to find $9^5$.

9 ^ 5 = 9 * 9 * 9 * 9 * 9
// Try to divide the power by 2
// Since the power is an odd number here, we cannot do so.
// However there's another way to represent 9 ^ 5
9 ^ 5 = (9 ^ 4) * 9
// Now we can find 9 ^ 4 and later multiple the extra 9 to the result
9 ^ 5 = (81 ^ 2) * 9

Effectively, when power is not divisible by $2$, we make power even by taking out the extra $9$. Then we already know the solution when power is divisible by $2$. Divide the power by $2$ and multiply the base to itself.

Now our problem is to find $(81^2)*9$

(81 ^ 2) * 9 = (81 * 81) * 9
// Try to divide the power by 2
(81 ^ 2) * 9 = (6561 ^ 1) * 9

Finally, we have our solution $3^10 = (6561^1)*9 = 6561*9 = 59049$

Let’s use recusive in java.

  public static double myPow_quick(double x, int n) {
long N = n;
if (n > 0) {
          return quickMul(x, N);
      } else {
          return 1.0 / quickMul(x, -N);
      }
  }

  public static double quickMul(double x, long n) {
      if (n == 0) {
          return 1.0;
      }

      double y = quickMul(x, n / 2);
      if (n % 2 == 0) {
          return y * y;
      } else {
          return y * y * x;
      }
  }

Analysis

• Time Complexity: $O(\log n)$
• Space Complexity: $O(\log n)$

Iterative

Although the complexity of both approaches is identical, but if we use iteration instead of recursion will be faster in practice since we don’t have the overhead of the recursive calls and reduce the space.

   public static double myPow_3(double x, int n) {
       long N = n;
       return N >= 0 ? binaryPower(x, N) : 1.0 / binaryPower(x, -N);
   }

   public static double binaryPower(double a, long b) {
	double res = 1.0;
	while (b > 0) {
		if ((b & 1) == 1) {
			res = res * a;
		}
		a = a * a;
		b >>= 1;
	}
	
	return res;
}

Analysis

• Time Complexity: $O(\log n)$
• Space Complexity: $O(\log n)$

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗