Back To Blog

Binary Exponentiation

Posted On: 01-09-2018


Brute Force:

int F(int num,int pow)
{
        int res = 1;
        for(int i = 1;i <= pow;i ++)
                res = res*num;
        return res;
}

O(POW)

 

Binary Exponentiation: 

Recurrence Relation:

if(i is even)

F(i) = F(i/2) * F(i/2)

else

F(i) = F(i/2) * F(i/2) * num

Using above recurrence relation:

int F(int num,int pow)
{
        if(pow == 0)
                return 1;
        int res = F(num,pow/2);
        if(pow%2 == 0)
                res = res * res;
        else
                res = res * res * num;
        return res;
}

O(log(POW))

Iterative Binary Exponentiation:

int F(int num,int pow)
{
        int res = 1;
        while(pow > 0)
        {
                if(pow%2 == 1)
                        res = res * num;

                num = num * num;

                pow = pow/2;
        }
        return res;
}

O(log(POW))

Iterative Binary Exponentiation with modulo MOD:

int F(int num,int pow,int mod)

        int res = 1;
        num = num%mod;
        while(pow > 0)
        {
                if(pow%2 == 1)
                        res = (res * num)%mod;
                num = (num * num)%mod;
                pow = pow/2;
        }
        return res;
}