Misplaced Pages

#894105

45-485: RANDU is a linear congruential pseudorandom number generator (LCG) of the Park–Miller type , which was used primarily in the 1960s and 1970s. It is defined by the recurrence with the initial seed number V 0 {\displaystyle V_{0}} as an odd number . It generates pseudorandom integers V j {\displaystyle V_{j}} which are uniformly distributed in

90-414: A cryptographically secure pseudorandom number generator for such applications. Although LCGs have a few specific weaknesses, many of their flaws come from having too small a state. The fact that people have been lulled for so many years into using them with such small moduli can be seen as a testament to the strength of the technique. A LCG with large enough state can pass even stringent statistical tests;

135-406: A is chosen so that r  ≤  q (and thus r / q  ≤ 1), then the second term is also less than m : r ⌊ x / q ⌋ ≤ rx / q = x ( r / q ) ≤ x < m . Thus, both products can be computed with a single-width product, and the difference between them lies in the range [1− m ,  m −1], so can be reduced to [0,  m −1] with a single conditional add. A second disadvantage

180-483: A unit cube will only sample 15 parallel planes, not even close to the upper limit of ⌊ ( 2 31 × 3 ! ) 1 / 3 ⌋ = 2344 {\displaystyle {\Big \lfloor }{\big (}2^{31}\times 3!{\big )}^{1/3}{\Big \rfloor }=2344} planes. As a result of the wide use of RANDU in the early 1970s, many results from that time are seen as suspicious. This misbehavior

225-408: A LCG needs to store state and alter it each time it generates a new number. Multiple threads may access this state simultaneously causing a race condition. Implementations should use different state each with unique initialization for different threads to avoid equal sequences of random numbers on simultaneously executing threads. There are several generators which are linear congruential generators in

270-522: A different form, and thus the techniques used to analyze LCGs can be applied to them. One method of producing a longer period is to sum the outputs of several LCGs of different periods having a large least common multiple ; the Wichmann–Hill generator is an example of this form. (We would prefer them to be completely coprime , but a prime modulus implies an even period, so there must be a common factor of 2, at least.) This can be shown to be equivalent to

315-423: A long period, but is obviously non-random. Other values of c coprime to m produce a Weyl sequence , which is better distributed but still obviously non-random. Historically, poor choices for a have led to ineffective implementations of LCGs. A particularly illustrative example of this is RANDU , which was widely used in the early 1970s and led to many results which are currently being questioned because of

360-472: A mathematician would call the recurrence an affine transformation , not a linear one, but the misnomer is well-established in computer science. The Lehmer generator was published in 1951 and the Linear congruential generator was published in 1958 by W. E. Thomson and A. Rotenberg. A benefit of LCGs is that an appropriate choice of parameters results in a period which is both known and long. Although not

405-590: A modulo-2 LCG which returns the high 32 bits passes TestU01 's SmallCrush suite, and a 96-bit LCG passes the most stringent BigCrush suite. For a specific example, an ideal random number generator with 32 bits of output is expected (by the Birthday theorem ) to begin duplicating earlier outputs after √ m ≈ 2 results. Any PRNG whose output is its full, untruncated state will not produce duplicates until its full period elapses, an easily detectable statistical flaw. For related reasons, any PRNG should have

