4.6.3 EVALUATION OF POWERS 463 in 6. [A4.26] (Web server type)
4.6.3 EVALUATION OF POWERS 463 in 6. [A4.26] exercise If a slight 5, so that change is made the nodes below to the definition n are attached of the power tree in decreasing order that is given Tl+ak-1, . . . . 71.+%, n+al, n+l instead of increasing order, we get a tree whose first five levels are Show that this tree gives a method of computing x that requires exactly as many multiplications as the binary method; therefore it is not as good as the power tree, although it has been constructed in almost the same way. 7. [M.Z1] Prove that there are infinitely many values of n a) for which the factor method is better than the binary method; b) for which the binary method is better than the factor method; c) for which the power tree method is better than both the binary and factor methods. (Here the better method shows how to compute xn using fewer multiplications.) 8. [M.21] Prove that the power tree (exercise 5) never gives more multiplications for the computation of xn than the binary method. 9. [M.B] Design an exponentiation procedure that is analogous to Algorithm A, but based on a general radix m 2 2. Your method should perform approximately lgn + v + 2m multiplications, where v is the number of nonaero digits in the m-ary representation of n. 10. [JO] Figure 14 shows a tree that indicates one way to compute ZI? with the fewest possible multiplications, for all n 5 100. How can this tree be conveniently represented within a computer, in just 100 memory locations? k 11. [A4.26] The tree of Fig. 14 depicts addition chains ac, al, . . . , a, having l(u%) = i for all i in the chain. Find all addition chains for n that have this property, when n = 43 and when n = 77. Show that any tree such as Fig. 14 must include either the path 1, 2, 4, 8, 9, 1 7, 34, 43, 77 or the path 1, 2, 4, 8, 9, 17, 34, 68, 77. 12. [MM] Is it possible to extend the tree shown in Fig. 14 to an infinite tree that yields a minimum-multiplication rule for computing z?, for all positive integers n? 13. [MZ1] Find a star chain of length A + 2 for each of the four cases listed in Theorem C. (Consequently Theorem C holds also with 1 replaced by 1*.) 14. [M35] Complete the proof of Theorem C, by demonstrating that (a) step r -1 is not a small step; and (b) X(o,-k) cannot be less than m -1. 15. [M42] Write a computer program to extend Theorem C, characterizing all n such that 1(n) = 1(n) + 3 and characterizing all n such that l*(n) = x(n) + 3.