Binary Exponentiation

#algorithms #cpp #programming

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

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

It can be seen that this approach would time out if n > 10^8.
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

Algorithm of lesser complexity can be utilized in this case -- we will see O(log n) algorithm next.
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)

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

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

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

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.