Because a^b = (a*a)^(b/2), so each multiplication reduces the exponent
by half. Therefore the number of multiplications is (roughly) log2 b.
int pow(int a, int b)
{
int result = a;
while(b 1)
{
result *= (b1) ? a*result : result;
b = 1;
}
return result;
}
You can see that a^16
@Don, Ankuj. I believe that Don's algorithm uses precisely
floor{log_2(b)) + (the number of one bits in b) - 1.
Dave
On Sep 29, 1:38 pm, Don dondod...@gmail.com wrote:
Because a^b = (a*a)^(b/2), so each multiplication reduces the exponent
by half. Therefore the number of multiplications is
Make two conditions for even and odd power. and use it to make solve
higher power
That could be solved in log b time
.
On 30-Sep-2011 4:12 AM, Dave dave_and_da...@juno.com wrote:
@Don, Ankuj. I believe that Don's algorithm uses precisely
floor{log_2(b)) + (the number of one bits in b) -