568 ANSWERS TO EXERCISES 4.1 of integers that (Geocities web hosting)
568 ANSWERS TO EXERCISES 4.1 of integers that can be expressed as {ti b + al , . . . , t, b + a,} in the above manner for m different sequences (ai, . . , 07), summed over all choices of m different sequences (al,…,&). Given m different sequences (a?), . . , a$ )) for 1 2 1 2 m, the number of such sets is k,-i({(si f j -a! ))/b 1 1 5 i 5 r, 1 5 1 5 m}). Thus there is a collection of sets T(S) such that k(S)= c CTLl(T), where each CT is an integer. Furthermore if T E T(S), its elements are near those of S; we have min T 2 (min S - max D)/b and max T 5 (max S + b -1 - min D)/b. Thus we obtain simultaneous recurrence relations for the sequences (km(S)), where S runs through the nonempty integer subsets of [I, u + 11, in the notation of exercise 19. Since k, = k,(S) for any one-element set S, the sequence (kn) appears these recurrences. The coefficients CT can be computed from the first few values of kn(S), so we can obtain a system of equations defining the generating functions ks(z) = C k,(S),? = Wll I 1) + z CTET(S) w-4. For example, when D = {-l,O, 3) and b = 3 we have 1 = -4 and 2~ = 4, so the relevant sets S are {0}, (0, l}, (-1, l}, and (-1, 0, l}. The corresponding sequences for n 5 3 are (1,3,8,21), (0, 1,3,8), (O,O, 1,4), and (O,O, 0,O); so we obtain ko(z) = 1+ z(3ko(z) -kOl(Z)), koz(z) = z(ko1(z)+ koz(z)), kOl(Z) = zko(z), lOlZ(Z) = 0, and k(z) = l/(1 -32 + z ). In this case k, = Fznt2 and ,k,({O, 2)) = Fznel - I. SECTION 4.2.1 1. iV = (62,+.60 22 52 00); h = (37, +.lO 54 50 00). Note that 10h would be (38, +.Ol 05 45 00). 2. bE-q(l _ b-p), b–q-P; b-(1 -b-p), b-9-1, 3. When e does not have its smallest value, the most significant one bit (which appears in all such normalized numbers) need not appear in the computer word. 4. (51, +.10209877); (50, +.12346000); (53, -j-.99999999). The third answer would be (54, +.lOOOOOOO) if the first operand had been (45, –.50000000). 5. If x -y and m is an integer then mb + .r - mb + y. Furthermore x -y implies x/b -y/b, by considering all possible cases. Another crucial property is that x and y will round to the same integer, whenever x -y. Now if bApp2 F,, # fV we must have ( bp-t2 fV) mod b # 0; hence the transformation leaves fV unchanged unless e, -e, > 2. Since u was normalized, it is nonzero and IfiL + fvl > b- -b-2 2 b-2: th e 1ead m g nonzero digit of fU + fv must be at most two places to the right of the radix point, and the rounding operation will convert bpf3(fu f f,,) to an integer, where j 5 1. The proof will be complete if we can show that bp+j+ (fu + fv) -bpfjW1 (f,, + bppp2F,). By the previous paragraph, we have bp+ (f,, +f,,) -bp+ f,, + F, = bpf2(fu + bYpp2F,), which implies the desired result for allj 2 1. Note that, when b > 2 is even, such an integer F, always exists; but when b = 2 we require p+ 3 bits (let 2F, be an integer). When b is odd, an integer F, always exists except in the case of division, when a remainder of i b is possible.