When addressed exponentiation in chapter 2, the author mentioned
"The number of multiplications required is clearly at most 2 log n(the base is 2), because at most two multiplications (if n is odd) are required to halve the problem. Again,a recurrence formula can be written and solved."
The code as follow:
int pow( int x, unsigned int n)
{
/*1*/ if( n == 0 )
/*2*/ return 1;
/*1*/ if( n == 1 )
/*4*/ return x;
/*5*/ if( even( n ) )
/*6*/ return( pow( x*x, n/2 ) );
else
/*7*/ return( pow( x*x, n/2 ) * x );
}
Q: As the author said,
2^16 need at most 8 multiplications
2^15 ... 7 ...
2^14 ... 7 ...
2^13 ... 7 ...
2^12 ... 7 ...
In fact, I perfrom the code:
2^16 .... 4 ...
2^15 .... 6 ...
2^14 ... 5 ...
2^13 ... 5 ...
2^12 ... 4 ...
So, is somewhere wrong?
There's no contradiction or mistake -- the book gives an upper bound, and you're looking at the exact number of multiplications.
The exact number of multiplications (for n>0) is floor(log_2(n)) + bitcount(n) - 1. That's just by inspecting the code -- the even cases (which perform one multiplication) correspond to 0 bits in the input, the odd cases (which perform an extra multiplication) correspond to 1 bits in the input, and the code stops when it reaches the highest bit.
The book says that 2*log_2(n) is an upper bound for the number of multiplications. That's consistent with the exact formula: floor(log_2(n)) <= log_2(n) and bitcount(n) - 1 <= log_2(n). So floor(log_2(n)) + bitcount(n) - 1 <= 2*log_2(n).
From the exact formula, you can see that the lower the bitcount of n, the worse the upper bound is. The very worst cases are when n is a power of 2: then exactly log_2(n) multiplications will be performed, and the upper bound is off by a factor of 2. The very best cases are when n is one less than a power of 2: then the upper bound will be off by only 1. That matches your empirical table of results.