f7-0

Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).Chapter 7. Random Numbers 7.0 Introduction It may seem perverseto use a computer,that most precise and deterministic of all machines conceived by the human mind, to produce “random” numbers. Morethan perverse,it may seem to be a conceptualimpossibility. Anyprogram,after all, will produce output that is entirely predictable, hence not truly “random.” Nevertheless, practical computer “random number generators” are in common use. We will leave it to philosophers of the computer age to resolve the paradox in a deepway (see, e.g., Knuth [1]§3.5 fordiscussion and references). One sometimes hearscomputer-generatedsequencestermed pseudo-random ,whiletheword random isreservedfortheoutputofanintrinsicallyrandomphysicalprocess,liketheelapsed timebetweenclicksofaGeigercounterplacednexttoasampleofsomeradioactiveelement. We will not try to make such fine distinctions. A working, though imprecise, definition of randomness in the context of computer-generatedsequences,istosaythatthedeterministicprogramthatproduces a random sequence should be different from, and — in all measurable respects — statistically uncorrelated with, the computer program that usesits output. In other words, any two different random number generators ought to produce statistically thesameresultswhencoupledtoyourparticularapplicationsprogram. Iftheydon’t, then at least one of them is not (from your point of view) a good generator. Theabovedefinitionmayseemcircular,comparing,asitdoes,onegeneratorto another. However,thereexistsabodyofrandomnumbergeneratorswhichmutually do satisfy the definition over a very, very broad class of applications programs. And it is also found empirically that statistically identical results are obtained from random numbers produced by physical processes. So, because such generators areknownto exist, we can leave to the philosophersthe problemof definingthem. Apragmaticpointofview,then,isthatrandomnessisintheeyeofthebeholder (or programmer). What is random enough for one application may not be randomenough for another. Still, one is not entirely adrift in a sea of incommensurable applications programs: There is a certain list of statistical tests, some sensible and some merely enshrined by history, which on the whole will do a very good job of ferreting out any correlations that are likely to be detected by an applications program(in this case, yours). Good randomnumber generators ought to pass all ofthese tests; or at least the user hadbetter be aware of anythat theyfail, so that he or she will be able to judge whether they are relevant to the case at hand. 266 7.1UniformDeviates 267Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).As for references on this subject, the one to turn to first is Knuth [1]. Then try[2]. Only a few of the standard books on numerical methods [3-4]treat topics relating to random numbers. CITED REFERENCES AND FURTHER READING: Knuth,D.E.1981, SeminumericalAlgorithms ,2nded.,vol.2of TheArtofComputerProgramming (Reading, MA: Addison-Wesley), Chapter 3, especially §3.5. [1] Bratley, P., Fox, B.L., and Schrage, E.L. 1983, A Guide to Simulation (New York: Springer- Verlag). [2] Dahlquist, G., and Bjorck, A. 1974, Numerical Methods (Englewood Cliffs, NJ: Prentice-Hall), Chapter 11. [3] Forsythe, G.E., Malcolm, M.A., and Moler, C.B. 1977, Computer Methods for Mathematical Computations (Englewood Cliffs, NJ: Prentice-Hall), Chapter 10. [4] 7.1 Uniform Deviates Uniform deviates are just random numbers that lie within a specified range (typically0to 1),withanyonenumberintherangejust as likelyas anyother. They are, in other words, what you probably think “random numbers” are. However, we want to distinguish uniform deviates from other sorts of random numbers, for example numbers drawn from a normal (Gaussian) distribution of specified meanandstandarddeviation. Theseothersortsofdeviatesarealmostalwaysgeneratedby performing appropriate operations on one or more uniform deviates, as we will see insubsequentsections. So,areliablesourceofrandomuniformdeviates,thesubjectof this section, is an essential building block for any sort of stochastic modeling or Monte Carlo computer work. System-Supplied RandomNumberGenerators Yourcomputerverylikelyhaslurkingwithinitalibraryroutinewhichiscalled a“randomnumbergenerator.” Thatroutinetypicallyhas anunforgettablenamelike “ran,” and a calling sequence like x=ran(iseed) sets xto the next random number and updates iseed You initialize iseedto a (usually) arbitrary value before the first call to ran. Eachinitializingvaluewill typicallyreturnadifferentsubsequentrandomsequence,oratleastadifferentsubsequenceofsomeoneenormouslylongsequence. The same initializingvalueof iseedwill always returnthe samerandomsequence,however. Now our first, and perhaps most important, lesson in this chapter is: Be very, verysuspiciousofasystem-supplied ranthatresemblestheonejustdescribed. Ifall scientific papers whose results are in doubt because of bad rans were to disappear from library shelves, there would be a gap on each shelf about as big as your fist. System-supplied rans arealmost always linearcongruentialgenerators ,which