Algorithm : Exponentiate

Algorithm : Exponentiate

Time complexity : O( log(n) )

Problem Description : To calculate x^n (x to the power of n) using minimum steps. Trick lies in the Algorithm being followed.

One general way to calculate x^n that is very crude is shown below.

void exponentaite(long int x,lont int n)
{

    long int result=1;  //to store the final result

    while( n-- )
    {
      result  *= x;
    }

    printf("%lld\n",result);
    return;
} //end of function

Definitely it takes O(n) linear time to do the work. But in tighter cases, it might be handy to do a task in short hand just if you know this small trick. I will write a short code below in C again, and i hope you might get the logic.

 typedef long int lint;
 typedef long long int llint;

 llint exponentiate_fast ( llint sample ,  llint n )
 {
   llint result=1 ;
   while( m > 0 )
   {
     while( m%2 == 0 )
     {
       sample *= sample;
       m /= 2;
     }
     --m;
     result *= sample;
   }
   return result;
 }

An Ideone sample running example has been provided to get you a clear insight. You can change the datatype as per your usage.

Concept behind this computation :

Every computation of x^n can be expressed as x^(2m+k), for some 'm' and 'k'. Hence instead of multiplying n times - which obviously was O(n) - we calculate its squares until the the inner loop terminates when m equals its value to 1.

Hence every time we square it, we are dividing are task into halves and hence its easy to show up that the time req is order of log(n).

Tip : You can examine the execution flow by placing 'printf' check points at suspected positions and hence analyse them. Its a good practice for newbies and helps improve debugging skills.