Program(s) for finding power of a number

First, an interactive solution: (raising a to the power of b)

public double Power(double a, int b) {
if (b<=0) return 0; // we want a positive integer for the exponent
else {
double c=1;
for (int i=0; i c*=a;
}
return c;
}
}


Very easy and linear. You start from one and go on multiplying c by a so c is respectively 1, a, a^2, a^3, ... a^b.
When done, you return c. This one takes linear time.

Second, a recursive solution:

public double Power(double a, int b) {
if (b<=0) return 0;
else if (b==1) return a;
else {
return a*Power(a,b-1);
}
}


This is also an easy one. What we do here? Simple: we calculate a^b=a * a^(b-1). This is done by the recursion and takes linear time as well.

So, how can we beat these to slugs? We do this way.
Let me give you an example with b being a power of 2 (which is the easiest to understand).

Imagine you have to evaluate a^64. You could think this:

a^64 = c^32 where c=a^2
c^32 = d^16 where d=c^2
d^16 = e^8 where e=d^2
e^8 = f^4 where f=e^2
f^4 = g^2 where g=f^2
g^2 = g*g

This requires 6 operations. Using one of the two previous algorithms takes 64 operations! In fact 6=log64 (log is meant in base 2 obviously).

Now, things are different when b isn't a power of 2, but the algorithm is just a bit more complicated. Let's see an example again. We'll evaluate a^20.

a^20 = c^10 where c=a^2
c^10 = d^5 where d=c^2
d^5 = d * e^2 where e=d^2
e^2 = e*e

This requires 5 operations. Log16=4 and log32=5 so as you can see we have here 5=Ceiling(log20). This happens when b isn't a power of 2, but the cost of the entire algorithm doesn't grow that much and we can still say that it runs in logarithmic time (this is more true when b is a medium-big number).

private double Power(double a, int b) {
if (b<0) {
throw new ApplicationException("B must be a positive integer or zero");
}
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;
}


Another solution can be :
a^b = 10^(ln[10](a) * b)

Reference : http://www.osix.net/modules/article/?id=696