Scientific Computing with PCs John C. Nash Faculty of Administration University of Ottawa Mary M. Nash Nash Information Services Inc. ISBN: 0 88769 008 4 Copyright © 1984, 1993 J C Nash and M M Nash This book is available from several Internet servers by anonymous FTP. It is NOT free to use, though the file SCPCDOC.PS contains the Preface, Contents and an example chapter that you may freely print and use. If you decide to use the text of the book, there is a $10 / copy licence payable to Nash Information Services Inc. 1975 Bel-Air Drive, Ottawa, Ontario, K2C 0X1, Canada Fax: (613) 225 6553 Email contacts: [email protected], [email protected] This file formatted on 29 November 1997 i ii Copyright©1984,1994 JC&MM Nash SCIENTIFICCOMPUTINGWITHPCs NashInformationServicesInc.,1975BelAirDrive,Ottawa,ONK2C0X1Canada Copyfor:Dr. Dobb’s Journal Preface Thisbooktells"whatto","whyto"and"whento"usepersonalcomputers(PCs)forcarryingoutscientific computing tasks. There are many books that purport to tell users how to operate particular software packagesortosetupandmaintaintheirpersonalcomputerhardware.These"howto"volumeshavetheir proper role and utility. Our goal is different: we aim to present ideas about the management decisions involved in using PCs for scientific and technical computing. The audience for this book is any scientist, engineer, statistician, economist, or similar worker who is considering using a personal computer for all or part of his or her technical work. The ideas we present can be used at the individual or group level. Being ideas about the management of resources, they are keptsimpletotheextentthatreaderswillthink"Iknowthat."Westress,however,thatitistheday-to-day practiceofmanagementideasthatcounts;theoreticalknowledgeislikeasmokealarmwithoutabattery. There are three themes to this book: • Deciding what is or is not reasonable to attempt in the way of scientific computing with a PC; • Learning about and finding software to carry out our tasks with a minimum of fuss; • Choosing the tools to match the task to keep costs low. ByPCwewillmeananycomputersystemthatismanaged,usedandmaintainedbyasingleperson.The typicalexamplesare the relativesanddescendantsof theoriginalIBMPC andtheAppleMacintosh, but other machines and workstations have similar properties. Workstation networks and mainframes with systemsupportstaffhavequitedifferentmanagementstrategies.Portablecomputersusedwithsuchlarger systemsare,however,verylikelytobeusedinawaythatrequirestheusertoexercisemanagementskills. Our examples use mainly MS-DOS PCs since these are the most common. The reader will notice some repetition of ideas we feel important; we also have tried to keep sections of the book self-contained. ThedistributionmechanismforthisbookisanexperimentinanewformofpublishingusingtheInternet. We did not intend this to be the case. Unfortunately the publisher who commissioned the book as a venture into a new subject area decided to retreat in the face of recessionary pressures after we had submittedatypesetmanuscript.Interestfromotherpublishersdidnottransformitselfintoacontract.Our responsehasbeentopaytohavetheworkprofessionallyreviewed—asagoodpublishershould—and to then edit and produce the work in a form that users can print out for their own use. The current work has been formatted to reduce the number of pages from about 300 to about 200 by choosingmarginsthatusemoreofthepageareaontraditionalletter-sizepaper.WebelievethatA4paper users will find that pages fit this size also. Your comments are welcome. John & Mary Nash, Ottawa, September 1994 0:PREFACEANDCONTENTS iii Contents Part I: Panorama 4.8 Input/output problems — bugs and glitches 4.9 Debugging and trouble-shooting Chapter 1: IntroductionandPurpose—How 4.10 Precision problems Scientific Problems are Solved 4.11 Size problems 4.12 Utilities and support 1.1 History and goals 4.13 Summary 1.2 Non-goals 1.3 The scientific method and our Chapter 5: File management audience 1.4 Computer configurations of interest 5.1 File creation and naming 1.5 Computing styles 5.2 Types and distributions of files 5.3 Cataloguing and organizing files Chapter 2: Data processing capabilities of 5.4 Backup PCs 5.5 Archiving 5.6 Version control 2.1 Non-mathematical data processing 5.7 Loss versus security related to calculation 2.2 Communications — Access to remote Chapter 6: Programming Aids and Practices data 2.3 Automated data collection 6.1 Programmingtoolsandenvironments 2.4 Input, output, edit, and selection 6.2 Cross-reference listing and data 2.5 Scientific text processing dictionary 2.6 Macro-editors and data converters 6.3 Flowchart or other algorithmic 2.7 Graphics description 2.8 Report writers 6.4 Structure and modularity 2.9 Programming and program 6.5 Sub-programs — data flow development 6.6 Programmer practices 2.10 Administration of research Chapter 7: Size Difficulties Chapter 3: ComputationalcapabilitiesofPCs 7.1 Determining memory and data 3.1 Good news storage limits 3.2 Application problems 7.2 Choice or adjustment of data 3.3 Component computational problems structures 3.4 Component symbolic problems 7.3 Usage map 3.5 Getting things to work 7.4 Restructuring 7.5 Reprogramming Part II: Computing environments 7.6 Chaining 7.7 Change of method Chapter 4: Will a PC suffice? 7.8 Data storage mechanisms for special matrices 4.1 Hardware 4.2 Software Chapter 8: Timing Considerations 4.3 Interfacing,communicationsanddata sharing 8.1 Profile of a program 4.4 Peripherals 8.2 Substitution of key code 4.5 Operational considerations 8.3 Special hardware 4.6 Issues to be addressed 8.4 Disk access times 4.7 Programming effectively 8.5 Time/accuracy and other trade-off 4.8 The software development decisions environment 8.6 Timing tools iv Copyright©1984,1994 JC&MM Nash SCIENTIFICCOMPUTINGWITHPCs NashInformationServicesInc.,1975BelAirDrive,Ottawa,ONK2C0X1Canada Copyfor:Dr. Dobb’s Journal Chapter 9: Debugging Chapter 13: Problem formulation 9.1 Using output wisely 13.1 Importance of correct formulation 9.2 Built-in debugging tools 13.2 Mathematical versus real-world 9.3 Listings and listing tools problems 9.4 Sub-tests 13.3 Using a standard approach 9.5 Fulltests—robustnessofcodetobad 13.4 Help from others input 13.5 Sources of software 9.6 Full tests — sample and test data 13.6 Verifying results 9.7 Resilience to I/O failure and disk 13.7 Usingknowntechniquesonunknown problems problems 9.8 Tests of language translators Part IV: Examples Chapter 10: Utilities — a desirable set Chapter 14: The Internal Rate of Return 10.1 Editors Problem 10.2 File view, move, copy, archive and backup 14.1 Problem statement 10.3 File display, conversion and print 14.2 Formulations 10.4 File comparison 14.3 Methods and Algorithms 10.5 Directories and catalogs 14.4 Programs or Packages 10.6 Fixup programs 14.5 Some solutions 10.7 Sorting 14.6 Assessment Chapter 11: Looking after the Baby - Chapter 15: Data Fitting and Modelling HardwareandOperatingPractice 15.1 Problem Statement 11.1 Cleanliness and a decent physical 15.2 Formulations environment 15.3 Methods and Algorithms 11.2 Bad habits — smoke, sticky fingers, 15.4 Programs or Packages children 15.5 Some solutions 11.3 Magnetic disks and their care 15.6 Assessment 11.4 Tapes, CDs and other storage media 11.5 Power considerations Chapter 16: Trajectories of Spacecraft 11.6 Interference and radio frequency shielding 16.1 Problem statement 11.7 Servicing and spare parts 16.2 Formulations 11.8 Configuration maintenance 16.3 Methods and Algorithms 16.4 Programs or Packages Part III: The problem and its solution 16.5 Some solutions method 16.6 Assessment Chapter 12: Steps in Problem Solving Chapter 17: Simulating a Hiring Process 12.1 Problem formulation example 17.1 Problem Statement 12.2 Algorithm choice 17.2 Formulations 12.3 Algorithm implementation — 17.3 Methods and Algorithms programming 17.4 Programs or Packages 12.4 Documentation 17.5 Some solutions 12.5 Testing — data entry 17.6 Assessment 12.6 Testing — sub-programs 12.7 Testing — complete programs 12.8 Production runs 12.9 Modifications and improvements 0:PREFACEANDCONTENTS v Chapter 18: A Program Efficiency Study: the Chapter 20: Your Own Strategy for Scientific Cholesky Decomposition Computing on PCs 18.1 Purpose of the study 20.1 Identifying needs and wants 18.2 The programs and systems compared 20.2 Acquiring the right computing 18.3 Measuring the differences environments 18.4 Program sizes and compiler options 20.3 Tools and methods 18.5 Time differences from program 20.4 Add-ons, extras and flexibility alternatives 20.6 Personal Choice and Satisfaction 18.6 Compiler and arithmetic influences 18.7 Processor and configuration time Bibliography differences Figures and Tables Chapter 19: Case study: graphical tools for data analysis Index 19.1 Purpose of the study 19.2 Example data for analysis 19.3 Display characteristics 19.4 Choices of graphical tools 19.5 Displaying level and variability 19.6 Displaying relative measurements 19.7 Displaying patterns and outliers This book is made available in PostScript™ form via Internet FTP servers. The copyright to this work belongstotheauthors.YoumaycopythePostScriptfilesforthisworkandprintoffthefileSCPCDOC.PS freely. If you print off the files of the book itself you then owe the authors a licence fee of $10. The book (and related materials) may be obtained by anonymous FTP from: MacNash.admin.uottawa.ca The full work is approximately 200 pages long and the PostScript files occupy about 4 megabytes of storage. vi Copyright©1984,1994 JC&MM Nash SCIENTIFICCOMPUTINGWITHPCs NashInformationServicesInc.,1975BelAirDrive,Ottawa,ONK2C0X1Canada Copyfor:Dr. Dobb’s Journal Trademarks The following table lists, as far as we could determine, the holders of various trademarks mentioned in this work. Trademark Holder Trademark(s) or Trade Name(s) Adobe Systems Inc. PostScript American Mathematical Society T X E Apple Computer Corporation Apple, Macintosh Aptech Systems Inc. GAUSS Borland International, Inc. BRIEF, dBase III, dBase IV, PARADOX, Turbo Basic, Turbo Pascal, Turbo C, Borland C, Turbo C++, Borland C++, Quattro, Quattro Pro C Ware Corporation SEE, DeSmet C, DeSmet ASM88 Conceptual Software Inc. DBMSCOPY Corel Corporation CorelDRAW, CorelPHOTO-PAINT Crescent Software Inc. GraphPak Data Description Inc. Data Desk Data Viz Inc MacLink Gazelle Systems OPTune Gibson Research Inc. SpinRite Hewlett-Packard Hewlett-Packard Intel Corporation Intel, 386 International Business Machines Inc. IBM, RS6000, OS/2 Lotus Development Corp. Lotus, 1-2-3 The MathWorks Inc. MATLAB Microsoft Corporation Excel, Microsoft, Quick C, MS-DOS, Windows, Quick BASIC, Visual BASIC Minitab Inc. MINITAB Motorola Motorola, 6800, 68000 Nash Information Services Inc. SnoopGuard NeXT Computer Inc. NeXT Numerical Algorithms Group Inc. NAG Scientific Endeavors Corp. GraphiC Stata Corporation Stata Sun Microsystems, Inc. SUN Soft Warehouse Inc. DERIVE, muMATH Strategy Plus Inc. EXECUSTAT Stac Electronics Inc. STACKER SYSTAT Inc. (now part of SPSS Inc.) SYSTAT, MYSTAT Travelling Software Inc. Laplink True BASIC Inc. True BASIC UNIX System Laboratories Inc. UNIX Waterloo Maple Software Maple Wolfram Research Mathematica WordPerfect Corporation WordPerfect Zilog Corporation Z80 1:INTRODUCTIONANDPURPOSE 1 Part I: Panorama To get a good idea of the lie of the land, one finds a convenient tree, hill or building and exploits the larger field of view gained by height. As a preliminary to the detailed study of the application of personal computers (PCs) to scientific computation, we will take such a panoramic view. First, a chapter on the aims (and non-aims) of this book, which concern the way in which scientific problems are solved and the role of computations in such solutions. Chapter 1 Introduction and Purpose: How Scientific Problems are Solved 1.1 Background 1.2 Goals 1.3 The scientific method and our audience 1.4 Computer configurations of interest 1.5 Computing styles ThisbookaimstohelpresearcherswhoarenotcomputerspecialiststousePCsprofitablyandefficiently. Itisespeciallyconcernedwiththestrategiesandtacticsthatenableuserstocarryouttheirscientificwork in all aspects — technical, administrative and educational — with the aid of PCs. We do not claim that PCsarethe"best"answerforscientificcomputationsbutpointoutthattheydeserveconsideration.Indeed our message is that there is no uniquely "best" approach to scientific problem solving, but that there are generally several options that will provide satisfactory results with modest expenditure of time and money. It is toward reasoned consideration of the PC option that we direct our energies here. 1.1 Background The PCs of this book are primarily those of the IBM PC family, with the Apple Macintosh also kept in mind.WewillusetheabbreviationPCtorefertomachinesofboththeIBMPC(thatis,MS-DOS)family and the Apple Macintosh. Because we have less familiarity with Atari and Commodore machines, there arefewreferencestothem.WorkstationsbasedontheUNIXoperatingsystem,suchasSUN,NeXT,IBM RS6000, certain Hewlett-Packard machines and many others, have not been used as examples, mainly becauseouruseofsuch machineshasbeenlimited.Theideaspresentedinthisbookcanneverthelessbe applied to such machines, particularly if the reader is the system manager. The software and manner of useofworkstationsis,inouropinion,qualitativelydifferentfromthatofPCsandMacintoshesinthatthe workstations are less independent machines than parts of larger networks. While many PCs are also connected in networks, the type of central support provided is more likely, we think, to be limited to 2 Copyright©1984,1994 JC&MM Nash SCIENTIFICCOMPUTINGWITHPCs NashInformationServicesInc.,1975BelAirDrive,Ottawa,ONK2C0X1Canada Copyfor:Dr. Dobb’s Journal non-scientific applications. Thus there is a qualitative difference between the PC world and the (UNIX) workstation world in the technical support provided to the user for scientific computations. We note that both IBM PC and Macintosh can be operated under variants of Unix, and that OS/2 is anotherchoiceofoperatingsystemforIBMPCusers.Aswewrite,MicrosoftisintroducingWindowsNT. We will mention such environments as appropriate, but they are not critical to our examples. The realities of present-day PCs are as interesting as the publicity that surrounds them. However, there is a lot less glamour to be found in the reality of PCs than in the advertising copy. This introduction presentstheauthors’ goalsin writingthisbook,suggeststhetypeofreaderwhowillfinditmostuseful, and declares several topics that will not be covered. We will caution that advertised products need to be evaluated carefully. New products may be able to serve us, but obstacles or restrictions mentioned in the fine print or omitted entirely may prevent easy resolutionofourproblems.Whileusersarenowlesslikelytoresorttodoingtheirownprogrammingthan a decade ago, there are still many computational problems that require such brute-force efforts. Furthermore,theexistenceofcommercialsoftwarethatsolvesonlyoneproblemisnotnecessarilyhelpful; it is difficult to justify spending hundreds of dollars to solve a problem that may be a small part of a larger task. Anannoyingaspectoftoday’srapidlydevelopingcomputerworld,atleastfromthepointofviewofthe computist — the person who must perform calculations — is the constant stream of statements, articles, lecturesandpapersthatdescribe"new,improved"hardwareorsoftware.Therealitiesoflifeintheworld of technical computation, be it in engineering, natural sciences, economics, statistics or business, are that funds are not available to acquire each new piece of apparently useful electronics or program code. Furthermore,thecost of learningandevaluating a singlenewproductishigh. Thepressuretobring out anewproductaheadofcompetitorsissuchthaterrorsareprobablypresentinthefirst(orsecondorthird or . . . ) models delivered. This leads to contradictory evaluations of products in the literature, forcing prospective users to spend much valuable time and effort to discover the true utility of the product for their own situation. There is, of course, pressure among the user’s own community to use the "latest and best." Salespeople, industry writers and futurists have successfully created a collective faith in the ongoing rapid change in computing. New products are supposedly obsoleteas soon as they are delivered. While we all like to be modernandup-to-date,muchofthepanicandhurrahisamyth.Thetruthisnolessinteresting,butdoes not have the glamour and air-brush artwork that should, in any event, be left for the cover of fashion magazines. We have studied computation and performed calculations for more than twenty-five years. In that time, many new and interesting devices have been brought to market. There have been substantial decreases intherealcostsofcomputing.In1968,wepaid$200(Canadian)forasecond-handMonroehand-cranked mechanical calculator. In 1980, we bought the Sharp PC 1211/Radio Shack Pocket Computer for $279 (Canadian). This machine was capable of quite sophisticated programs in BASIC and had a large repertoire of special functions. In 1992, a modest PC with 640K memory and floppy disk drives can be boughtforunder$500(Canadian)andaPC/ATwithfixeddiskforunder$1000.Clearly,thesearegreat advances,andtheMonroeisnowafondlyregardedantiquethatneverthelessstillfunctionsperfectly.In its time it fulfilled a need and was used to solve many problems similar to those still coming across our desk today. In turn, the other machines will serve their time before being replaced. In fact we disposed of our first generation personal computers late in 1991 after over 13 years of solid service. Theusefullifetimeofcomputerscontinuestobeseveralyears.Therearesoundbusinessandoperational reasons for this. One cannot consider equipment with a useful lifetime of less than five years as a good investment, though we may expect the uses of equipment to change over that lifetime. Similarly, manufacturerswishtoconvinceusthattheirproductsarethelastwordintechnology,butmusthavelong enough production runs to keep their costs to a minimum. Thus many "innovations" are cosmetic and 1:INTRODUCTIONANDPURPOSE 3 designed to respond to marketing pressures. Inthepracticeofcomputationthechangesobservedinthelasttwenty-fiveyearshavebeenquitegradual. Several commendable efforts have been made to produce quality mathematical software packages and libraries.Despitethesuccessofsomeoftheseeffortsandtheappearanceofseveralnewjournalsdedicated to specialized computation, there is still a vast body of very low quality programs in use that have been purchased, borrowed or stolen. These have frequently been installed without regard to the effects that a different computing environment may introduce into a calculated result. 1.2 Goals To the chagrin of developers of quality mathematical software, poorly designed programs will correctly solve more than 99% of the problems presented to them. The expense and effort of good program development is spent mostly to prevent disaster for a few cases in a million. This "insurance" aspect of qualitysoftwareisdifficulttoselltousers.Auserwhoishappywith,butignorantof,resultsfromapoor program is unlikely to change programs if it means, as it usually does, a considerable effort and cost. Knowledgeable staff are seldom available to help the scientific user in the implementation of programs to carry out calculations. Unlike programs to process data or control functions, the results of computational programs are rarely right or wrong absolutely. That is, success in obtaining reasonable results is not necessarily a sign that the calculation has been correctly performed. Worse, correct performance in a number of cases may only lead to a false sense of confidence in a program destined to give erroneous output in a future calculation. If this output is the basis of decisions — business investment,governmentpolicy,vehicledesignoraircraftnavigation—wehavetheseedsofcatastrophe. Withincreasingrelianceoncomputationsandsimulationsinallfieldsofhumanendeavor,thepossibility andlikelihoodofoccurrenceofdisasterslarge,andsmall,becauseofsoftwarefailure,areanunfortunate reality in all our lives. We address such topics in our related work on technological risks. One objective, then, of this book is the realistic evaluation of what may be accomplished with the computers that are commonly available to those of us who must perform calculations. The second concern is the choice of strategies and tactics to make the most of the capabilities while avoiding or overcoming the limitations, diversity or inconsistency. Much of this material is common to all computing and data processing, be it on large, general-purpose machines, PCs or even a calculator, pencilandpaper.Inthiswewishtoavoidgimmicksandtricks,insteademphasizingascientificapproach. That is, we test claims, measure performance, deepen our understanding of what works and what does not, gradually improving our computing tools and our abilities to use them as we develop a solution to a problem. Athirdgoalwillbeavoidingunnecessaryexpense.Thosewithmoneyandtimetothrowawaywethank for buying our book. They need read no further. Others with slimmer budgets will hopefully find some useful tips to keep costs down. In summary, this book is intended to be a guide and handbook to the calculation practitioner who must produce correct answers to problems that can be stated mathematically. With this in mind, an index is provided to enable quick reference use of the material. It is our hope that the text is interesting, comprehensible, and informative to users. Having stated the goals of this book, it may be assumed that objectives left unmentioned will not be pursued.However,thediverseandturbulentactivityconcerningPCshascreatedaclimatewherereaders mayexpectadifferentbookfromthatwhichwehavewritten.Therefore,ashortlistoftopicsthatarenot addressed is presented here. • Thereisnocomparativeshoppingguidetocomputerhardware,peripheralsorsoftware.Theexamples that do appear are there to serve as illustrations of the text. One reason for not attempting such a catalog is that it is difficult to keep it accurate in detail as manufacturers make alterations and 4 Copyright©1984,1994 JC&MM Nash SCIENTIFICCOMPUTINGWITHPCs NashInformationServicesInc.,1975BelAirDrive,Ottawa,ONK2C0X1Canada Copyfor:Dr. Dobb’s Journal introduce their "new" products. Another reason is that we prefer to write from experience, which clearly cannot be products just released today. • There is no attempt to present mathematical software formally in this volume. In other works (Nash JC,1990d;NashJCandWalker-Smith,1987;ourmagazinecolumns)wehavediscussedmethodsfor solution of many mathematical problems. We do, where appropriate, mention some sources and examples of mathematical software. We point to sources and advice on their use, but do not include machine readable software. • Thereisnoattempttoprovideanall-purposehandbookforeveryPCowner.Whilewesincerelyfeel there are useful ideas here for all who work with computers, the focus is on calculation and its practitioners as described below. 1.3 The Scientific Method and Our Audience Inalltechnicalfieldsofendeavor,quantitativemethodsareassuminganincreasingimportanceanduse. Heighteningourunderstandingofphenomena,naturalorman-made,quantitativemeasuresbringalevel of detail compared to simple qualitative descriptions of observed objects or events. In business decision-making, numerical rather than descriptive information is vital. In engineering, accurate calculations of the strengths of structures and materials are important in saving millions of dollars in unnecessary effort and fabric, while at the same time such results are critical to the integrity and safety of the structures built. Quantitative methods are an outgrowth of the scientific method, which may be summarized as follows: • Careful observation of the system of interest; • Formulation of a model explaining the system’s behavior; • Testing of the model by comparison of its behavior with that of the real system; • Further observation, model refinement and testing. Fromthenaturalsciences,thescientificmethodhasinrecentyearsspreadtosocialsciencesandbusiness. Notallapplicationshavebeeneitherwell-foundedorwell-executed,especiallywhenthescientificmethod istakentoimplytheuseofacomputermodel.Modelsarepopularbecausetheyaremuchlesscostlythan experiments or prototypes. Their limitations derive from our imperfect understanding or poor approximationofthesysteminquestion.Inasocialmodelofconsumerbuyinghabits,wemaybecontent withveryroughindicatorsofhowalargegroupofpeoplereacttochangesinpricesorpolicies,sincethe alternative is a complete lack of information. For aircraft flight simulation, however, we wish to mimic the behavior of an airplanevery precisely so that the pilot can practice maneuvers without risk to life or property, while saving fuel and avoiding airport charges. Models and related quantitative methods (the spectrum of statistical and data analysis tools) require calculationstobeperformed.Itistothosewhomustcarryoutthesecalculationsthatthisbookisdirected. The special interest is PCs, because calculations are increasingly being carried out in such computing environments. 1.4 Computer Configurations of Interest PCs may be purchased with an extremely wide range of options and it is necessary to define the type of machine that is the focus of this book. For our purposes, we will be interested in machines that are can carry out serious computations, which implies they must be able to run reasonably sophisticated software. The key word here is "reasonably." In1980,suchsoftwarewasoperatedinamachinewithaprocessor,memory,videodisplayandkeyboard,