How does the number of multiplications used by the al-gorithm in Exercise 24 compare to the number of multi-plications used by Algorithm 2 to evaluate

a^2^n ( just to be clear is a to the power of two, and two is to the power of n) ?

First let me state exercise 24 and algorithm 2.

ex 24: Devise a recursive algorithm to finda^2^n, where a is a real number and n is a positive integer. [Hint:Use the equality a^2^n+1 = (a^2^n)^2.]

The answer is: procedure twopower(n: positive integer, a: real number)

if n=1 return a^2

else

return twopower(n-1, a)^2

ALGORITHM 2

A Recursive Algorithm for Computing a^n.

procedure power (a: nonzero real number, n: nonnegative integer)

if n= 0 then return 1

else return a * power (a, n1)

{output is a^n}

I have found two different solutions from Chegg textbook solutions and from a solution manual ad they are both different. I'm not sure how they come up with each solution and I'm unsure if they are both correct.

Algorithm 2 uses 2^n multiplications by a, one for each factor of a in the product a^2^n The algorithm in Exercise 24, based on squaring, uses only n multiplications (each of which is a multiplication of a number by itself). For instance, to compute a^2^4= a^16, this algorithm will compute a*a= a^2 (one multiplication), then a^2. a^2 = a^4 (a second multiplication), then a^4. a^4 = as (a third),and finally as. as = a^16 (a fourth multiplication). (Solutions Manual)

Chegg solutions states for ex 24 uses 2^n multiplications, for algorithm 2 it states the number of multiplications used is n. Thank you for your help in advance.