450-427: A period longer than the square of the number of outputs required. Given modern computer speeds, this means a period of 2 for all but the least demanding applications, and longer for demanding simulations. One flaw specific to LCGs is that, if used to choose points in an n-dimensional space, the points will lie on, at most, √ n !⋅ m hyperplanes ( Marsaglia's theorem , developed by George Marsaglia ). This

495-460: A power-of-2 multiplier b . A permuted congruential generator begins with a power-of-2-modulus LCG and applies an output transformation to eliminate the short period problem in the low-order bits. Unit cube A unit cube , more formally a cube of side 1 , is a cube whose sides are 1 unit long. The volume of a 3-dimensional unit cube is 1 cubic unit, and its total surface area is 6 square units. The term unit cube or unit hypercube

SECTION 10

#1732772226895

540-474: A prime just less than a power of 2 is used (the Mersenne primes 2 −1 and 2 −1 are popular), so that the reduction modulo m  = 2  −  d can be computed as ( ax  mod 2 ) +  d   ⌊ ax /2 ⌋ . This must be followed by a conditional subtraction of m if the result is too large, but the number of subtractions is limited to ad / m , which can be easily limited to one if d

585-405: A sequence which fails one test for non-randomness or another, and finding a multiplier which is satisfactory to all applicable criteria is quite challenging. The spectral test is one of the most important tests. Note that a power-of-2 modulus shares the problem as described above for c  = 0: the low k bits form a generator with modulus 2 and thus repeat with a period of 2 ; only

630-414: A single LCG with a modulus equal to the product of the component LCG moduli. Marsaglia 's add-with-carry and subtract-with-borrow PRNGs with a word size of b =2 and lags r and s ( r  >  s ) are equivalent to LCGs with a modulus of b  ±  b  ± 1. Multiply-with-carry PRNGs with a multiplier of a are equivalent to LCGs with a large prime modulus of ab −1 and

675-461: A small number of high-order bits of an LCG may well suffice. (The low-order bits of LCGs when m is a power of 2 should never be relied on for any degree of randomness whatsoever.) The low order bits go through very short cycles. In particular, any full-cycle LCG, when m is a power of 2, will produce alternately odd and even results. LCGs should be evaluated very carefully for suitability in non-cryptographic applications where high-quality randomness

720-483: A solution to 1 + 3 ≡ (1 − 157) X 0  (mod 256). This is satisfied by X 0  ≡ 41 (mod 64), so if we start with that, then X n ≡  X 0  −  Y n  (mod 256) for all n . For example, using X 0 = 233 = 3×64 + 41: The following table lists the parameters of LCGs in common use, including built-in rand() functions in runtime libraries of various compilers . This table

765-513: Is a power of 2, then c must be odd), so the value c =1 is commonly chosen. The sequence produced by other choices of c can be written as a simple function of the sequence when c =1. Specifically, if Y is the prototypical sequence defined by Y 0 = 0 and Y n +1 =  aY n  + 1 mod m, then a general sequence X n +1 =  aX n  +  c mod  m can be written as an affine function of Y : More generally, any two sequences X and Z with

810-400: Is also used for hypercubes , or "cubes" in n -dimensional spaces , for values of n other than 3 and edge length 1. Sometimes the term "unit cube" refers in specific to the set [0, 1] of all n -tuples of numbers in the interval [0, 1]. The length of the longest diagonal of a unit hypercube of n dimensions is n {\displaystyle {\sqrt {n}}} ,

855-528: Is an implementation of an LCG in Python , in the form of a generator : Free Pascal uses a Mersenne Twister as its default pseudo random number generator whereas Delphi uses a LCG. Here is a Delphi compatible example in Free Pascal based on the information in the table above. Given the same RandSeed value it generates the same sequence of random numbers as Delphi. Like all pseudorandom number generators,

900-463: Is because the higher-order bits have longer periods than the lower-order bits (see below). LCGs that use this truncation technique produce statistically better values than those that do not. This is especially noticeable in scripts that use the mod operation to reduce range; modifying the random number mod 2 will lead to alternating 0 and 1 without truncation. Contrarily, some libraries use an implicit power-of-two modulus but never output or otherwise use

945-465: Is critical. For Monte Carlo simulations, an LCG must use a modulus greater and preferably much greater than the cube of the number of random samples which are required. This means, for example, that a (good) 32-bit LCG can be used to obtain about a thousand random numbers; a 64-bit LCG is good for about 2 random samples (a little over two million), etc. For this reason, in practice LCGs are not suitable for large-scale Monte Carlo simulations. The following

SECTION 20

#1732772226895

990-418: Is defined by the recurrence relation : where X {\displaystyle X} is the sequence of pseudo-random values, and are integer constants that specify the generator. If c  = 0, the generator is often called a multiplicative congruential generator (MCG), or Lehmer RNG . If c  ≠ 0, the method is called a mixed congruential generator . When c  ≠ 0,

