7.7 Quasi-(that is,Sub-)Random Sequences 315 Note that we have not provided the routine sobseg with a means of starting the sequence at a point other than the beginning,but this feature would be easy to add.Once the initialization of the direction numbers iv has been done,the jth point can be obtained directly by XORing together those direction numbers corresponding to nonzero bits in the Gray code of j,as described above. The Latin Hypercube We might here give passing mention the unrelated technique of Latin square or Latin hypercube sampling,which is useful when you must sample an N-dimensional space exceedingly sparsely,at M points.For example,you may want to test the crashworthiness of cars as a simultaneous function of 4 different design parameters, but with a budget of only three expendable cars.(The issue is not whether this is a good plan-it isn't-but rather how to make the best of the situation!) The idea is to partition each design parameter(dimension)into M segments,so that the whole space is partitioned into MN cells.(You can choose the segments in each dimension to be equal or unequal,according to taste.)With 4 parameters and 3 cars,for example,you end up with 3 x 3 x 3 x 3 =81 cells. Next,choose M cells to contain the sample points by the following algorithm: 9 Randomly choose one of the MN cells for the first point.Now eliminate all cells that agree with this point on any of its parameters (that is,cross out all cells in the same row,column,etc.),leaving (M-1)N candidates.Randomly choose one of these,eliminate new rows and columns,and continue the process until there is only one cell left,which then contains the final sample point. 旦 The result of this construction is that each design parameter will have been tested in every one of its subranges.If the response of the system under test is dominated by one of the design parameters,that parameter will be found with this 61 sampling technique.On the other hand,if there is an important interaction among different design parameters,then the Latin hypercube gives no particular advantage. Use with care. CITED REFERENCES AND FURTHER READING: Numerica 10621 Halton,J.H.1960,Numerische Mathematik,vol.2,pp.84-90.[1] Bratley P.,and Fox,B.L.1988,ACM Transactions on Mathematical Software,vol.14,pp.88- 431 100.[2) Recipes Lambert,J.P.1988,in Numerical Mathematics-Singapore 1988,ISNM vol.86,R.P.Agarwal, Y.M.Chow,and S.J.Wilson,eds.(Basel:Birkhauser),pp.273-284. 腿 Niederreiter,H.1988,in Numerical Integration Ill,ISNM vol.85,H.Brass and G.Hammerlin, North eds.(Basel:Birkhauser),pp.157-171. Sobol',I.M.1967,USSR Computational Mathematics and Mathematical Physics,vol.7,no.4, pp.86-112.[3] Antonov,I.A.,and Saleev,V.M 1979,USSR Computational Mathematics and Mathematical Physics,vol.19,no.1,pp.252-256.[4] Dunn,O.J.,and Clark,V.A.1974,Applied Statistics:Analysis of Variance and Regression(New York,Wiley)[discusses Latin Square].7.7 Quasi- (that is, Sub-) Random Sequences 315 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). Note that we have not provided the routine sobseq with a means of starting the sequence at a point other than the beginning, but this feature would be easy to add. Once the initialization of the direction numbers iv has been done, the jth point can be obtained directly by XORing together those direction numbers corresponding to nonzero bits in the Gray code of j, as described above. The Latin Hypercube We might here give passing mention the unrelated technique of Latin square or Latin hypercube sampling, which is useful when you must sample an N-dimensional space exceedingly sparsely, at M points. For example, you may want to test the crashworthiness of cars as a simultaneous function of 4 different design parameters, but with a budget of only three expendable cars. (The issue is not whether this is a good plan — it isn’t — but rather how to make the best of the situation!) The idea is to partition each design parameter (dimension) into M segments, so that the whole space is partitioned into M N cells. (You can choose the segments in each dimension to be equal or unequal, according to taste.) With 4 parameters and 3 cars, for example, you end up with 3 × 3 × 3 × 3 = 81 cells. Next, choose M cells to contain the sample points by the following algorithm: Randomly choose one of the M N cells for the first point. Now eliminate all cells that agree with this point on any of its parameters (that is, cross out all cells in the same row, column, etc.), leaving (M − 1)N candidates. Randomly choose one of these, eliminate new rows and columns, and continue the process until there is only one cell left, which then contains the final sample point. The result of this construction is that each design parameter will have been tested in every one of its subranges. If the response of the system under test is dominated by one of the design parameters, that parameter will be found with this sampling technique. On the other hand, if there is an important interaction among different design parameters, then the Latin hypercube gives no particular advantage. Use with care. CITED REFERENCES AND FURTHER READING: Halton, J.H. 1960, Numerische Mathematik, vol. 2, pp. 84–90. [1] Bratley P., and Fox, B.L. 1988, ACM Transactions on Mathematical Software, vol. 14, pp. 88– 100. [2] Lambert, J.P. 1988, in Numerical Mathematics – Singapore 1988, ISNM vol. 86, R.P. Agarwal, Y.M. Chow, and S.J. Wilson, eds. (Basel: Birkha¨user), pp. 273–284. Niederreiter, H. 1988, in Numerical Integration III, ISNM vol. 85, H. Brass and G. H¨ammerlin, eds. (Basel: Birkha¨user), pp. 157–171. Sobol’, I.M. 1967, USSR Computational Mathematics and Mathematical Physics, vol. 7, no. 4, pp. 86–112. [3] Antonov, I.A., and Saleev, V.M 1979, USSR Computational Mathematics and Mathematical Physics, vol. 19, no. 1, pp. 252–256. [4] Dunn, O.J., and Clark, V.A. 1974, Applied Statistics: Analysis of Variance and Regression (New York, Wiley) [discusses Latin Square]