one of the basic algorithms has been the exponentiation.
This involves raising an integer to a power (which is also an integer).
The obvious algorithm to compute X^N uses N-1 multiplications.
In this section we shall see a better algorithm compared to the above one.
long int pow(long int X, unsigned int N)
/* 1 */ if(N==0)
/* 2 */ return 1;
/* 3 */ else if(N==1)
/* 4 */ return X;
/* 5 */ else if(isEven(N))
/* 6 */ return pow( X * X, N /2);
/* 7 */ return pow( X * X, N /2)*X;
Lines 1 to 4 handle the base case of recursion. Otherwise
if N is even , we have X^N = X^N/2 * X^N/2
and if N is odd, we have X^N= X^(N-1)/2 * X^(N-1)/2
The number of multiplications required is clearly at most 2 log N, because at most 2 multiplications are required(if N is odd) to halve the problem.
Simple intuition obviates the need for a brute-force approach.
one of the following alternative lines for line 6 are bad, even though they look correct:
/* 6a */ return pow( pow( X,2) , N/2);
/* 6b */ return pow( pow( X,N/2) , 2);
/* 6c */ return pow(X,N/2) * pow(X,N/2);
Both lines 6a and 6b are incorrect because when N is 2, one of the recursive calls to pow has 2 as the second argument.Thus no progress is made, and an infinite loop results in an eventual crash.
Using line 6c effects the efficiency, because there are now 2 recursive calls of size N/2 instead of one.