Binary Exponentiation

Binary exponentiation is a simple technique used to find the value for aⁿ in O(logn) multiplications instead of the naive way which is O(n) multiplications. First, let's have a look at the naive way then this way.

The naive way

From mathematics, aⁿ is expressed as a multiplying itself n times. Hence a naive function for solving this will be like below.

int pow(int a, int n){
  int ans = 1;
  while(n--){
    ans *= a;
  } 
  return ans;
}

This is quite simple but we will want to reduce the complexity of this function and that is where binary exponentiation comes in.

This way(Binary Exponentiation)

In this method, the work is split into the binary representation of the exponent which reduces the computation to O(logn).

Example

Naive: 3¹³ = 3 * 3 ... 3
This way: 3¹³ = 3¹¹⁰¹ = 3⁸ * 3⁴ * 3¹
Implementing an algorithm for this is very simple. intead of looping n times we rather loop through the bits which is logn times. To get our solution, we then find the powers at which a bit is set just like the example above. Because we are using the binary presentation of n the power at a set bit will be the square of the previous set bit.
That is:
3¹ = 3
3² = (3¹)²
3⁴ = (3²)²
3⁸ = (3⁴)² ...

So with this, we just find the product of the powers set in n.

Code for this way

int pow(int a,int n){
  int res = 1;
  while(b){
    if(b&1){
      res *= a;
    }
    a *= a;
    b >>= 1;
  }
  return res;
}

The above code computes in O(logn) which is better than the naive way which computes in O(n)

Comments

[Anshul Bansal]

There seems to be a small mistake in the example:
This way: 3¹³ = 3¹¹⁰¹ = 3⁸ * 3⁴ * 3² should be 3⁸ * 3⁴ * 3¹

[Farhan Yahya]

Thanks for the correction