A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value or state, usually called the PRNG's seed (which may be based on truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility. PRNGs are central in applications such as simulations (e.g. for the Monte Carlo method), electronic games (e.g. for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs, and more elaborate algorithms, which do not inherit the linearity of simpler PRNGs, are needed. Appropriate statistical properties are a central requirement for the output of a PRNG. Careful mathematical analysis is required to have reasonable confidence that a given PRNG generates numbers that are sufficiently close to random to suit the intended use. John von Neumann cautioned about possible misinterpretation of a PRNG as a truly random generator, joking that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
Potential issues In practice, the output from many common PRNGs exhibit artifacts that cause them to fail statistical pattern-detection tests. These include:
Shorter-than-expected periods for some seed states (such seed states may be called "weak" in this context); Lack of uniformity of distribution for large quantities of generated numbers; Correlation of successive values; Poor dimensional distribution of the output sequence; Distances between where certain values occur are distributed differently from those in a random sequence distribution. Defects exhibited by flawed PRNGs range from unnoticeable (and unknown) to very obvious. An example was the RANDU random number algorithm used for decades on mainframe computers. It was seriously flawed, but its inadequacy went undetected for a very long time. In many fields, research work prior to the 21st century that relied on random selection or on Monte Carlo simulations, or in other ways relied on PRNGs, were much less reliable than ideal as a result of using poor-quality PRNGs. Even today, caution is sometimes required, as illustrated by the following warning in the International Encyclopedia of Statistical Science (2010).
The list of widely used generators that should be discarded is much longer [than the list of good generators]. Do not trust blindly the software vendors. Check the default RNG of your favorite software and be ready to replace it if needed. This last recommendation has been made over and over again over the past 40 years. Perhaps amazingly, it remains as relevant today as it was 40 years ago. As an illustration, consider the widely used programming language Java. Up until 2020, Java still relied on a linear congruential generator (LCG) for its PRNG, which is of low quality (see further below). Java support was upgraded with Java 17. One well-known PRNG to avoid major problems and still run fairly quickly is the Mersenne Twister (discussed below), which was published in 1998. Other higher-quality PRNGs, both in terms of computational and statistical performance, were developed before and after this date; these can be identified in the List of pseudorandom number generators.
Generators based on linear recurrences In the second half of the 20th century, the standard class of algorithms used for PRNGs comprised linear congruential generators. The quality of LCGs was known to be inadequate, but better methods were unavailable. Press et al. (2007) described the result thus: "If all scientific papers whose results are in doubt because of [LCGs and related] were to disappear from library shelves, there would be a gap on each shelf about as big as your fist." A major advance in the construction of pseudorandom generators was the introduction of techniques based on linear recurrences on the two-element field; such generators are related to linear-feedback shift registers. The 1997 invention of the Mersenne Twister, in particular, avoided many of the problems with earlier generators. The Mersenne Twister has a period of 219 937 − 1 iterations (≈ 4.3×106001), is proven to be equidistributed in (up to) 623 dimensions (for 32-bit values), and at the time of its introduction was running faster than other statistically reasonable generators. In 2003, George Marsaglia introduced the family of xorshift generators, again based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, they pass strong statistical tests. In 2006, the WELL family of generators was developed. The WELL generators in some ways improves on the quality of the Mersenne Twister, which has a too-large state space and a very slow recovery from state spaces with a large number of zeros.
Counter-based RNGs
A counter-based random number generation (CBRNG, also known as a counter-based pseudo-random number generator, or CBPRNG) is a kind of PRNG that uses only an integer counter as its internal state:
output = f ( n , key ) {\displaystyle {\text{ output }}=f(n,{\text{ key}})}
They are generally used for generating pseudorandom numbers for large parallel computations, such as over GPU or CPU clusters. They have certain advantages:
The only "state" needed is the counter value and the key. For a given counter and key, the output is always the same. This property makes CBRNGs reproducible. Because each random number is computed independently of any previous outputs, they can be generated in parallel. For example, in a massively parallel application, each thread or GPU core can be assigned a range of counter values and compute random numbers without synchronization or shared state. Since the generator does not require stepping through every intermediate state, it can "jump" to any point in the sequence in constant time. This is particularly useful in applications like Monte Carlo simulations where independent streams are needed. Examples include:
… excerpt ends here. Continue reading the full article.
