How does the number of multiplications used by the al-gorithm in Exercise 24 com

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

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.

Explanation / Answer

Suppose x and y are each n bits long; in this chapter we will consistently use the letter n forthesizesofnumbers. Thenthesumof x andy is n+1 bitsatmost,andeachindividualbit of thissum gets computed inaxed amountof time. The total runningtime for the addition algorithmisthereforeoftheform c0+c1n,where c0 andc1 aresomeconstants;inotherwords, itis linear. Instead of worryingaboutthe precise valuesof c0 and c1, we willfocus onthe big pictureanddenotetherunningtimeas O(n).
Nowthatwehaveaworkingalgorithmwhoserunningtimeweknow,ourthoughtswander inevitablytothequestionofwhetherthereissomethingevenbetter.
Isthereafasteralgorithm? (Thisisanotherpersistentquestion.) Foraddition,theanswer is easy: in order to add two n-bit numbers we must at least read them and write down the answer, and even that requires n operations. So the addition algorithm is optimal, up to multiplicativeconstants!

Onward to multiplication! The grade-school algorithm for multiplying two numbers x and y istocreateanarrayofintermediatesums,eachrepresentingtheproductof x byasingledigit of y. Thesevaluesareappropriatelyleft-shiftedandthenaddedup. Supposeforinstancethat wewantto multiply 13×11, orinbinarynotation, x = 1101 and y = 1011. Themultiplication wouldproceed thus.
24
Algorithms
1 1 0 1 × 1 0 1 1 1 1 0 1 (1101times1) 1 1 0 1 (1101times1,shiftedonce) 0 0 0 0 (1101times0,shiftedtwice) + 1 1 0 1 (1101times1,shiftedthrice) 1 0 0 0 1 1 1 1 (binary143) In binary this is particularly easy since each intermediate row is either zero or x itself, leftshifted an appropriate amount of times. Also notice that left-shifting is just a quick way to multiply by the base, which in this case is 2. (Likewise, the effect of a right shift is to divide bythebase,roundingdownifneeded.) The correctness of this multiplication procedure is the subject of Exercise 1.6; let’s move on andgure out how long it takes. If x and y are both n bits, then there are n intermediate rows, withlengths of up to 2n bits (taking the shifting into account). The total time taken to adduptheserows,doingtwonumbersatatime,is O(n) + O(n) +···+ O(n) | {z } n1 times , which is O(n2), quadratic in the size of the inputs: still polynomial but much slower than addition(aswehaveallsuspected sinceelementaryschool). But Al Khwarizmi knew another way to multiply, a method which is used today in some European countries. To multiply two decimal numbers x and y, write them next to each other, as in the example below. Then repeat the following: divide the rst number by 2, rounding down the result (that is, dropping the .5 if the number was odd), and double the second number. Keep going tillthe rst numbergets down to 1. Then strike out allthe rows inwhichtherstnumberiseven,andaddupwhateverremainsinthesecondcolumn. 11 13 5 26 2 52 (strikeout) 1 104 143 (answer) But if we now compare the two algorithms, binary multiplication and multiplication by repeated halvings of the multiplier, we notice that they are doing the same thing! The three numbers added in the second algorithm are precisely the multiples of 13 by powers of 2 that were added in the binary method. Only this time 11 was not given to us explicitly in binary, andsowehadtoextractitsbinaryrepresentationbylookingattheparityofthenumbersobtained from it by successive divisions by 2. Al Khwarizmi’ssecond algorithmis a fascinating mixtureofdecimalandbinary!

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.