Chapter 7.Random Numbers http://www.nr.com or call 7.0 Introduction 11-800-72 Cambridge It may seem perverse to use a computer,that most precise and deterministic of NUMERICAL RECIPES IN all machines conceived by the human mind,to produce"random"numbers.More than perverse,it may seem to be a conceptual impossibility.Any program,after all, server will produce output that is entirely predictable,hence not truly "random." compu Nevertheless,practical computer "random number generators are in common Press C:THEA use.We will leave it to philosophers of the computer age to resolve the paradox in a deep way (see,e.g.,Knuth [1]83.5 for discussion and references).One sometimes 号 hears computer-generated sequences termed pseudo-random,while the word random is reserved for the output of an intrinsically random physical process,like the elapsed time between clicks of a Geiger counter placed next to a sample of some radioactive SCIENTIFIC element.We will not try to make such fine distinctions. A working,though imprecise,definition of randomness in the context of 6 computer-generated sequences,is to say that the deterministic program that produces a random sequence should be different from,and-in all measurable respects- COMPUTING statistically uncorrelated with,the computer program that uses its output.In other words,any two different random number generators ought to produce statistically r Numerical 188-1892 Further the same results when coupled to your particular applications program.Ifthey don't, then at least one of them is not (from your point of view)a good generator. The above definition may seem circular,comparing,as it does,one generator to another.However,there exists a body of random number generators which mutually (outside Recipes 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 are North Software. known to exist,we can leave to the philosophers the problem of defining them. A pragmatic point of view,then,is that randomness is in the eye of the beholder (or programmer).What is random enough for one application may not be random America) visit website enough for another.Still,one is not entirely adrift in a sea of incommensurable machine. 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 random number generators ought to pass all of these tests;or at least the user had better be aware of any that they fail,so that he or she will be able to judge whether they are relevant to the case at hand. 274Permission 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). Chapter 7. Random Numbers 7.0 Introduction It may seem perverse to use a computer, that most precise and deterministic of all machines conceived by the human mind, to produce “random” numbers. More than perverse, it may seem to be a conceptual impossibility. Any program, 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 deep way (see, e.g., Knuth [1] §3.5 for discussion and references). One sometimes hears computer-generated sequences termed pseudo-random, while the word random is reserved for the output of an intrinsically random physical process, like the elapsed time between clicks of a Geiger counter placed next to a sample of some radioactive element. We will not try to make such fine distinctions. A working, though imprecise, definition of randomness in the context of computer-generated sequences, is to say that the deterministic program that produces a random sequence should be different from, and — in all measurable respects — statistically uncorrelated with, the computer program that uses its output. In other words, any two different random number generators ought to produce statistically the same results when coupled to your particular applications program. If they don’t, then at least one of them is not (from your point of view) a good generator. The above definition may seem circular, comparing, as it does, one generator to another. However, there exists a body of random number generators which mutually 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 are known to exist, we can leave to the philosophers the problem of defining them. A pragmatic point of view, then, is that randomness is in the eye of the beholder (or programmer). What is random enough for one application may not be random enough 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 random number generators ought to pass all of these tests; or at least the user had better be aware of any that they fail, so that he or she will be able to judge whether they are relevant to the case at hand. 274