By Long Luo

This article is the solution Fast Power Algorithm: Binary Exponentiation of Problem 50. Pow(x, n).

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 = \underbrace{a \times a \dots \times a}_b\).

A simple java implementation of that would be:

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

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 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \]

Try to divide the power by \(2\):

\[ 3^{10} = (3 \times 3) \times (3 \times 3) \times (3 \times 3) \times (3 \times 3) \times (3 \times 3) \]

\[ 3^{10} = ((3 \times 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 \times 9 \times 9 \times 9 \times 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) \times 9 \]

// Now we can find \(9^4\) and later multiple the extra \(9\) to the result

\[ 9^5 = (81^2) \times 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) \times 9\)

\[ (81^2) \times 9 = (81 \times 81) \times 9 \]

// Try to divide the power by \(2\) \[ (81 ^ 2) \times 9 = (6561 ^ 1) \times 9 \]

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

Let’s use recusive in java.

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

  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.

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

   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(logn)\)
• Space Complexity: \(O(logn)\)

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. 😉😃💗