4.2.4 ANSWERS (Web hosting faq) TO EXERCISES 577 10. When 1
4.2.4 ANSWERS TO EXERCISES 577 10. When 1 < r < 10 the generating function C(z) has simple poles at the points 1 f wn, where wn = 2Tni/ In 10, hence C(z) = l qor; l + c * (ln ;,;l yl;lw ) + E(z) n#O n where E(z) is analytic in the entire plane. Thus if B = arctan(27r/ In lo), 2 -w,lnr _ 1 cm = log,, r -1 - ~ !J? e + em In lo n>OCC wn(l + w,p ) sin(m0 + 2~ log,, T) -sin(&) 1 = log,, r -1 + ~(1 -k 4r2/(ln 10)2)m 2 (1 + 16+/(ln 10)2)m/2 > 11. When (log, U) mod 1 is uniformly distributed in [ 0, I), so is (log, l/U) mod 1 = (1 -log,U)modl. 12. We have h(z) = JITb f(x) dx g(z/bx)/bx + sZ1 f(x) dx g(z/x)/x, and the same holds for 1(z) = llTb f(x) dx l(z/bx)/bx + s, f(x) dx @/x)/x, hence g(z/bx)qzpxj dz/x) w - l(z)= = dx -+ -@lx) l(z) sl,bf(x) l(zlbx)sz f(x)dx @lx). Since f(x) 2 0, ](h(z)-L(z))/~(z)] 5 S:/,f(~)dxA(g)+~~ f(x)dxA(g) for all z, hence A(h) 5 A(g). By symmetry, A(h) 5 A(f). [Bell System Tech. J. 49 (1970), 1609-1625.1 13. Let X = (log, U) mod 1 and Y = (log, V) mod 1, so that X and Y are inde- pendently and uniformly distributed in [ 0,l). No left shift is needed if and only if X + Y 2 1, and this occurs with probability 3. (Similarly, the probability is 3 that floating point division by Algorithm 4.2.lM needs no normalization shifts; this needs only the weaker assumption that both of the operands independently have the same distribution.) 14. For convenience, the calculations are shown here for b = 10. If k = 0, the probability of a carry is 01 (See Fig. A-7.) The value of the integral is Fig. A-7. and