Fast Exponentiation

Write a program to calculate pow(x,n)?

1)Given two integers x and n, you need to find x^n (given that: x and n are small and no overflow takes place)?

A)Naive approach:

since there is no issue of overflow, we can directly multiply x, to itself n times to get the desired result!!

Code-

Add caption

Time Complexity: O(n)

Space Complexity: O(1)

The demerit of this approach is that it is more prone to overflow.

As the values of x and n increases, the value of pow(x,n) becomes too large to be accommodated in int or even long long int.

B)Time Optimization:

The Time complexity of the naive method is O(n), which can further be improved to O(log(n)) by using a divide and conquerer approach.

IDEA: 

if n is even :

    we calculate pow(x*x,n/2);

else :

    we calculate x*pow(x*x,(n-1)/2);

and we do so, till the value of n becomes == 0;

By doing so, we are reducing n by factors of 2, which ultimately will give us the complexity of O(log(n)). 

Code-

Time Complexity: O(log(n)).

Space Complexity: O(1).

C)Modular Exponentiation:

Now that we have seen, different approaches to find pow(x,n); it's time to get rid of the assumption taken in the above two approaches. i.e the assumption that x and n are small.

We will use modular exponentiation to get rid of our assumptions.

Pre-requisite: (a*b)%m=((a%m)*(b%m))%m

Example: (54*36)%25=19.

         (54%25)=4.  and (36%25)=11

         (4*11)%25 = (44%25) = 19.

Code-

Time Complexity: O(log(n)).

Space Complexity: O(1).

This was all about how we can solve pow(x,n), optimally for large values of x,n. Keep Learning!!😊