Nash - Compact Numerical Methods for Computers (523163), страница 4
Текст из файла (страница 4)
Then if therepresentation of q + (R – 1) is greater than that of q, the machine we are usingrounds, otherwise it chops or truncates the results of arithmetic operations.The number of radix digits t is now easily found as the smallest integer suchthatRt + 1is represented identically to Rt. Thus the machine precision is given aseps = R1-t = R-(t-1).(1.9)In the example, R = 10, t = 4, soR-3 = 0·001.Thus1 + 0·00l = 1·001 > 1but 1 + 0·0009 is, on a machine which truncates, represented as 1.In all of the previous discussion concerning the computation of the machineprecision it is important that the representation of numbers be that in the8Compact numerical methods for computersmemory, not in the working registers where extra digits may be carried.
On aHewlett-Packard 9830, for instance, it was necessary when determining theso-called ‘split precision’ to store numbers specifically in array elements to forcethe appropriate truncation.The above discussion has assumed a model of floating-point arithmetic which maybe termed an additive form in that powers of the radix are added together and theentire sum multiplied by some power of the radix (the exponent) to provide the finalquantity representing the desired real number. This representation may or may notbe exact. For example, the fraction cannot be exactly represented in additive binary(radix 2) floating-point arithmetic. While there are other models of floating-pointarithmetic, the additive form is the most common, and is used in the IEEE binaryand radix-free floating-point arithmetic standards.
(The March, 1981, issue of IEEEComputer magazine, volume 3, number 4, pages 51-86 contains a lucid description ofthe binary standard and its motivations.)If we are concerned with having absolute upper and lower bounds on computedquantities, interval arithmetic is possible, but not commonly supported by programming languages (e.g. Pascal SC (Kulisch 1987)). Despite the obvious importance ofassured bounds on results, the perceived costs of using interval arithmetic havelargely prevented its widespread use.The development of standards for floating-point arithmetic has the great benefitthat results of similar calculations on different machinery should be the same.Furthermore, manufacturers have been prompted to develop hardware implementations of these standards, notably the Intel 80 x 87 family and the Motorola 68881of circuit devices.
Hewlett-- Packard implemented a decimal version of the IEEE 858standard in their HP 71B calculator.Despite such developments, there continues to be much confusion and misinformation concerning floating-point arithmetic. Because an additive decimal form ofarithmetic can represent fractions such as exactly, and in general avoid inputoutput conversion errors, developers of software products using such arithmetic(usually in binary coded decimal or BCD form) have been known to claim that it has'no round-off error', which is patently false. I personally prefer decimal arithmetic, inthat data entered into a calculation can generally be represented exactly, so that adisplay of the stored raw data reproduces the input familiar to the user. Nevertheless,the differences between good implementations of floating-point arithmetic, whetherbinary or decimal, are rarely substantive.While the subject of machine arithmetic is still warm, note that the mean of twonumbers may be calculated to be smaller or greater than either! An example infour-figure decimal arithmetic will serve as an illustration of this.aba+b(a + b) /2ExactRoundedTruncated50085007100155007·5500850071002 * 10501·0 * 10= 5010500850071001 * 10500·5 * 10= 500.5A starting point9That this can and does occur should be kept in mind whenever averages arecomputed.
For instance, the calculations are quite stable if performed as(a + b)/2 = 5000+[(a – 5000) + (b – 5000)]/2.Taking account of every eventuality of this sort is nevertheless extremely tedious.Another annoying characteristic of small machines is the frequent absence ofextended precision, also referred to as double precision, in which extra radix digitsare made available for calculations. This permits the user to carry out arithmeticoperations such as accumulation, especially of inner products of vectors, andaveraging with less likelihood of catastrophic errors. On equipment which functions with number representations similar to the IBM/360 systems, that is, sixhexadecimal (R = 16) digits in the mantissa of each number, many programmersuse the so-called ‘double precision’ routinely.
Actually t = 14, which is not doublesix. In most of the calculations that I have been asked to perform, I have notfound such a sledgehammer policy necessary, though the use of this feature inappropriate situations is extremely valuable. The fact that it does not exist onmost small computers has therefore coloured much of the development whichfollows.Finally, since the manufacturers’ basic software has been put in question above,the user may also wonder about their various application programs and packages.While there are undoubtedly some ‘good’ programs, my own experience is that thequality of such software is very mixed. Badly written and poorly documentedprograms may take longer to learn and understand than a satisfactory homegrownproduct takes to code and debug.
A major fault with many software products is thatthey lack references to the literature and documentation of their pedigree andauthorship. Discussion of performance and reliability tests may be restricted to verysimple examples. Without such information, it may be next to impossible todetermine the methods used or the level of understanding of the programmer of thetask to be carried out, so that the user is unable to judge the quality of the product.Some developers of mathematical and statistical software are beginning to recognisethe importance of background documentation, and their efforts will hopefully berewarded with sales.1.3. SOURCES OF PROGRAMSWhen the first edition of this book was prepared, there were relatively few sources ofmathematical software in general, and in essence none (apart from a few manufacturers’ offerings) for users of small computers. This situation has changed remarkably, with some thousands of suppliers.
Source codes of numerical methods,however, are less widely available, yet many readers of this book may wish toconduct a search for a suitable program already coded in the programming languageto be used before undertaking to use one of the algorithms given later.How should such a search be conducted? I would proceed as follows.First, if FORTRAN is the programming language, I would look to the majorcollections of mathematical software in the Collected Algorithms of the Association forComputing Machinery (ACM).
This collection, abbreviated as CALGO, is comprised10Compact numerical methods for computersof all the programs published in the Communications of the ACM (up to 1975) andthe ACM Transactions on Mathematical Software (since 1975). Other importantcollections are EISPACK, UNPACK, FUNPACK and MINPACK, which concern algebraiceigenproblems, linear equations, special functions and nonlinear least squares minimisation problems. These and other packages are, at time of writing, available fromthe Mathematics and Computer Sciences Division of the Argonne National Laboratory of the US Department of Energy. For those users fortunate enough to haveaccess to academic and governmental electronic mail networks, an index of softwareavailable can be obtained by sending the messageSEND INDEXto the pseudo-user NETLIB at node ANL-MCS on the ARPA network (Dongarra andGrosse 1987).
The software itself may be obtained by a similar mechanism.Suppliers such as the Numerical Algorithms Group (NAG), International Mathematical and Statistical Libraries (IMSL), C Abaci, and others, have packagesdesigned for users of various computers and compilers, but provide linkable objectcode rather than the FORTRAN source. C Abaci, in particular, allows users of theScientific Desk to also operate the software within what is termed a ‘problem solvingenvironment’ which avoids the need for programming.For languages other than FORTRAN, less software is available.
Several collections ofprograms and procedures have been published as books, some with accompanyingdiskettes, but once again, the background and true authorship may be lacking. Thenumber of truly awful examples of badly chosen, badly coded algorithms is alarming,and my own list of these too long to include here.Several sources I consider worth looking at are the following.Maindonald (1984)—A fairly comprehensive collection of programs in BASIC (for a Digital Equipment Corporation VAX computer) are presented covering linear estimation,statistical distributions and pseudo-random numbers.Nash and Walker-Smith (1987)—Source codes in BASIC are given for six nonlinear minimisation methods and alarge selection of examples. The algorithms correspond, by and large, to thosepresented later in this book.LEQBO5 (Nash 1984b, 1985)—This single ‘program’ module (actually there are three starting points forexecution) was conceived as a joke to show how small a linear algebra packagecould be made.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
