Question
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
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.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started