angelm
加人: 2006-01-20
回应: 110
|
generation of random numbers
Random Numbers, Generation Of
At first it might seem odd to want random numbers: that is, numbers in which no patterns can be found, which do not "say" anything. Yet it would be difficult to name a branch of science that does not rely, heavily or occasionally, on random numbers.
The most common scientific use for random numbers is in Monte Carlo simulations. A Monte Carlo simulation is any calculation that feeds random numbers into a set of deterministic rules (such as Newton's laws of motion) to model the outcome of a physical process. (Monte Carlo simulations are named after the city of Monte Carlo, famous for its gambling casinos.) Most real-world processes involve a random element, such as the arrival times of photons or of phone calls, the decay times of atomic nuclei, or the thermal jigglings of particles. In Monte Carlo simulations, therefore, the purpose of randomness is realism. Another feature of randomness is secrecy; if someone picks a number purely at random, there is no systematic way for someone else to guess what that number is. Random numbers are thus important in cryptography, the study of secret codes.
There are two basic ways to make random numbers. One is to perform physical experiments that produce apparently random outcomes: coin-flipping, sampling electronic noise, or the like. To the outcome of each experiment one assigns a number, thus obtaining a random series. The second approach is arithmetical. One may perform calculations that produce sequences of digits that behave for certain purposes as if they were random, even though they are known not to be. Such numbers are called pseudo-random numbers, and the recipes or algorithms for producing them are called pseudo-random number generators (PRNGs).
Both ways of making "random" numbers have their advantages, but PRNGs are much favored today over physical methods for several reasons. First, the speed with which a physical process produces random numbers depends on the process itself, whereas the speed of a PRNG increases with computer speed. Second, physical random number generators tend to be fussy devices requiring regular readjustment. Third, the non-randomness of pseudo-random numbers is really an advantage; a PRNG, being merely a series of calculations, can reproduce the same series of pseudo-random numbers on demand. This property is important in debugging Monte Carlo simulations, because it requires a defective simulation to go wrong exactly the same way every time. It is also important in spread-spectrum digital communications systems, which use pseudo-random numbers to smear out transmitted information signals into noise-like signals that are resistant to interference and interception. This technique is made possible by the repeatability of pseudo-random numbers, for the receiver of a spread-spectrum signal can only reassemble the scrambled signal if it is set to generate the same pseudo-random sequence as the transmitter. Only in applications where unpredictability is more important than repeatability, such as cryptography, are physical devices still used to produce random numbers.
Many PRNGs are variations on a single, simple algorithm. Consider a series generated by the following rule:
xi = Kxi - 1 (modulo M), i = {1, 2, 3, . . . }.
That is, each new number in the series (xi) is found by multiplying the previous number in the series (xi - 1) by some constant K, then taking the result modulo M. "Taking the result modulo M" means that the result of the multiplication Kxi - 1 is divided by M and only the remainder kept. Thus if K = 4, xi - 1 = 5, and M = 7, then Kxi - 1 = 5 x 4 = 20, and xi is given by 20 modulo 7, which is by definition the remainder of 20/7 (2 6/7). This remainder is 6/7 or approximately .857142--an apparently random number. The first number in the series, x0, is called the "seed" and may take on any chosen value, some choices being better than others; 0, for instance, would make a terrible x0, resulting in xi = 0 for all i. Every distinct seed produces a distinct, repeating sequence of pseudo-random numbers.
Pseudo-random, however, means not truly random. There are several ways in which the numbers generated by a PRNG (such as the one just described) fail to behave like truly random numbers. Their first and most basic failing is repetition or periodicity. Periodicity follows from the fact that a binary computer using N-bit words can only name 2N different numbers. Any possible PRNG running on any real computer is therefore doomed to eventually run out of numbers and start repeating itself. The reality is even worse, for no PRNG produces anywhere near the theoretical limit of 2N pseudo-random numbers before starting to repeat itself. Furthermore, other, more subtle failures of randomness can also be detected in the output of any PRNG, and these non-random qualities can (depending on many factors) be disastrous for practical Monte Carlo simulations.
In an effort to overcome these limitations, many PRNGs have been invented over the last 50 or so years. Most are variations on the theme described above: each new number in the series is calculated by subjecting an earlier number in the series to some simple set of arithmetic operations. For example, the PRNG described above is a special case of a slightly more complex group of PRNGs in common use, linear congruential generators (LCGs). LCG algorithms have the form
xi = Axi - 1 + B (modulo M), i = {1, 2, 3, . . . }.
where A and B are mutually prime numbers. (It can easily be seen that setting B = 0 recovers the basic PRNG given earlier.) The PRNG built into the ANSI C programming language, for example, is an LCG algorithm with M = 231, A = 1103515245, B = 12345, and seed x0 = 12345.
Other PRNGs in widespread use are multiple recursive generators, lagged Fibonnaci generators, inversive congruential generators, and explicit-inversive congruential generators. Much effort goes into testing these algorithms to characterize the statistical qualities of the numbers they generate. A cautious researcher using Monte Carlo simulation will sometimes run her or his simulation several times, using a different PRNG for each run to see how this affects the results.
The field of PRNG design and evaluation continues to be an active one, driven by the ever-increasing use of computer simulation as a scientific tool. 投稿于 2006-01-20 23:47:24 |
