c1-1 (Numerical Recipes in C)

1.1 Program Organization and Control Structures5Kernighan, B., and Ritchie, D. 1978, The C Programming Language (Englewood Cliffs, NJ:Prentice-Hall). [2] [Reference for K&R “traditional” C. Later editions of this book conformto the ANSI C standard.]Meeus, J. 1982, Astronomical Formulae for Calculators, 2nd ed., revised and enlarged (Richmond, VA: Willmann-Bell). [3]We sometimes like to point out the close analogies between computer programs,on the one hand, and written poetry or written musical scores, on the other. Allthree present themselves as visual media, symbols on a two-dimensional page orcomputer screen.

Yet, in all three cases, the visual, two-dimensional, frozen-in-timerepresentation communicates (or is supposed to communicate) something ratherdifferent, namely a process that unfolds in time. A poem is meant to be read; music,played; a program, executed as a sequential series of computer instructions.In all three cases, the target of the communication, in its visual form, is a humanbeing. The goal is to transfer to him/her, as efficiently as can be accomplished,the greatest degree of understanding, in advance, of how the process will unfold intime. In poetry, this human target is the reader. In music, it is the performer. Inprogramming, it is the program user.Now, you may object that the target of communication of a program is nota human but a computer, that the program user is only an irrelevant intermediary,a lackey who feeds the machine.

This is perhaps the case in the situation wherethe business executive pops a diskette into a desktop computer and feeds thatcomputer a black-box program in binary executable form. The computer, in thiscase, doesn’t much care whether that program was written with “good programmingpractice” or not.We envision, however, that you, the readers of this book, are in quite a differentsituation. You need, or want, to know not just what a program does, but also howit does it, so that you can tinker with it and modify it to your particular application.You need others to be able to see what you have done, so that they can criticize oradmire. In such cases, where the desired goal is maintainable or reusable code, thetargets of a program’s communication are surely human, not machine.One key to achieving good programming practice is to recognize that programming, music, and poetry — all three being symbolic constructs of the humanbrain — are naturally structured into hierarchies that have many different nestedlevels.

Sounds (phonemes) form small meaningful units (morphemes) which in turnform words; words group into phrases, which group into sentences; sentences makeparagraphs, and these are organized into higher levels of meaning. Notes formmusical phrases, which form themes, counterpoints, harmonies, etc.; which formmovements, which form concertos, symphonies, and so on.The structure in programs is equally hierarchical. Appropriately, good programming practice brings different techniques to bear on the different levels [1-3].At a low level is the ascii character set.

Then, constants, identifiers, operands,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).1.1 Program Organization and ControlStructures6Chapter 1.Preliminariesoperators.

Then program statements, like a[j+1]=b+c/3.0;. Here, the best programming advice is simply be clear, or (correspondingly) don’t be too tricky. Youmight momentarily be proud of yourself at writing the single linek=(2-j)*(1+3*j)/2;k=j+1;if (k == 3) k=0;Many programming stylists would even argue for the ploddingly literalswitch (j) {case 0: k=1; break;case 1: k=2; break;case 2: k=0; break;default: {fprintf(stderr,"unexpected value for j");exit(1);}}on the grounds that it is both clear and additionally safeguarded from wrong assumptions about the possible values of j.

Our preference among the implementationsis for the middle one.In this simple example, we have in fact traversed several levels of hierarchy:Statements frequently come in “groups” or “blocks” which make sense only takenas a whole. The middle fragment above is one example. Another isswap=a[j];a[j]=b[j];b[j]=swap;which makes immediate sense to any programmer as the exchange of two variables,whileans=sum=0.0;n=1;is very likely to be an initialization of variables prior to some iterative process. Thislevel of hierarchy in a program is usually evident to the eye. It is good programmingpractice to put in comments at this level, e.g., “initialize” or “exchange variables.”The next level is that of control structures. These are things like the switchconstruction in the example above, for loops, and so on.

This level is sufficientlyimportant, and relevant to the hierarchical level of the routines in this book, thatwe will come back to it just below.At still higher levels in the hierarchy, we have functions and modules, and thewhole “global” organization of the computational task to be done. In the musicalanalogy, we are now at the level of movements and complete works. At these levels,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).if you want to permute cyclically one of the values j = (0, 1, 2) into respectivelyk = (1, 2, 0). You will regret it later, however, when you try to understand thatline. Better, and likely also faster, is1.1 Program Organization and Control Structures7Sample 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).modularization and encapsulation become important programming concepts, thegeneral idea being that program units should interact with one another only throughclearly defined and narrowly circumscribed interfaces. Good modularization practiceis an essential prerequisite to the success of large, complicated software projects,especially those employing the efforts of more than one programmer.

It is also goodpractice (if not quite as essential) in the less massive programming tasks that anindividual scientist, or reader of this book, encounters.Some computer languages, such as Modula-2 and C++, promote good modularization with higher-level language constructs absent in C. In Modula-2, for example,functions, type definitions, and data structures can be encapsulated into “modules”that communicate through declared public interfaces and whose internal workingsare hidden from the rest of the program [4]. In the C++ language, the key conceptis “class,” a user-definable generalization of data type that provides for data hiding,automatic initialization of data, memory management, dynamic typing, and operatoroverloading (i.e., the user-definable extension of operators like + and * so as to beappropriate to operands in any particular class) [5]. Properly used in defining the datastructures that are passed between program units, classes can clarify and circumscribethese units’ public interfaces, reducing the chances of programming error and alsoallowing a considerable degree of compile-time and run-time error checking.Beyond modularization, though depending on it, lie the concepts of objectoriented programming.

Here a programming language, such as C++ or Turbo Pascal5.5 [6], allows a module’s public interface to accept redefinitions of types or actions,and these redefinitions become shared all the way down through the module’shierarchy (so-called polymorphism). For example, a routine written to invert amatrix of real numbers could — dynamically, at run time — be made able to handlecomplex numbers by overloading complex data types and corresponding definitionsof the arithmetic operations. Additional concepts of inheritance (the ability to definea data type that “inherits” all the structure of another type, plus additional structureof its own), and object extensibility (the ability to add functionality to a modulewithout access to its source code, e.g., at run time), also come into play.We have not attempted to modularize, or make objects out of, the routines inthis book, for at least two reasons.

First, the chosen language, C, does not really makethis possible. Second, we envision that you, the reader, might want to incorporatethe algorithms in this book, a few at a time, into modules or objects with a structureof your own choosing. There does not exist, at present, a standard or accepted setof “classes” for scientific object-oriented computing. While we might have tried toinvent such a set, doing so would have inevitably tied the algorithmic content of thebook (which is its raison d’être) to some rather specific, and perhaps haphazard, setof choices regarding class definitions.On the other hand, we are not unfriendly to the goals of modular and objectoriented programming.

Within the limits of C, we have therefore tried to structureour programs to be “object friendly.” That is one reason we have adopted ANSIC with its function prototyping as our default C dialect (see §1.2). Also, withinour implementation sections, we have paid particular attention to the practices ofstructured programming, as we now discuss.8Chapter 1.PreliminariesControl StructuresCatalog of Standard StructuresIteration.In C, simple iteration is performed with a for loop, for examplefor (j=2;j<=1000;j++) {b[j]=a[j-1];a[j-1]=j;}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.