638 ANSWERS (Web server extensions) TO EXERCISES 4.6.3 blocks of >
638 ANSWERS TO EXERCISES 4.6.3 blocks of > CY in a row. If m and m have P(o), so does m V m ; if m has P(a) then p(m) has P(cy + 6). Hence Bi has P(l + 6~). Finally if-m has P(a) then v(p(m)) 5 (a + G)v(m)/a; for v(m) = vi + . . . + vq, where each block size vj is 2 cr, hence &Cm)) I (~1 + 6) + . . . i- (vq + 6) I (1 -I- 6/@1 i-. . . t (1-k bl4b (4 Let f = b, + cI be the number of nondoublings and s the number of small steps. If f 2 3.2711gv(n) we have s 2 lgv(n) as desired, by (16). Otherwise we have ai 5 (1 + 2-6)bi2CE+dt for 0 5 i < r, hence n 2 ((1 + 2-6)/2)br2r, and r 2 lgn + b, - b, lg(1 + 2-6) 2 lg n + lg v(K) -lg(1 + bc,) -b, lg(1 + 2-6). Let 6 = [lg(f + l)]; then ln(1 f 2X6) 5 ln(1 f l/(f + 1)) 5 l/(f + 1) 2 6/(1 + Sf), and it follows that lg(1 + bz) + (f -Z) lg(1 + 2-6) 2 lg(1 + Sf) for 0 2 z 5 f. Hence finally l(n) 2 lgn+lgv(n)-lg(l+(3.271 lgv(n))[lg(l+3.271 lgv(n))]). [Theoretical Comp. Sci. 1 (1975) l-121 29. In the paper just cited, Schonhage refined the method of exercise 28 to prove that l(n) 2 lgn + lgv(n) -2.13 for all n. Can the remaining gap be closed? 30. n = 31 is the smallest example; 1(31) = 7, but 1, 2, 4, 8, 16, 32, 31 is an addition-subtraction chain of length 6. [After proving Theorem E, Erdiis stated that the same result holds also for addition-subtraction chains. Schijnhage has extended the lower bound of exercise 28 to addition-subtraction chains, with v(n) replaced by v(n) = minimum number of nonzero digits to represent n = (nnq . . . ns)a where each nj is -1, 0, or +l. This quantity P(n) is the number of l s, in the ordinary binary representation of n, that are immediately preceded by 0 or by the string OO(lO)kl for some k 2 0.1 32. First compute 2i for 1 2 i 5 x(n,), then compute each n = nj by the following variant of the 2k-ary method: For all odd i < 2k, compute fi = c{ 2kt-te ] dt = 2%) where n = (. . . drds)+, in at most [i lgn] steps; then compute n = c ifi in at most cl(i) + 2k- f ur th er steps. The number of steps per nj is 5 Li lgnj + O(/C~~), and this is x(n)/U(n) + O(x(n)Ux(n)/U(n) ) when k = llg lgn -3 lg lg lg n]. [A generalization of Theorem E gives the corresponding lower bound. Reference: SIAM J. Computing 5 (1976), 100-103. See also exercise 39.1 33. The following construction due to D. J. Newman provides the best upper bound currently known: Let k = pl . . . p7 be the product of the first r primes. Compute k and all quadratic residues mod k by the method of exercise 32, in 0(2- klog k) steps (because there are approximately 2- k quadratic residues). Also compute all multiples of k that are < m2, in about m2/k further steps. Now m additions suffice to compute 12, 22, . . . , m2. We have k = exp(p, + O(p,/(logp,) ooo)) where p7 is given by the formula in exercise 4.5.4-35; so by choosing r = [( 1 + (1 + 4 In 2)/lg lg m) In m/in In ml it follows that 1(12,. . . , m2) = m + O(m . exp(-3 In 2 In m/in In m)). On the other hand, D. Dobkin and R. Lipton have shown that, for any E > 0, 1(12,. . . , m2) > m+m2f3-e when m is sufficiently large [SIAM J. Computing 9 (1980), 121-1251. 35. See Discrete Math. 23 (1978), 115-119. 36. Eight; there are four ways to compute 39 = 12 + 12 + 12 + 3 and two ways to compute 79 = 39 + 39 + 1.