One efficient algorithm employs the repeated-squaring method. The repeated-squaring method works as follows: if the value of x*x is already at hand, it is more efficient to calculate x4 as (x*x)*(x*x) rather than starting from scratch using x*x*x*x. You can decompose any integer power into a sequence of repeated squares.
The algorithm below examines each bit in the exponent, starting with the rightmost bit. If the bit is set, the result variable h is multiplied by x, which holds the base raised to the current power of 2. In either case, x is subsequently squared, and the exponent is shifted one bit to the right (i.e., divided by 2). This process is repeated until the exponent is exhausted. Note that the exponent is passed as unsigned int: this way, the C Standard guarantees that the bits shifted in from the left will be 0. To find a negative integer power, you must call 1.0/qip(x, abs(n)).
/* Compute pow(x,n) for positive
integer n through repeated
squarings */
double qip(double x,
unsigned int n)
{
double h = 1.0;
while(n){
if(n&1){ h *= x; }
x *= x;
n >>= 1;
}
return h;
}
Table 1 shows the results of a very crude performance
comparison. The values in the table represent the factor by which qip(x,n)
is faster than pow(x,n) for various values of n. For n=2,
qip is almost three times as fast as pow, but the speed-up degrades
quickly as n becomes larger. The results do not depend insignificantly
on x.