 # Binary Exponentiation Farhan Yahya Updated on ・2 min read

Binary exponentiation is a simple technique used to find the value for an 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, an 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: 313 = 3 * 3 ... 3
This way: 313 = 31101 = 38 * 34 * 31
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:
31 = 3
32 = (31)2
34 = (32)2
38 = (34)2 ...

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)

### Discussion   