Photo web hosting - 42.2 ACCURACY OF FLOATING POINT ARITHMETIC 213 Round
42.2 ACCURACY OF FLOATING POINT ARITHMETIC 213 Round numbers are always false. -SAMUEL JOHNSON (1750) I shall speak in round numbers, not absolutely accurate, yet not so wide from truth as to vary the result materially. -THOMAS JEFFERSON (1824) 19. [,%$I What is the running time for the FADD subroutine in Program A, in terms of relevant characteristics of the data? What is the maximum running time, over all inputs that do not cause overflow or underflow? 4.2.2. Accuracy of Floating Point Arithmetic Floating point computation is by nature inexact, and it is not difficult to misuse it so that the computed answers consist almost entirely of noise. One of the principal problems of numerical analysis is to determine how accurate the results of certain numerical methods will be. A credibility-gap problem is involved here: we don t know how much of the computer s answers to believe. Novice computer users solve this problem by implicitly trusting in the computer as an infallible authority; they tend to believe that all digits of a printed answer are significant. Disillusioned computer users have just the opposite approach, they are constantly afraid that their answers are almost meaningless. Many a serious mathematician has attempted to give rigorous analyses of a sequence of floating point operations, but has found the task to be so formidable that he has tried to content himself with plausibility arguments instead. A thorough examination of error analysis techniques is, of course, beyond the scope of this book, but in this section we shall study some of the characteristics of floating point arithmetic errors. Our goal is to discover how to perform floating point arithmetic in such a way that reasonable analyses of error propagation are facilitated as much as possible. A rough (but reasonably useful) way to express the behavior of floating point arithmetic can be based on the concept of significant figures or relative error. If we are representing an exact real number II: inside a computer by using the approximation 2 = ~(1 + E), the quantity E = (? -X)/X is called the relative error of approximation. Roughly speaking, the operations of floating point multiplication and division do not magnify the relative error by very much; but floating point subtraction of nearly equal quantities (and floating point addition, u $ 21, where u is nearly equal to -V) can very greatly increase the relative error. So we have a general rule of thumb, that a substantial loss of accuracy is expected from such additions and subtractions, but not from multiplications and divisions. On the other hand, the situation is somewhat paradoxical and needs to be understood properly, since bad additions and subtractions are performed with perfect accuracy! (See exercise 25.)