Most popular web site - 446 ARITHMETIC 4.6.3 Yhl, / A I A
446 ARITHMETIC 4.6.3 Yhl, / A I A I 1Li A 7 A r I i F: r 21 22 23 40 I I I I I I / I A P A A Pe I I 38 29 56 31 42 44 46 41 80 39 54 45 60 50 51 96 35 52 43 68 37 72 49 66 65 I I I I I I / I I I I I I I I I I I / 76 58 57 59 62 84 88 47 92 82 83 85 78 55 90 63 75 100 53 97 99 70 61 77 86 69 74 73 98 67 81 I I I II I I I 89 94 93 95 79 91 71 87 Fig. 14. A tree that minimizes the number of multiplications, for n 5 100. The length of this chain is m -2 + (k + 1)t; and it can often be reduced by de- leting certain elements of the first row that do not occur among the coefficients dj, plus elements among 2do, 4do, . . . that already appear in the first row. Whenever digit dJ is zero, the step at the right end of the corresponding line may, of course, be dropped. Furthermore, as E. C. Thurber has observed [Duke Math. J. 40 (1973), 907-9131, we can omit all the even numbers (except 2) in the first row, if we bring values of the form dj/2e into the computation e steps earlier. The simplest case of the m-ary method is the binary method (m = 2), when the general scheme (4) simplifies to the S and x rule mentioned at the beginning of this section: The binary addition chain for 2n is the binary chain for n followed by 2n; for 2n + 1 it is the binary chain for 2n followed by 2n + 1. From the binary method we conclude that l(aeo + 2e1 + . . . + 2e ) 5 e. + t, if eo > el > … > et 2 0. (5) Let us now define two auxiliary functions for convenience in our subsequent discussion: W = lk nJ; (6) v(n) = number of l s in the binary representation of n. (7) Thus X(17) = 4, ~(17) = 2; these functions may be defined by the recurrence relations X(1) = 0, X(2n) = X(2n + 1) = A(n) + 1; (8) Y(1) = 1, v(2n) = v(n), v(2n + 1) = v(n) + 1. (9)