4.3.1 ANSWERS TO EXERCISES 579 18. Let p(a) (Web design tools)
4.3.1 ANSWERS TO EXERCISES 579 18. Let p(a) = P(La) and p(a, b) = xaikib p(k) for 1 5 a < b. Since L, = Lloa U Lloa+l I-, .. U Lloa+g for all a, we have;(a) = p(lOa, lO(a + 1)) by (i). Furthermore since P(S) = P(2S) + P(2S + 1) by (i), (ii), m , we have p(a) = p(2a, 2(a + 1)). ( ) It follows that p(a, b) = ~(2~lO~a, 2m10nb) for all m, n 2 0. If 1 < b/a < b /a , then p(a, b) 5 ~(a , b ). The reason is that there exist integers m, n, m , n such that 2 lO a 5 2m10na < 2 lO b 5 2m 10n b as a consequence of the fact that log 2/ log 10 is irrational, hence we can apply (v). (Cf. exercise 3.5-22 with Ic = 1 and U,, = nlog 2/ log 10.) In particular, p(a) 2 p(a + l), and it follows that p(a, b)/p(a, b + 1) 2 (b -a)/(b + 1 -a). (Cf. Eq. 4.2.2-15.) Now we can prove that p(a, b) = p(a , b ) w h enever b/a = b fa ; for p(a, b) = p(lOna, 10 b) 5 c,p(lOna, 10 b -1) 5 c,p(a , b ), for arbitrarily large values of n, where c,, = 10n(b -a)/(lO (b -a) -1) = 1 + O(lOmn). For any positive integer n we have p(an, b ) = p(a , ba - )+p(ba - , b2anp2)+ . . +p(bn- a, b ) = np(a, b). If 10m 5 an 5 10m+ and 10 2 b < 10n + , then PC10 m+l, 10m ) 5 p(an, b ) 5 p(lO , lo + ) by (v). But ~(1, 10) = Thy (iv), hence p(lO , 10m ) = m -m for all m 2 m. We conclude that [log,, b J -[log,, a ] -1 2 np(a, b) 5 Llogio b ] + ]logio a ] + 1 for all n, and p(a, b) = log,,(b/a). [This exercise was inspired by D. I. A. Cohen, who proved a slightly weaker result in J. Combinatorial Theory (A) 20 (1976), 367370.1 SECTION 4.3.1 2. If the ith number to be added is ui = (uziuis.. Uzn)b, use Algorithm A with step A2 changed to the following: A2 . [Add digits.] Set wj +- (urj + . + umj + k) mod b, and k t ](uiJ + . . . + urn3 + k)/bJ. (The maximum value of k- is m -1, so step A3 would have to be altered if m > b.) 3. ENTI N 1 JOV OFLO 1 Ensure overflow is off. ENTA 0 1 k + 0. 2H ENT2 0 N (r12 G next value of k) ENT3 MN-N, 1 N (LOC(ui,) = U + n(i -1) + j) 3H ADD U,3 MN rA t rA+u,,. JNOV *+2 MN INC2 1 K Carry one. DEC3 N MN Repeat for m 2 i 2 0. J3P 3B MN (r13 = n(i -1) + j) STA W,l N wj + rA. ENTA 0,2 N k + r12. DECl 1 N JIP 2B N Repeat for n 2 j 2 0. STA W 1 Store final carry in wc. 1 Running time, assuming that K = ;MN, is 5.5MN + 7N + 4 cycles.