I implemented this function power() which takes two arguments a and b 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?
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;
}