1035-482: Is determined by c  ≡ ±1 (mod 4), and the constant X 0 is determined by 1 ∓  c  ≡ (1 −  a ) X 0  (mod  m ). As a simple example, consider the generators X n +1 = 157 X n  + 3 mod 256 and Y n +1 = 157 Y n  + 1 mod 256; i.e. m  = 256, a  = 157, and c  = 3. Because 3 ≡ −1 (mod 4), we are searching for

1080-441: Is due to serial correlation between successive values of the sequence X n . Carelessly chosen multipliers will usually have far fewer, widely spaced planes, which can lead to problems. The spectral test , which is a simple test of an LCG's quality, measures this spacing and allows a good multiplier to be chosen. The plane spacing depends both on the modulus and the multiplier. A large enough modulus can reduce this distance below

1125-414: Is small. If a double-width product is unavailable, and the multiplier is chosen carefully, Schrage's method may be used. To do this, factor m  =  qa + r , i.e. q = ⌊ m / a ⌋ and r = m mod a . Then compute ax  mod  m = a ( x mod q ) − r ⌊ x / q ⌋ . Since x  mod  q < q ≤ m / a , the first term is strictly less than am / a  =  m . If

1170-425: Is that it is awkward to convert the value 1 ≤  x  <  m to uniform random bits. If a prime just less than a power of 2 is used, sometimes the missing values are simply ignored. Choosing m to be a power of two , most often m = 2 or m = 2 , produces a particularly efficient LCG, because this allows the modulus operation to be computed by simply truncating the binary representation. In fact,

1215-474: Is to show popularity, not examples to emulate; many of these parameters are poor. Tables of good parameters are available. random0 As shown above, LCGs do not always use all of the bits in the values they produce. In general, they return the most significant bits. For example, the Java implementation operates with 48-bit values at each iteration but returns only their 32 most significant bits. This

1260-506: The Hull–Dobell Theorem. This form may be used with any m , but only works well for m with many repeated prime factors, such as a power of 2; using a computer's word size is the most common choice. If m were a square-free integer , this would only allow a  ≡ 1 (mod  m ), which makes a very poor PRNG; a selection of possible full-period multipliers is only available when m has repeated prime factors. Although

1305-460: The Hull–Dobell theorem provides maximum period, it is not sufficient to guarantee a good generator. For example, it is desirable for a  − 1 to not be any more divisible by prime factors of m than necessary. If m is a power of 2, then a  − 1 should be divisible by 4 but not divisible by 8, i.e.  a  ≡ 5 (mod 8). Indeed, most multipliers produce

1350-405: The fact that bits are never affected by higher-order bits, so the low b bits of such a generator form a modulo-2 LCG by themselves, repeating with a period of 2 . Only the most significant bit of X achieves the full period. When c ≠ 0, correctly chosen parameters allow a period equal to m , for all seed values. This will occur if and only if : These three requirements are referred to as

1395-511: The interval [1, 2 − 1] , but in practical applications are often mapped into pseudorandom rationals X j {\displaystyle X_{j}} in the interval (0, 1) , by the formula IBM's RANDU is widely considered to be one of the most ill-conceived random number generators ever designed, and was described as "truly horrible" by Donald Knuth . It fails the spectral test badly for dimensions greater than 2, as shown below. The reason for choosing these particular values for

RANDU - Misplaced Pages Continue

1440-408: The low-order bits when m is chosen to be a power of 2. This can be mitigated by using a modulus larger than the required output, and using the most significant bits of the state. Nevertheless, for some applications LCGs may be a good option. For instance, in an embedded system, the amount of memory available is often severely limited. Similarly, in an environment such as a video game console taking

