Time complexity of power() [duplicate]

This question already has answers here: The most effi开发者_运维百科cient way to implement an integer based power function pow(int, int) (21 answers) Closed 5 years ago.

I implemented this function power() which takes two arguments a and b and computes a^b.

typedef long long int LL;

LL power(int a,int b)
{
   int i = 1;
   LL pow = 1; 
   for( ; i <= b ; ++i )
     pow *= a;
   return pow;
}

Given : a^b falls in the range of long long int.

Problem : How to reduce the time complexity of my algorithm?

---

Exponentiation by Squaring.

A non-recursive implementation

LL power(int a, int b)
{
  LL pow = 1;
  while ( b ) 
  {
         if ( b & 1 ) 
         {
           pow = pow * a;
           --b;
         }
         a = a*a;
         b = b/2;
  }
  return pow;
}

This algorithm requires log₂b squarings and at most log₂b multiplications.

The running time is O(log b)

---

---

Use Exponentiation by squaring

---

Exponentiation by squaring does not give the minimal number of multiplications in all cases. Look for "addition chains", "Brauer chains", "Hansen chains", and "Scholz conjecture".

---

I would suggest: Use the pow() function if you really need a faster function (with long double ) or think about your homework for yourself.

For arbitrary precision: See the GMP lib http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation

---

Use exponentiation by squares. That is if we need a^b, we check if b is even, if b is even, we find (a^2)^(b/2), else we find a*((a^2)^(b/2)). This may not be the best algorithm, but it is better than the linear algorithm.

int Power(int a, int b)
{
    if (b>0)
    {
       if (b==0)
          return 1;
       if (a==0)
          return 0;
       if (b%2==0) {
          return Power(a*a, b/2);
       }
       else if (b%2==1)
       {
        return a*Power(a*a,b/2);
       }
    }
    return 0;
}

---

Here is the recursive implementation of Java code for 2 to the power of n with O(log n) complexity using Exponentiation by squaring

int ans=1;
public int myTwoPower(int n){
    if(n<=0)
        return 1;

    if(n%2 !=0){            
        return myTwoPower(n-1)*2;
    }
    else{
        ans = myTwoPower(n/2);
        return ans * ans;
    }
}