c20-1 (779623)
Текст из файла
20.0 IntroductionYou can stop reading now. You are done with Numerical Recipes, as such. Thisfinal chapter is an idiosyncratic collection of “less-numerical recipes” which, for onereason or another, we have decided to include between the covers of an otherwisemore-numerically oriented book.
Authors of computer science texts, we’ve noticed,like to throw in a token numerical subject (usually quite a dull one — quadrature,for example). We find that we are not free of the reverse tendency.Our selection of material is not completely arbitrary. One topic, Gray codes, wasalready used in the construction of quasi-random sequences (§7.7), and here needsonly some additional explication.
Two other topics, on diagnosing a computer’sfloating-point parameters, and on arbitrary precision arithmetic, give additionalinsight into the machinery behind the casual assumption that computers are usefulfor doing things with numbers (as opposed to bits or characters). The latter of thesetopics also shows a very different use for Chapter 12’s fast Fourier transform.The three other topics (checksums, Huffman and arithmetic coding) involvedifferent aspects of data coding, compression, and validation.
If you handle a largeamount of data — numerical data, even — then a passing familiarity with thesesubjects might at some point come in handy. In §13.6, for example, we alreadyencountered a good use for Huffman coding.But again, you don’t have to read this chapter. (And you should learn aboutquadrature from Chapters 4 and 16, not from a computer science text!)20.1 Diagnosing Machine ParametersA convenient fiction is that a computer’s floating-point arithmetic is “accurateenough.” If you believe this fiction, then numerical analysis becomes a very cleansubject.
Roundoff error disappears from view; many finite algorithms become“exact”; only docile truncation error (§1.3) stands between you and a perfectcalculation. Sounds rather naive, doesn’t it?Yes, it is naive. Notwithstanding, it is a fiction necessarily adopted throughoutmost of this book.
To do a good job of answering the question of how roundoff error889Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Chapter 20.
Less-NumericalAlgorithms890Chapter 20.Less-Numerical AlgorithmsSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).propagates, or can be bounded, for every algorithm that we have discussed would beimpractical. In fact, it would not be possible: Rigorous analysis of many practicalalgorithms has never been made, by us or anyone.Proper numerical analysts cringe when they hear a user say, “I was gettingroundoff errors with single precision, so I switched to double.” The actual meaningis, “for this particular algorithm, and my particular data, double precision seemedable to restore my erroneous belief in the ‘convenient fiction’.” We admit that mostof the mentions of precision or roundoff in Numerical Recipes are only slightly morequantitative in character.
That comes along with our trying to be “practical.”It is important to know what the limitations of your machine’s floating-pointarithmetic actually are — the more so when your treatment of floating-point roundofferror is going to be intuitive, experimental, or casual. Methods for determininguseful floating-point parameters experimentally have been developed by Cody [1],Malcolm [2], and others, and are embodied in the routine machar, below, whichfollows Cody’s implementation.All of machar’s arguments are returned values. Here is what they mean:• ibeta (called B in §1.3) is the radix in which numbers are represented,almost always 2, but occasionally 16, or even 10.• it is the number of base-ibeta digits in the floating-point mantissa M(see Figure 1.3.1).• machep is the exponent of the smallest (most negative) power of ibetathat, added to 1.0, gives something different from 1.0.• eps is the floating-point number ibetamachep, loosely referred to as the“floating-point precision.”• negep is the exponent of the smallest power of ibeta that, subtractedfrom 1.0, gives something different from 1.0.• epsneg is ibetanegep, another way of defining floating-point precision.Not infrequently epsneg is 0.5 times eps; occasionally eps and epsnegare equal.• iexp is the number of bits in the exponent (including its sign or bias).• minexp is the smallest (most negative) power of ibeta consistent withthere being no leading zeros in the mantissa.• xmin is the floating-point number ibetaminexp, generally the smallest(in magnitude) useable floating value.• maxexp is the smallest (positive) power of ibeta that causes overflow.• xmax is (1−epsneg)×ibetamaxexp, generally the largest (in magnitude)useable floating value.• irnd returns a code in the range 0 .
. . 5, giving information on what kind ofrounding is done in addition, and on how underflow is handled. See below.• ngrd is the number of “guard digits” used when truncating the product oftwo mantissas to fit the representation.There is a lot of subtlety in a program like machar, whose purpose is to ferretout machine properties that are supposed to be transparent to the user. Further, it mustdo so avoiding error conditions, like overflow and underflow, that might interruptits execution. In some cases the program is able to do this only by recognizingcertain characteristics of “standard” representations.
For example, it recognizesthe IEEE standard representation [3] by its rounding behavior, and assumes certainfeatures of its exponent representation as a consequence. We refer you to [1] and89120.1 Diagnosing Machine ParametersSample Results Returned by machartypical IEEE-compliant machineDEC VAXsingledoublesingleibeta222it245324machep−23−52−24eps1.19 × 10−72.22 × 10−165.96 × 10−8negep−24−53−24epsneg5.96 × 10−81.11 × 10−165.96 × 10−8iexp8118minexp−126−1022−128xmin1.18 × 10−382.23 × 10−3082.94 × 10−39maxexp1281024127xmax3.40 × 10381.79 × 103081.70 × 1038irnd551ngrd000references therein for details. Be aware that machar can give incorrect results onsome nonstandard machines.The parameter irnd needs some additional explanation.
In the IEEE standard,bit patterns correspond to exact, “representable” numbers. The specified methodfor rounding an addition is to add two representable numbers “exactly,” and thenround the sum to the closest representable number. If the sum is precisely halfwaybetween two representable numbers, it should be rounded to the even one (low-orderbit zero). The same behavior should hold for all the other arithmetic operations,that is, they should be done in a manner equivalent to infinite precision, and thenrounded to the closest representable number.If irnd returns 2 or 5, then your computer is compliant with this standard. If itreturns 1 or 4, then it is doing some kind of rounding, but not the IEEE standard. Ifirnd returns 0 or 3, then it is truncating the result, not rounding it — not desirable.The other issue addressed by irnd concerns underflow.
If a floating value isless than xmin, many computers underflow its value to zero. Values irnd = 0, 1,or 2 indicate this behavior. The IEEE standard specifies a more graceful kind ofunderflow: As a value becomes smaller than xmin, its exponent is frozen at thesmallest allowed value, while its mantissa is decreased, acquiring leading zeros and“gracefully” losing precision. This is indicated by irnd = 3, 4, or 5.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).precision892Chapter 20.Less-Numerical Algorithms#include <math.h>#define CONV(i) ((float)(i))Change float to double here and in declarations below to find double precision parameters.one=CONV(1);two=one+one;zero=one-one;a=one;Determine ibeta and beta by the method of M.do {Malcolm.a += a;temp=a+one;temp1=temp-a;} while (temp1-one == zero);b=one;do {b += b;temp=a+b;itemp=(int)(temp-a);} while (itemp == 0);*ibeta=itemp;beta=CONV(*ibeta);*it=0;Determine it and irnd.b=one;do {++(*it);b *= beta;temp=b+one;temp1=temp-b;} while (temp1-one == zero);*irnd=0;betah=beta/two;temp=a+betah;if (temp-a != zero) *irnd=1;tempa=a+beta;temp=tempa+betah;if (*irnd == 0 && temp-tempa != zero) *irnd=2;*negep=(*it)+3;Determine negep and epsneg.betain=one/beta;a=one;for (i=1;i<=(*negep);i++) a *= betain;b=a;for (;;) {temp=one-a;if (temp-one != zero) break;a *= beta;--(*negep);}*negep = -(*negep);*epsneg=a;*machep = -(*it)-3;Determine machep and eps.a=b;Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).void machar(int *ibeta, int *it, int *irnd, int *ngrd, int *machep, int *negep,int *iexp, int *minexp, int *maxexp, float *eps, float *epsneg,float *xmin, float *xmax)Determines and returns machine-specific parameters affecting floating-point arithmetic.
Returned values include ibeta, the floating-point radix; it, the number of base-ibeta digits inthe floating-point mantissa; eps, the smallest positive number that, added to 1.0, is not equalto 1.0; epsneg, the smallest positive number that, subtracted from 1.0, is not equal to 1.0;xmin, the smallest representable positive number; and xmax, the largest representable positivenumber. See text for description of other returned parameters.{int i,itemp,iz,j,k,mx,nxres;float a,b,beta,betah,betain,one,t,temp,temp1,tempa,two,y,z,zero;20.1 Diagnosing Machine Parameters893Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