1485-412: The most significant bit achieves the full period. If a pseudorandom number less than r is desired, ⌊ rX / m ⌋ is a much higher-quality result than X mod r . Unfortunately, most programming languages make the latter much easier to write ( X % r ), so it is very commonly used. The generator is not sensitive to the choice of c , as long as it is relatively prime to the modulus (e.g. if m

1530-496: The most significant bit, in order to limit the output to positive two's complement integers. The output is as if the modulus were one bit less than the internal word size, and such generators are described as such in the table above. LCGs are fast and require minimal memory (one modulo- m number, often 32 or 64 bits) to retain state. This makes them valuable for simulating multiple independent streams. LCGs are not intended, and must not be used, for cryptographic applications; use

1575-409: The most significant bits are usually not computed at all. There are, however, disadvantages. This form has maximal period m /4, achieved if a  ≡ ±3 (mod 8) and the initial state X 0 is odd. Even in this best case, the low three bits of X alternate between two values and thus only contribute one bit to the state. X is always odd (the lowest-order bit never changes), and only one of

1620-465: The multiplier and modulus had been that with a 32-bit-integer word size, the arithmetic of mod 2 and 65539 = 2 16 + 3 {\displaystyle 65539=2^{16}+3} calculations could be done quickly, using bitwise operators in hardware, but the values were chosen for computational convenience, not statistical quality. For any linear congruential generator with modulus m used to generate points in n -dimensional space,

1665-408: The next two bits ever changes. If a  ≡ +3, X alternates ±1↔±3, while if a  ≡ −3, X alternates ±1↔∓3 (all modulo 8). It can be shown that this form is equivalent to a generator with modulus m /4 and c ≠ 0. A more serious issue with the use of a power-of-two modulus is that the low bits have a shorter period than the high bits. Its simplicity of implementation comes from

1710-400: The only criterion, too short a period is a fatal flaw in a pseudorandom number generator. While LCGs are capable of producing pseudorandom numbers which can pass formal tests for randomness , the quality of the output is extremely sensitive to the choice of the parameters m and a . For example, a  = 1 and c  = 1 produces a simple modulo- m counter, which has

1755-426: The points fall in no more than ( n ! × m ) 1 / n {\displaystyle (n!\times m)^{1/n}} parallel hyperplanes. This indicates that low-modulus LCGs are unsuited to high-dimensional Monte Carlo simulation . For m = 2 and n = 3, an LCG could have up to 2344 planes, theoretical maximum. A much tighter upper bound is proved in the same Marsaglia paper to be

1800-423: The recursive relation as which after expanding the quadratic factor becomes (because 2 mod 2 = 0 ) and allows us to show the correlation between three points as Summing the absolute values of the coefficients, we get no more than 16 planes in 3D, becoming only 15 planes on closer examination, as shown in the diagram above. Even by the standards of LCGs, this shows that RANDU is terrible: using RANDU for sampling

1845-414: The resolution of double precision numbers. The choice of the multiplier becomes less important when the modulus is large. It is still necessary to calculate the spectral index and make sure that the multiplier is not a bad one, but purely probabilistically it becomes extremely unlikely to encounter a bad multiplier when the modulus is larger than about 2 . Another flaw specific to LCGs is the short period of

RANDU - Misplaced Pages Continue

1890-474: The same multiplier and modulus are related by In the common case where m is a power of 2 and a  ≡ 5 (mod 8) (a desirable property for other reasons), it is always possible to find an initial value X 0 so that the denominator X 1  −  X 0 ≡ ±1 (mod  m ), producing an even simpler relationship. With this choice of X 0 , X n =  X 0  ±  Y n will remain true for all n . The sign

1935-437: The sum of the absolute values of all the coefficients of the hyperplanes in standard form. That is, if the hyperplanes are of the form Ax 1 + Bx 2 + Cx 3 = some integer such as 0, 1, 2 etc, then the maximum number of planes is | A | + | B | + | C |. Now we examine the values of multiplier 65539 and modulus 2 chosen for RANDU. Consider the following calculation where every term should be taken mod 2. Start by writing

1980-431: The use of this poor LCG. There are three common families of parameter choice: This is the original Lehmer RNG construction. The period is m −1 if the multiplier a is chosen to be a primitive element of the integers modulo m . The initial state must be chosen between 1 and m −1. One disadvantage of a prime modulus is that the modular reduction requires a double-width product and an explicit reduction step. Often

2025-485: Was already detected in 1963 on a 36-bit computer, and carefully reimplemented on the 32-bit IBM System/360 . It was believed to have been widely purged by the early 1990s but there were still FORTRAN compilers using it as late as 1999. The start of the RANDU's output period for the initial seed V 0 = 1 {\displaystyle V_{0}=1} is Linear congruential generator The generator

#894105