Binary Exponentiation

Binary exponentiation is a commonly used optimization technique to compute the power of a number. It involves computing the power of a number using repeated multiplication and division by 2. This technique is useful when we need to compute the power of a number very quickly and efficiently, especially when the power is very large.


#include<iostream>
using namespace std;

int power(int x, int n) {
    int res = 1;
    while(n) {
        if(n&1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}

int main() {
    int x = 3, n = 5;
    cout<<x<<" raised to "<<n<<" is "<<power(x,n);
    return 0;
}

In the above code, the function power takes in two parameters – x (the base) and n (the exponent). It then computes x raised to the power n using binary exponentiation and returns the result.

The function works as follows:

It initializes a variable res to 1.

It then enters a while loop that continues until n becomes 0.

Inside the loop, it checks if the least significant bit of n is 1 using the bitwise AND operator with 1. If it is 1, it multiplies res by x.

It then multiplies x by itself (square x) and right-shifts n by 1. This is equivalent to dividing n by 2.

The loop continues until n becomes 0.

Finally, the function returns res, which is the result of x raised to the power n.

The output of the above code would be:


3 raised to 5 is 243

This is the result of 3 raised to the power of 5 computed using binary exponentiation.

The time and space complexity of the binary exponentiation algorithm is as follows:

Time Complexity: The time complexity of the binary exponentiation algorithm is logarithmic to the value of the exponent. The reason for this is that the algorithm decreases the value of the exponent by half with each step, so the number of iterations required to that value the exponent becomes significantly less as the input exponent becomes larger. Therefore, the time complexity of the binary exponentiation algorithm is O(log n), where n is the value of the exponent.

Space Complexity: The space complexity of the binary exponentiation algorithm is constant. Regardless of the value of the exponent, this algorithm requires only a constant amount of memory to store its variables. Therefore, the space complexity of the binary exponentiation algorithm is O(1).

In conclusion, the binary exponentiation algorithm is a very efficient algorithm for computing powers of a number, particularly when dealing with very large exponents, with a time complexity of O(log n) and a space complexity of O(1).

PRACTICE PROBLEMS :

Power of Three

Pow(x, n)