Binary Exponentiation

Naive Algorithm

we are given numbers x, y .

Multiply x with itself y times to get x^y.

Pseudo code :

    power(x,y):
        result = 1         
        for i = 0 to y:
            result = result*x           
        return result
    

Code :

    // naive algorithm
    // complexity O(n)
    
    #include <iostream>
    using namespace std;
    
    int Binary_exponentiation(int x, int y)
    {
        int res = 1;
        for (int i = 0; i < y; i++) // x.x.x....x ( y times )
        {
            res *= x;
        }
        return res;
    }
    
    int main()
    {
        int x, y;
        cout << "Enter Base: ";
        cin >> x;
        cout << "Enter Exponent: ";
        cin >> y;
    
        int result = Binary_exponentiation(x, y);
        cout << x << "^" << y << " = " << result << "\n";
    }
    
    

Complexity Analysis :

we see that the algorithm has to go through n steps. Hence Time complexity is O(n).

Binary Exponentiation Algorithm

In algorithm 1, we ran the loop for all n numbers.

If we can find half the product i.e, x^y/2 then x^y/2.x ^y/2 = x^y

Hence finding half of it is enough. Now, we can see that we have only half of the actual problem to solve. Continuing to divide the problem into half problems ( sub problems ) we will be just left with x ⁰

So this algorithm finds x ^y/2 when y is even and x ^y-1 when y is odd. when we know x ^y/2

Now the sub problem x ^y/2 or x ^y-1 can be solved by repeating above step.

finally we will end up with x ⁰ from which we can recurse back to find x^y

Pseudo code :

    power(x,y):
        if y == 0:
            return 1
        if y % 2 == 0:
            t = power(x, y/2) 
            return t*t
        else:
            return power(x, y-1)*x
    

Code :

    // binary exponentiation 
    // complexity O(logn)
    
    #include <iostream>
    using namespace std;
    
    int Binary_exponentiation(int x, int y)
    {
        if (y == 0) // base case
        {
            return 1;
        }
    
        if (y % 2 == 0) // even power
        {
            int temp = Binary_exponentiation(x, y / 2);
            return temp * temp;
        }
        else // odd power
        {
            return Binary_exponentiation(x, y - 1) * x;
        }
    }
    
    int main()
    {
        int x, y;
        cout << "Enter Base: ";
        cin >> x;
        cout << "Enter Exponent: ";
        cin >> y;
    
        int result = Binary_exponentiation(x, y);
        cout << x << "^" << y << " = " << result << "\n";
    }
    
    

Complexity Analysis :

Time complexity is O(logN)