f20-0

Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).Chapter 20. Less-Numerical Algorithms 20.0 Introduction Youcanstopreadingnow. Youaredonewith NumericalRecipes ,assuch. This finalchapterisanidiosyncraticcollectionof“ less-numericalrecipes”which,forone reason or another, we have decided to include between the covers of an otherwisemore-numericallyorientedbook. Authorsof computerscience texts, we’venoticed, liketothrowinatokennumericalsubject(usuallyquiteadullone—quadrature,for example). We find that we are not free of the reverse tendency. Ourselectionofmaterialisnotcompletelyarbitrary. Onetopic,Graycodes,was already used in the construction of quasi-random sequences ( §7.7), and here needs only some additional explication. Two other topics, on diagnosing a computer’s floating-point parameters, and on arbitrary precision arithmetic, give additional insight into the machinery behind the casual assumption that computers are usefulfor doingthings with numbers(as opposedto bits or characters). The latter of these topics also shows a verydifferent use for Chapter 12’s fast Fourier transform. The three other topics (checksums, Huffman and arithmetic coding) involve different aspects of data coding, compression, and validation. If you handle a large amount of data — numerical data, even — then a passing familiarity with these subjects might at some point come in handy. In §13.6, for example, we already encountered a good use for Huffman coding. But again, you don’t have to read this chapter. (And you should learn about quadrature from Chapters 4 and 16, not from a computer science text!) 20.1 Diagnosing Machine Parameters A convenient fiction is that a computer’s floating-point arithmetic is “accurate enough.” If you believe this fiction, then numerical analysis becomes a very clean subject. Roundoff error disappears from view; many finite algorithms become “exact”; only docile truncation error ( §1.2) stands between you and a perfect calculation. Sounds rather naive, doesn’t it? Yes, it is naive. Notwithstanding,it is a fiction necessarily adoptedthroughout mostofthisbook. Todoagoodjobofansweringthequestionofhowroundofferror 881