DEV Community

loading...
Cover image for Binary Exponentiation
eduAlgo

Binary Exponentiation

rishsinghal profile image Rishabh Singhal ・3 min read

Let's say you are given two numbers a, n and you have to compute a^n.

Algorithm

Naive Approach: O(n)

The easiest approach to do this, if one knows how to use "for" loops or implement it (if it is not implemented already) in any given programming language is just a single O(n) iteration. Below is a sample implementation in C++.

int a, n;
// a, n can be initialized either by taking input or
// by assigning hardcoded values a = 3, n = 4 let's say

// expo initialized to 1 as it is the multiplicative identity
int expo = 1;

for (int i = 0; i < n; ++i) {
    expo = expo * a;
}

// now expo == a^n : true
Enter fullscreen mode Exit fullscreen mode

Note
Here, the data type is "int", assuming the value of expo = a^n comes under the constraint of "int". So, any other data type can be used as per requirements.

Caveats

  1. It can be seen that this approach would time out if n > 10^8.
  2. If the value of a^n is very large i.e. it can not be stored in "int" or any other provided data type, it will overflow.

Possible Solutions

  1. Algorithm of lesser complexity can be utilized in this case -- we will see O(log n) algorithm next.
  2. This is the reason why most of the time (a^n)%(some number) is to be calculated. Most of the time that "some number" is 1e9 + 7 (which is a prime) in competitive programming problems.

Binary Exponentiation Approach: O(log n)

For achieving O(log n) complexity, the mathematical fact that any number (in decimal) can be represented uniquely in binary can be utilized.

For example,
12 = 1*8 + 1*4 + 0*2 + 0*1 = (1100)_2
15 = 1*8 + 1*4 + 1*2 + 1*1 = (1111)_2

Now, also using the fact that a^(m + n) = (a^m)*(a^n), we can calculate the values of a^1, a^2, a^4, and so on ...

int expo = a;
for (int i = 0; i < n; ++i) {
    expo = (expo*expo);
}
// it's like
// expo: a -> a^2 -> a^4 -> a^8 -> a^16 ...
// i.e. with ith step the value will be a^(2*i)
Enter fullscreen mode Exit fullscreen mode

Now, let's say we need to calculate a^n, then there will exist a unique representation of "n" in binary, whose i_th bit can be checked if it is set or not by using a simple boolean expression involving bitwise operator

// (n >> i) & 1 == ith bit of n
Enter fullscreen mode Exit fullscreen mode

for the proof for this refer to Link

now, it can be seen that a^n = (a^(1*b_1))x(a^(2*b_2))x(a^(4*b_3))x... and we can find if the a^(2*i) have to multiply or not by using the fact we saw above. So, by a simple modification to the previous code we can calculate a^n.

//init a, n
int expo = a;

// answer initialized to 1 as it is multiplicative identity
int answer = 1;
for (int i = 0; i < NUMBER_OF_BITS_IN_N; ++i) {
    if((n >> i) & 1) {
        // we check if the ith bit is set or not
        // if it is set then, we multiply expo = a^(2*i)
        answer = answer*expo;
    }  
    expo = (expo*expo);
}

// answer now have the value a^n
Enter fullscreen mode Exit fullscreen mode

See, there is only one "O(NUMBER_OF_BITS_IN_N)" for loop, and it is easy to see that the number of bits in n = log_2(n).

Hence, the overall complexity = 0(log n)

If you are not sure of the number of bits in n, then just simply take MAXIMUM_POSSIBLE_NUMBER_OF_BITS instead which can be ~32 for the int datatype.

Modular Binary Exponentiation

Considering the second caveat described above, there can be cases where we need to find (a^n)%(some value) -- note that % is the remainder operator (as used in C++).

For this, just an easy modification of the code will work,

//init a, n, modvalue
long long expo = a;

// answer initialized to 1 as it is multiplicative identity
long long answer = 1;
for (int i = 0; i < NUMBER_OF_BITS_IN_N; ++i) {
    if((n >> i) & 1) {
        // we check if the ith bit is set or not
        // if it is set then, we multiply expo = a^(2*i)
        answer = (answer*expo) % modvalue;
    }  
    expo = (expo*expo) % modvalue;
}

// answer now have the value (a^n)% modevalue
Enter fullscreen mode Exit fullscreen mode

Conclusion

So, as we saw the binary exponentiation algorithm, it can be used for exponentiating a matrix too, just by changing "*" operator with implemented matrix multiplication and taking remainder with each number in the matrix.

Further Directions

For reading more about binary exponentiation and solving some related problems to get a grasp refer to CP-Algorithms Binary-Exp


Discussion (4)

pic
Editor guide
Collapse
abhijit2505 profile image
Collapse
rishsinghal profile image
Collapse
nishantsachdeva profile image
Nishant Sachdeva • Edited

Great Read. Well expounded

Collapse
rishsinghal profile image