466 ARITHMETIC 4.6.3 37. [M,u] The (Web host music) binary addition
466 ARITHMETIC 4.6.3 37. [M,u] The binary addition chain for n = 2 O -+-. . .+2et, when eo > > et 2 0, is 1, 2, . . . , 2eo-e1, 2eo-e1 + 1, . . . , 2e0-e2 + 2e1-ez, 2 Ope2 + 2e1-ez + 1, . . . , n. This corresponds to the S-and-X method described at the beginning of this section, while Algorithm A corresponds to the addition chain obtained by sorting the two sequences (1,2,4,. . ,2 O) and (set-l + 2et, 2 t-2 + 2et-1 + 2 t,. . . , n) into increasing order. Prove or disprove: Each of these addition chains is a dual of the other. 38. [M,C?7] How many addition chains without useless steps are equivalent to each of the addition chains discussed in exercise 37, when eo > el + l? b 39. [A4.25] (J. Olivos, 1979.) Let l([nl,na,. . . , n,]) be the minimum number of mul- tiplications needed to evaluate the monomial z; z~ . . CI$ in the sense of exercise 27, where each nz is a positive integer. Prove that this problem is equivalent to the problem of exercise 32, by showing that I( [nl, n2, . . , n,]) = l(nl, n2, . , n,) + m - 1. [Hint: Generalize the directed graph construction by considering graphs with more than one source vertex.] F 40. [kC?I] (J. Olivos.) Generalizing the factor method, prove that l(mlnl + . . . + mtnt) I l(ml, . . . , mt)+l(nl,…,nt)+t-1, where l(nl, . . , n,) is defined in exercise 32. 41. [M40](P. Downey, B. Leong, R. Sethi.) Let G be a connected graph with n vertices (1,. , n} and m edges, where the edges join uj to vj for 1 5 j 5 m. Prove that 1(1,2,. . . , 2An, 2AU1 + 2A 1 + 1,. . . , 2AUm + 2Avm + 1) = An + m + k for all sufficiently large A, where k is the minimum number of vertices in a vertex cover for G (i.e., a set containing either uj or V~ for 1 5 j 5 m). 4.6.4. Evaluation of Polynomials Now that we know efficient ways to evaluate the special polynomial z%, let us consider the general problem of computing an nth degree polynomial U(X)= u,zn + un-&–l + * * * + UlZ + U-J, GL # 0, (1) for given values of Z. This problem arises frequently in practice. In the following discussion we shall concentrate on minimizing the number of operations required to evaluate polynomials by computer, blithely assuming that all arithmetic operations are exact. Polynomials are most commonly evaluated using floating point arithmetic, which is not exact, and different schemes for the evaluation will, in general, give different answers. A numerical analysis of the accuracy achieved depends on the coefficients of the particular polynomial being considered, and is beyond the scope of this book; the reader should be careful to investigate the accuracy of any calculations undertaken with floating point arithmetic. In most cases the methods we shall describe turn out to be reasonably satisfactory from a numerical standpoint, but many bad examples can also be given. [See Webb Miller, SIAM J. Computing 4 (1975), 105-10 7, for a survey of the literature on stability of fast polynomial evaluation, and for