Time complexity of power()

Question

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?

Given an arbitrary degree of precision, it's possible to compute exponentation in constant time. — Crashworks, Mar 08 '11 at 10:23
@Crashworks only if the exponent is bounded by a constant, right? — vidstige, Mar 08 '11 at 10:27
@vidstige Yes, I assume both base and exponent are stored in a finite-length register. — Crashworks, Mar 08 '11 at 10:28
@Crashworks: this homework assignment is after an algorithm with better complexity, though, not a semantic argument about whether it's ever appropriate to apply complexity analysis to programs with a finite upper bound on the size of the input. — Steve Jessop, Mar 08 '11 at 10:31
@Steve Jessop: Hush, you're spoiling a perfectly good snipe hunt! — Crashworks, Mar 08 '11 at 10:32

Prasoon Saurav · Accepted Answer · 2011-03-08T10:32:59.140

41

Exponentiation by Squaring.

enter image description here

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)

edited Mar 08 '11 at 10:32

answered Mar 08 '11 at 10:21

Prasoon Saurav

91,295
49
239
345

score 7 · Answer 2 · answered Mar 08 '11 at 10:22

7

Use Exponentiation by squaring

answered Mar 08 '11 at 10:22

Oswald

31,254
3
43
68

score 5 · Answer 3 · answered Mar 08 '11 at 10:30

5

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".

answered Mar 08 '11 at 10:30

Eric Bainville

9,738
1
25
27

2

This answer would have been much more useful had it links to reading on those particular algorithms. – Daniel Dec 14 '15 at 17:47

tgmath · Answer 4 · 2011-03-08T10:30:48.303

4

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

edited Mar 08 '11 at 10:30

answered Mar 08 '11 at 10:24

tgmath

12,813
2
16
24

score 3 · Answer 5 · edited Jan 16 '12 at 07:30

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;
}

praveen · Answer 6 · 2013-11-07T19:08:22.863

2

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;
    }
}

enter image description here

edited Nov 07 '13 at 19:08

answered Jan 16 '12 at 07:22

praveen

1,871
1
12
5

Time complexity of power()

6 Answers6

Linked