Time complexity of power()
Solution 1
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 log2b squarings and at most log2b multiplications.
The running time is O(log b)
Solution 2
Use Exponentiation by squaring
Solution 3
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".
Solution 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
Solution 5
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;
}
Admin
Updated on July 09, 2022Comments
-
Admin almost 2 years
I implemented this function
power()
which takes two argumentsa
andb
and computes ab.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 : ab falls in the range of
long long int
.
Problem : How to reduce the time complexity of my algorithm? -
Daniel over 8 yearsThis answer would have been much more useful had it links to reading on those particular algorithms.