4.2.2 ACCURACY OF FLOATING POINT ARITHMETIC 217 As (Professional web hosting)
4.2.2 ACCURACY OF FLOATING POINT ARITHMETIC 217 As an example of typical error-estimation procedures, let us consider the associative law for multiplication. Exercise 3 shows that (U @ U) @ w is not in general equal to u @ (V @ w); but the situation in this case is much better than it was with respect to the associative law of addition (1) and the distributive law (12). In fact, we have (u El v) @I w = ((UW + h,) @ w = UN1 + a1 + (521, uLB(v @WI = u@((vw)P+63))= uvw(l+63)(1+~4), for some 61, 62, Ss, 64, provided that no exponent underflow or overflow occurs, where I& < $b -p for each j. Hence (u @ v) @ w cl+ m1+ 62) u @(v 020) = (1+ 63)(1+ 64) = l+ 6T where 16) < 2PP/(l -&bl-q2. (19) The number bl-p occurs so often in such analyses, it has been given a special name, one ulp, meaning one unit in the last place of the fraction part. Floating point operations are correct to within half an ulp, and the calculation of uvw by two floating point multiplications will be correct within about one ulp (ignoring second-order terms). Hence the associative law for multiplication holds to within about two ulps of relative error. We have shown that (u @ v) @ w is approximately equal to u @ (v @ w), except when exponent overflow or underflow is a problem. It is worthwhile to study this intuitive idea of being approximately equal in more detail; can we make such a statement more precise in a reasonable way? A programmer using floating point arithmetic almost never wants to test if two computed values are exactly equal to each other (or at least he hardly ever should try to do so), because this is an extremely improbable occurrence. For example, if a recurrence relation x,+1 = f(d is being used, where the theory in some textbook says that x, approaches a limit as n + 00, it is usually a mistake to wait until x,+1 = xn for some n, since the sequence zn might be periodic with a longer period due to the rounding of intermediate results. The proper procedure is to wait until Ix,+1 -x, 1 < 6, for some suitably chosen number 6; but since we don t necessarily know the order of magnitude of x, in advance, it is even better to wait until I%+1 -%I I +kl; (20) now t is a number that is much easier to select. This relation (20) is another way of saying that x,+1 and x, are approximately equal; and our discussion