20 Chapter 1.Preliminaries Matrices and Two-Dimensional Arrays The zero-versus unit-offset issue arises here,too.Let us,however,defer it for a moment in favor of an even more fundamental matter.that of variable dimension arrays(FORTRAN terminology)or conformant arrays(Pascal terminology).These are arrays that need to be passed to a function along with real-time information about their two-dimensional size.The systems programmer rarely deals with two- dimensional arrays,and almost never deals with two-dimensional arrays whose size is variable and known only at run time.Such arrays are,however,the bread and butter of scientific computing.Imagine trying to live with a matrix inversion routine that could work with only one size of matrix! There is no technical reason that a C compiler could not allow a syntax like void someroutine(a,m,n) float a[m][n]; /ILLEGAL DECLARATION * y and emit code to evaluate the variable dimensions m and n(or any variable-dimension 令 expression)each time someroutine (is entered.Alas!the above fragment is forbidden by the C language definition.The implementation of variable dimensions in C instead requires some additional finesse;however,we will see that one is Press. rewarded for the effort. There is a subtle near-ambiguity in the C syntax for two-dimensional array 9 references.Let us elucidate it,and then turn it to our advantage.Consider the array reference to a(say)float value a[i][j],where i and j are expressions that evaluate to type int.A C compiler will emit quite different machine code for OF SCIENTIFIC( this reference,depending on how the identifier a has been declared.If a has been 6 declared as a fixed-size array,e.g.,float a[5][9];,then the machine code is:"to the address a add 9 times i.then add i.return the value thus addressed."Notice that the constant 9 needs to be known in order to effect the calculation,and an integer multiplication is required (see Figure 1.2.1). Suppose,on the other hand,that a has been declared by float **a;.Then the machine code for a[i]j]is:"to the address of a add i,take the value thus Numerica 10621 addressed as a new address,add i to it.return the value addressed by this new address."Notice that the underlying size of a]]does not enter this calculation at all,and that there is no multiplication;an additional indirection replaces it.We thus have,in general,a faster and more versatile scheme than the previous one.The price that we pay is the storage requirement for one array of pointers(to the rows of a[][]),and the slight inconvenience of remembering to initialize those pointers when we declare an array. Here is our bottom line:We avoid the fixed-size two-dimensional arrays of C as being unsuitable data structures for representing matrices in scientific computing.We adopt instead the convention"pointer to array of pointers,"with the array elements pointing to the first element in the rows of each matrix.Figure 1.2.1 contrasts the rejected and adopted schemes. The following fragment shows how a fixed-size array a of size 13 by 9 is converted to a"pointer to array of pointers"reference aa:20 Chapter 1. Preliminaries Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). Matrices and Two-Dimensional Arrays The zero- versus unit-offset issue arises here, too. Let us, however, defer it for a moment in favor of an even more fundamental matter, that of variable dimension arrays (FORTRAN terminology) or conformant arrays (Pascal terminology). These are arrays that need to be passed to a function along with real-time information about their two-dimensional size. The systems programmer rarely deals with two￾dimensional arrays, and almost never deals with two-dimensional arrays whose size is variable and known only at run time. Such arrays are, however, the bread and butter of scientific computing. Imagine trying to live with a matrix inversion routine that could work with only one size of matrix! There is no technical reason that a C compiler could not allow a syntax like void someroutine(a,m,n) float a[m][n]; /* ILLEGAL DECLARATION */ and emit code to evaluate the variable dimensions m and n (or any variable-dimension expression) each time someroutine() is entered. Alas! the above fragment is forbidden by the C language definition. The implementation of variable dimensions in C instead requires some additional finesse; however, we will see that one is rewarded for the effort. There is a subtle near-ambiguity in the C syntax for two-dimensional array references. Let us elucidate it, and then turn it to our advantage. Consider the array reference to a (say) float value a[i][j], where i and j are expressions that evaluate to type int. A C compiler will emit quite different machine code for this reference, depending on how the identifier a has been declared. If a has been declared as a fixed-size array, e.g., float a[5][9];, then the machine code is: “to the address a add 9 times i, then add j, return the value thus addressed.” Notice that the constant 9 needs to be known in order to effect the calculation, and an integer multiplication is required (see Figure 1.2.1). Suppose, on the other hand, that a has been declared by float **a;. Then the machine code for a[i][j] is: “to the address of a add i, take the value thus addressed as a new address, add j to it, return the value addressed by this new address.” Notice that the underlying size of a[][] does not enter this calculation at all, and that there is no multiplication; an additional indirection replaces it. We thus have, in general, a faster and more versatile scheme than the previous one. The price that we pay is the storage requirement for one array of pointers (to the rows of a[][]), and the slight inconvenience of remembering to initialize those pointers when we declare an array. Here is our bottom line: We avoid the fixed-size two-dimensional arrays of C as being unsuitable data structures for representing matrices in scientific computing. We adopt instead the convention “pointer to array of pointers,” with the array elements pointing to the first element in the rows of each matrix. Figure 1.2.1 contrasts the rejected and adopted schemes. The following fragment shows how a fixed-size array a of size 13 by 9 is converted to a “pointer to array of pointers” reference aa: