Web hosting ratings - 4.2.4 DISTRIBUTION OF FLOATING POINT NUMBERS 239 Table
4.2.4 DISTRIBUTION OF FLOATING POINT NUMBERS 239 Table 2 EMPIRICAL DATA FOR NORMALIZATION AFTER ADDITION b=2 b= 10 b= 16 b = 64 Shift right 1 0.20 0.07 0.06 0.03 No shift 0.59 0.80 0.82 0.87 Shift left 1 0.07 0.08 0.07 0.06 Shift left 2 0.03 0.02 0.01 0.01 Shift left 3 0.02 0.00 0.01 0.00 Shift left 4 0.02 0.01 0.00 0.01 Shift left >4 0.06 0.02 0.02 0.02 When u and v have the same sign and are normalized, then u + v either requires one shift to the right (for fraction overflow), or no normalization shifts whatever. When u and v have opposite signs, we have zero or more left shifts during the normalization. Table 2 gives the observed number of shifts required; the last line of that table includes all cases where the result was zero. The average number of left shifts per normalization was about 0.9 when b = 2; about 0.2 when b = 10 or 16; and about 0.1 when b = 64. B. The fraction parts. Further analysis of floating point routines can be based on the statistical distribution of the fraction parts of randomly chosen normalized floating point numbers. In this case the facts are quite surprising, and there is an interesting theory that accounts for the unusual phenomena that are observed. For convenience let us temporarily assume that we are dealing with floating decimal (i.e., radix 10) arithmetic; modifications of the following discussion to any other positive integer base b will be very straightforward. Suppose we are given a random positive normalized number (e, f) = 10e . f. Since f is normalized, we know that its leading digit is 1, 2, 3, 4, 5, 6, 7, 8, or 9, and it seems natural to assume that each of these nine possible leading digits will occur about one-ninth of the time. But, in fact, the behavior in practice is quite different. For example, the leading digit tends to be equal to 1 over 30 percent of the time! One way to test the assertion just made is to take a table of physical constants (e.g., the speed of light, the acceleration of gravity) from some standard reference. If we look at the Handbook of Mathematical Functions (U.S. Dept of Commerce, 1964), for example, we find that 8 of the 28 different physical constants given in Table 2.3, roughly 29 percent, have leading digit equal to 1. The decimal values of n! for 1 5 n 5 100 include exactly 30 entries beginning with 1; so do the decimal values of 2n and of F,, for 1 5 n 5 100. We might also try looking at census reports, or a Farmer s Almanack (but not a telephone directory). In the days before pocket calculators, the pages in well-used tables of loga- rithms tended to get quite dirty in the front, while the last pages stayed relatively clean and neat. This phenomenon was apparently first mentioned in print by the American astronomer Simon Newcomb [Amer. J. Math. 4 (1881), 39-401, who