Exponentiation

Exponentiation is raising a number to a power (represented as xn).

Assuming n>=0

  • Naive method to calculate xn
    int exponentiate(int x, int n)
    {
      int result=1;
      for(int i=1; i<=n; i++)
      {
        result=result*x;
      }
    
      return result;
    }
    

    The above code takes O(n) time to compute xn

  • Exponentiation by squaring
    There exists another method to calculate xn in O(log n).

    It is evident that

    xn = xn/2*xn/2*x   if x is odd

    xn = xn/2*xn/2   if x is even

    We can use this fact to calculate xn in O(log n) time.

    int exponentiate(int x, int n)
    {
      static int result;
      if(n==0)
      {
        return 1;
      }
      if(n%2==1)
      {
        result=exponentiate(x, n/2);
        result=result*result*x;
      }
      else
      {
        result=exponentiate(x, n/2);
        result=result*result;
      }
    
      return result;
    }
    

    Complexity of above code is O(log n).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s