There are at least two different algorithms that can compute XN
for some positive integer N.
Algorithm 1 is to use N – 1 multiplications.
Algorithm 2 works in the following way: if N is even, XN = XN / 2 XN / 2; and if N is odd, XN = X(N – 1) / 2 X(N – 1) / 2 X. Figure 2.11 in your textbook gives the recursive version of this algorithm.
Your tasks are:
(1) Implement Algorithm 1 and an iterative version of Algorithm 2;
(2) Analyze the complexities of the two algorithms;
(3) Measure and compare the performances of Algorithm 1 and the iterative and recursive implementations of Algorithm 2 for X=1.0001 and N = 1000, 5000, 10000, 20000, 40000, 60000, 80000, 100000.
1