4.2.4 DISTRIBUTION OF FLOATING POINT NUMBERS 249 relative (Cheap web hosting)
4.2.4 DISTRIBUTION OF FLOATING POINT NUMBERS 249 relative error, A(f) = where 1(x) = l/(x In b) is the density of the logarithmic distribution. Prove that A(h) 5 min(A(f),A(g)). (I n p ar t KU 1ar, if either factor has logarithmic distribution the product does also.) b 13. [M@ The floating point multiplication routine, Algorithm 4.2.1M, requires zero or one left shifts during normalization, depending on whether fufv 2 l/b or not. Assuming that the input operands are independently distributed according to the logarithmic law, what is the probability that no left shift is needed for normalization of the result? b 14. [HM30] Let U and V be random, normalized, positive floating point numbers whose fraction parts are independently distributed according to the logarithmic law, and let pk be the probability that the difference in their exponents is k. Assuming that the distribution of the exponents is independent of the fraction parts, give an equation for the probability that fraction overflow occurs during the floating point addition of U $ V, in terms of the base b and the quantities PO, pl, pz, . . . . Compare this result with exercise 1. (Ignore rounding.) 15. [HM.Z8] Let U, V, PO, pl, . be as in exercise 14, and assume that radix 10 arithmetic is being used. Show that regardless of the values of PO, pl, pz, , the sum U @ V will not obey the logarithmic law exactly, and in fact the probability that U $ V has leading digit 1 is always strictly less than log,, 2. 16. [HA&%] (P. Diaconis.) Let PO(~) be 0 or 1 for each n, and define probabilities P,+l(n) by repeated averaging, as in (9). Show that if lim,,, PI(~) does not exist, neither does lim n+ocI P,(n) for any m. [Hint: Prove that a, + 0 whenever we have (al f . . + a,)/n + 0 and an+1 5 a, + M/n, for some fixed constant M > 0.1 b 17. [HM.Ei] (R. L. Duncan.) Another way to define the value of Pr(S(n)) is to evaluate the quantity lim,+,((Cs(kj and llkln l/lc)/H,); it can be shown that this harmonic probability exists and is equal to Pr(S(n)), whenever the latter exists according to Definition 3.5A. Prove that the harmonic probability of the statement (log,, n) mod 1 < r exists and equals r. (Thus, initial digits of integers exactly satisfy the logarithmic law in this sense.) b 18. [HM30] Let P(S) be any real-valued function defined on sets S of positive integers, but not necessarily on all such sets, satisfying the following rather weak axioms: i) If P(S) and P(T) are defined and S n T = 0, then P(S u T) = P(S) + P(T). ii) If P(S) is defined, then P(S + 1) = P(S), where S $1 = {n f 1 1 n E S}. iii) If P(S) is defined, then P(2S) = $P(S), where 2S = { 2n 1 n E S}. iv) If S is the set of all positive integers, then P(S) = 1. v) If P(S) is defined, then P(S) 2 0. Assume furthermore that P(La) is defined for all positive integers a, where L, is the set of all integers whose decimal representation begins with a: L, = {n 1 10 ~ 2 n < lO (u + 1) for some integer m }. (In this definition, m may be negative; for example, 1 is an element of Llo, but not of L11.) Prove that P(L,) = log,,(l + l/a) for all integers a 2 1.