In this assignment you will analyze two algorithms, written in Java-like pseudocode, for calculating powers of real numbers:

• SP(x,n) // SP stands for "slow power"
• FP(x,n) // FP stands for "fast power"

These algorithms both take two parameters: a non-zero real number called x, and a natural number called n. The algorithms do not perform any error checking of the values passed to them. They are simply assumed to be correct. These algorithms both return a real number which is xn

Here is pseudocode for the algorithms:

SP(x,n) result = 1 for (i=1; i<=n; i++) result = result *x return result

FP(x,n) if n==0 return 1 if n is even return FP(x*x, n/2) else return x*FP(x*x,(n-1)/2)

In this analysis you will be comparing the efficiency of the two algorithms by counting the use of the most expensive operation in the algorithms, which is multiplication. (Note that because all the divisions in FP are integer divisions by 2, they can be implemented efficiently as right binary shifts).

In the questions that follow, it doesnt matter what x is.

1. How many multiplications will be used in total to calculate SP(x,n)?
2. Trace the execution of the return statements of FP(x,53), printing them statements one by one as they are being called and stating next to it the number of multiplications in that statement. The first line of the answer is:

return x*FP(x*x,26) // 2 multiplications (in red: the first one, in the first parameter, is executed before FP is called. The second one is executed after)

3. Add one line to the FP algorithm to reduce the total number of multiplications in FP(x,n) when FP is initially called with n > 0. Rewrite the algorithm underneath:

4. What is the total number of multiplications used by your new algorithm to calculate FP(53)?