20:
2588:
2652:
3597:
2666:
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
2562:
implementation operates with 48-bit values at each iteration but returns only their 32 most significant bits. This 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
2738:
The plane spacing depends both on the modulus and the multiplier. A large enough modulus can reduce this distance below 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
2761:
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
2753:
taking 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,
2694:
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 a period longer than the square of the number of outputs required. Given modern computer speeds, this means a
3227:
Like all pseudorandom number generators, 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
1621:
806:= 2, produces a particularly efficient LCG, because this allows the modulus operation to be computed by simply truncating the binary representation. In fact, the most significant bits are usually not computed at all. There are, however, disadvantages.
862:
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 the fact that bits are never affected by higher-order bits, so the low
1411:
419:
A benefit of LCGs is that an appropriate choice of parameters results in a period which is both known and long. Although not the only criterion, too short a period is a fatal flaw in a pseudorandom number generator.
3251:, 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 a single LCG with a modulus equal to the product of the component LCG moduli.
4201:
uses a simple (single state) linear congruential generator only in case that the state is declared as 8 bytes. If the state is larger (an array), the generator becomes an additive feedback generator (
2644:
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 a
154:
2749:
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
1110:
Indeed, most multipliers produce 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
1430:
3633:
these denominations, by now used for half a century, are completely wrong from a mathematical viewpoint.... At this point it is unlikely that the now-traditional names will be corrected.
524:
One disadvantage of a prime modulus is that the modular reduction requires a double-width product and an explicit reduction step. Often a prime just less than a power of 2 is used (the
358:
2419:
2739:
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.
2563:
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.
303:
262:
764:. Thus, both products can be computed with a single-width product, and the difference between them lies in the range , so can be reduced to with a single conditional add.
217:
23:
Two modulo-9 LCGs show how different parameters lead to different cycle lengths. Each row shows the state evolving until it repeats. The top row shows a generator with
3473:
A powerful technique for generating high-quality pseudorandom numbers is to combine two or more PRNGs of different structure; the sum of an LFSR and an LCG (as in the
35: = 0, and a seed of 1, which produces a cycle of length 6. The second row is the same generator with a seed of 3, which produces a cycle of length 2. Using
2566:
Contrarily, some libraries use an implicit power-of-two modulus but never output or otherwise use the most significant bit, in order to limit the output to positive
1125:
bits form a generator with modulus 2 and thus repeat with a period of 2; only the most significant bit achieves the full period. If a pseudorandom number less than
1019:
967:
3346:. These have the advantage that all of their bits are full-period; they do not suffer from the weakness in the low-order bits that plagues arithmetic modulo 2.
67:
algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide
3236:
There are several generators which are linear congruential generators in a different form, and thus the techniques used to analyze LCGs can be applied to them.
1039:
991:
939:
919:
177:
2645:
4708:
2746:
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.
1252:
2558:
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
2762:
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.
3364:
It is easy to detect the structure of a linear-feedback shift register with appropriate tests such as the linear complexity test implemented in the
3875:
In a sense it is unfortunate that this test for full period is so trivial as it falsely encourages non-specialists to build their own generators.
2605:
1770: = 3. Because 3 ≡ −1 (mod 4), we are searching for a solution to 1 + 3 ≡ (1 − 157)
477:, which was widely used in the early 1970s and led to many results which are currently being questioned because of the use of this poor LCG.
4519:
3361:
also fall into this category; although they use arithmetic addition, their period is ensured by an LFSR among the least-significant bits.
411:
The Lehmer generator was published in 1951 and the Linear congruential generator was published in 1958 by W. E. Thomson and A. Rotenberg.
3314:
begins with a power-of-2-modulus LCG and applies an output transformation to eliminate the short period problem in the low-order bits.
2932:
based on the information in the table above. Given the same RandSeed value it generates the same sequence of random numbers as Delphi.
4549:
4396:
3387:
Another structure for a PRNG is a very simple recurrence function combined with a powerful output mixing function. This includes
4955:
3955:
3528:
4919:
4914:
4812:
84:
4824:
4691:
4156:
4027:
3739:
L'Ecuyer, Pierre (13 July 2017). Chan, W. K. V.; D'Ambrogio, A.; Zacharewicz, G.; Mustafee, N.; Wainer, G.; Page, E. (eds.).
4897:(in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).
4223:
4281:
Dohmann, Birgit; Falk, Michael; Lessenich, Karin (August 1991). "The random number generators of the Turbo Pascal family".
867:
bits of such a generator form a modulo-2 LCG by themselves, repeating with a period of 2. Only the most significant bit of
1634: ≡ 5 (mod 8) (a desirable property for other reasons), it is always possible to find an initial value
4090:
2574:
the modulus were one bit less than the internal word size, and such generators are described as such in the table above.
775:
to uniform random bits. If a prime just less than a power of 2 is used, sometimes the missing values are simply ignored.
4374:
4202:
4190:
2698:
One flaw specific to LCGs is that, if used to choose points in an n-dimensional space, the points will lie on, at most,
4852:
4418:
2627:
1616:{\displaystyle {X_{n}-X_{0} \over X_{1}-X_{0}}=Y_{n}={a^{n}-1 \over a-1}={Z_{n}-Z_{0} \over Z_{1}-Z_{0}}{\pmod {m}}.}
4308:
3512:
3490:
2780:
2731:. Carelessly chosen multipliers will usually have far fewer, widely spaced planes, which can lead to problems. The
510:
3239:
One method of producing a longer period is to sum the outputs of several LCGs of different periods having a large
4777:
4749:
3568:
3502:
3381:
3311:
4925:
The "Death of Art" computer art project at
Goldstein Technologies LLC, uses an LCG to generate 33,554,432 images
2928:
as its default pseudo random number generator whereas Delphi uses a LCG. Here is a Delphi compatible example in
3323:
2735:, which is a simple test of an LCG's quality, measures this spacing and allows a good multiplier to be chosen.
2609:
496:
4940:
3357:. The latter provides a very long period (2−1) and variate uniformity, but it fails some statistical tests.
310:
2776:
2757:
LCGs should be evaluated very carefully for suitability in non-cryptographic applications where high-quality
2390:
64:
4000:
3740:
3499:– not to be confused with ACG which term appears to have been used for variants of LCG and LFSR generators
4960:
4604:
2559:
2340:
1076:), which makes a very poor PRNG; a selection of possible full-period multipliers is only available when
832:
is always odd (the lowest-order bit never changes), and only one of the next two bits ever changes. If
4577:
PCG: A Family of Simple Fast Space-Efficient
Statistically Good Algorithms for Random Number Generation
3963:
3358:
269:
3849:
3339:
2039:
2035:
228:
60:
4728:
2674:
For a specific example, an ideal random number generator with 32 bits of output is expected (by the
4450:
4234:
3985:
3908:
3598:"Computationally easy, spectrally good multipliers for congruential pseudorandom number generators"
4683:
3376:
greater than the degree of the polynomial. Adding a non-linear output mixing function (as in the
4173:
2598:
1986:
4930:
4634:
On the
Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators
4490:
2695:
period of 2 for all but the least demanding applications, and longer for demanding simulations.
473:
have led to ineffective implementations of LCGs. A particularly illustrative example of this is
189:
4911:
visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
4723:
4516:
4334:
4229:
4069:
4044:
3980:
3903:
2717:
4767:
4709:"Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator"
3748:. Proceedings of the 2017 Winter Simulation Conference (to appear). Las Vegas, United States.
1083:
Although the Hull–Dobell theorem provides maximum period, it is not sufficient to guarantee a
19:
3373:
3240:
400:
396:
4675:
4575:
4341:
are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied
4256:
4791:
4105:
3972:
3787:
428:
424:
8:
4676:
4584:
3517:
3292:
3258:
2567:
1065:
998:
946:
75:
4908:
4109:
3976:
3956:"Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure"
3791:
3322:
The other widely used primitive for obtaining long-period pseudorandom sequences is the
4888:
4871:
4741:
4652:
4600:"On the adequacy of pseudo-random number generators (or: How big a period do we need?)"
3921:
3866:
3721:
3612:
3571:. Vol. 2 (3rd ed.). Reading, MA: Addison-Wesley Professional. pp. 10–26.
2750:
1024:
976:
924:
904:
162:
68:
3841:
3810:
4848:
4820:
4687:
4617:
4294:
4152:
4023:
4017:
3870:
3815:
3589:
3244:
2010:
1930:
3925:
3725:
1406:{\displaystyle X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.}
59:
that yields a sequence of pseudo-randomized numbers calculated with a discontinuous
4892:
4880:
4830:
4781:
4745:
4733:
4671:
4613:
4535:
4290:
4121:
4113:
3990:
3913:
3858:
3805:
3795:
3766:
3711:
3678:
3622:
3593:
3474:
3369:
3354:
3254:
2925:
2721:
2675:
2658:
of a linear congruential generator in three dimensions. This structure is what the
1851:
The following table lists the parameters of LCGs in common use, including built-in
1151:. Unfortunately, most programming languages make the latter much easier to write (
431:, the quality of the output is extremely sensitive to the choice of the parameters
220:
4863:
3994:
3650:
Lehmer, Derrick H. (1951). "Mathematical methods in large-scale computing units".
2667:
stringent statistical tests; a modulo-2 LCG which returns the high 32 bits passes
574:
If a double-width product is unavailable, and the multiplier is chosen carefully,
4523:
4503:
4477:
4464:
3889:"A Portable Uniform Random Number Generator Well Suited for the Rejection Method"
3327:
2027:
1856:
4794:
4771:
4351:
3770:
3377:
2671:'s SmallCrush suite, and a 96-bit LCG passes the most stringent BigCrush suite.
451:
counter, which has a long period, but is obviously non-random. Other values of
4632:
4599:
2724:). This is due to serial correlation between successive values of the sequence
2062:
2058:
895:
767:
A second disadvantage is that it is awkward to convert the value 1 ≤
525:
4225:
A collection of selected pseudorandom number generators with linear structures
4949:
4338:
3343:
3334:. Rather than integer addition and multiplication, the basic operations are
3247:
generator is an example of this form. (We would prefer them to be completely
3228:
avoid equal sequences of random numbers on simultaneously executing threads.
2742:
Another flaw specific to LCGs is the short period of the low-order bits when
2732:
2659:
2022:
1111:
828:
alternate between two values and thus only contribute one bit to the state.
463:
4045:"Computer Systems Performance Analysis Chapter 26: Random-Number Generation"
3888:
3683:
3666:
4766:
Eastlake, Donald E. 3rd; Schiller, Jeffrey I.; Crocker, Steve (June 2005).
4209:
3819:
3560:
3496:
3388:
3335:
2254:
2139:
2112:
2084:
2014:
1056:
with many repeated prime factors, such as a power of 2; using a computer's
970:
795:
4737:
4337:, RtlUniform uses LCG, and not Lehmer's algorithm, implementations before
3917:
3716:
3699:
3478:
1103: − 1 should be divisible by 4 but not divisible by 8, i.e.
4660:. Proceedings of the 1992 Winter Simulation Conference. pp. 443–447.
4312:
3800:
3652:
Proceedings of 2nd
Symposium on Large-Scale Digital Calculating Machinery
3384:
constructions) can greatly improve the performance on statistical tests.
2929:
2713:
2018:
1117:
Note that a power-of-2 modulus shares the problem as described above for
851:
It can be shown that this form is equivalent to a generator with modulus
559:
if the result is too large, but the number of subtractions is limited to
4931:"TestU01: A C Library for Empirical Testing of Random Number Generators"
4884:
3862:
43: = 1 (bottom row) gives a cycle length of 9 with any seed in .
4924:
4859:
4309:"How Visual Basic Generates Pseudo-Random Numbers for the RND Function"
3522:
3507:
3466: ≥ 2. With a prime modulus, this can generate periods up to
3392:
2758:
2655:
2612: in this section. Unsourced material may be challenged and removed.
2571:
2167:
377:
4786:
4126:
3627:
3470:−1, so is a useful extension of the LCG structure to larger periods.
2193:
1057:
1045:
These three requirements are referred to as the Hull–Dobell
Theorem.
56:
4117:
3749:
2587:
4198:
3617:
3350:
1860:
1784: ≡ 41 (mod 64), so if we start with that, then
180:
3939:, produces random numbers with a bad one-dimensional distribution.
3667:"A Modified Congruence Method of Generating Pseudo-random Numbers"
2866:"""Linear congruential generator."""
4864:"Inferring sequences produced by pseudo-random number generators"
3637:
3365:
3248:
2668:
2310:
2224:
2197:
2089:
1955:
455:
365:
4810:
4019:
Numerical
Recipes in Fortran 77: The Art of Scientific Computing
1659:), producing an even simpler relationship. With this choice of
1091: − 1 to not be any more divisible by prime factors of
4915:
Security of Random Number
Generation: An Annotated Bibliography
4811:
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007),
3493:– other PRNGs including some with better statistical qualitites
2272:
2243:
2217:
2006:
403:
one, but the misnomer is well-established in computer science.
4654:
Analysis of Add-with-Carry and
Subtract-with-Borrow Generators
4193:
See the code after the test for "TYPE_0"; the GNU C library's
1863:. This table is to show popularity, not examples to emulate;
466:, which is better distributed but still obviously non-random.
4476:
Stephen J. Chapman. "Example 6.4 – Random Number
Generator".
4463:
Stephen J. Chapman. "Example 6.4 – Random Number
Generator".
3372:
initialized from consecutive bits of an LFSR will never have
3331:
2538:
2429:
2425:
2348:
2344:
2318:
1982:
474:
395: ≠ 0, a mathematician would call the recurrence an
137:
1166:, as long as it is relatively prime to the modulus (e.g. if
501:
This is the original Lehmer RNG construction. The period is
3778:
2529:
previously bits 31..16, current bits 31..16 xor bits 14..0
2507:
2480:
2453:
2291:
2250:
1910:
3326:
construction, which is based on arithmetic in GF(2), the
2651:
2031:
1185:
can be written as a simple function of the sequence when
890:≠ 0, correctly chosen parameters allow a period equal to
63:. The method represents one of the oldest and best-known
715: ≤ 1), then the second term is also less than
555:. This must be followed by a conditional subtraction of
149:{\displaystyle X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}}
4765:
3481:
constructions) can do very well at some cost in speed.
3391:
block ciphers and non-cryptographic generators such as
824:
is odd. Even in this best case, the low three bits of
528:
2−1 and 2−1 are popular), so that the reduction modulo
4819:(3rd ed.), New York: Cambridge University Press,
4682:(First ed.). Cambridge University Press. p.
4212:
that reproduces the random sequence from this library.
3842:"Random Number Generators: Good Ones Are Hard To Find"
2646:
cryptographically secure pseudorandom number generator
4707:
Matsumoto, Makoto; Nishimura, Takuji (January 1998).
3299:
are equivalent to LCGs with a large prime modulus of
2640:
LCGs are fast and require minimal memory (one modulo-
2393:
1433:
1255:
1027:
1001:
979:
949:
927:
907:
480:
There are three common families of parameter choice:
313:
272:
231:
192:
165:
87:
4716:
ACM Transactions on Modeling and Computer Simulation
4640:. Workshop on Stochastic Numerics. Kyoto University.
4478:"MATLAB Programming with Applications for Engineers"
4280:
1937:, Chapter 7.1, §An Even Quicker Generator, Eq. 7.1.6
1695: ≡ ±1 (mod 4), and the constant
1424:
with the same multiplier and modulus are related by
3840:Park, Stephen K.; Miller, Keith W. (October 1988).
1217: + 1 mod m, then a general sequence
4817:Numerical Recipes: The Art of Scientific Computing
4706:
4650:
4630:
2413:
1615:
1405:
1033:
1013:
985:
961:
933:
913:
352:
297:
256:
211:
171:
148:
16:Algorithm for generating pseudo-randomized numbers
4517:"'Module': A Major Feature of the Modern Fortran"
4397:"Creating and Controlling a Random Number Stream"
4257:"Last public Committee Draft from April 12, 2011"
3886:
3402:equivalent, is the multiple-recursive generator:
517:. The initial state must be chosen between 1 and
4947:
4845:Random Number Generation and Monte Carlo Methods
3342:, which is usually implemented as a sequence of
2775:The following is an implementation of an LCG in
372: = 0, the generator is often called a
4920:Linear Congruential Generators post to sci.math
4651:Tezuka, Shi; L'Ecuyer, Pierre (December 1992).
3887:Hörmann, Wolfgang; Derflinger, Gerhard (1993).
2754:will produce alternately odd and even results.
2577:
4631:Tezuka, Shu; L'Ecuyer, Pierre (October 1993).
4591:
3317:
817: ≡ ±3 (mod 8) and the initial state
3761:
3759:
2678:) to begin duplicating earlier outputs after
1724:As a simple example, consider the generators
1087:generator. For example, it is desirable for
4597:
4283:Computational Statistics & Data Analysis
3953:
3949:
3947:
3738:
1777: (mod 256). This is satisfied by
4670:
4573:
4352:"WINE source identifier search: RtlUniform"
4221:
3742:History of Uniform Random Number Generation
3588:
3281:) are equivalent to LCGs with a modulus of
1846:
1842:mod 256 = 233, 233, 233, 233, 233, 233, ...
4858:
4674:(1999). "Section 5.3.2: Linear Feedback".
4536:The Open Group Base Specifications Issue 7
4165:
4151:. John Wiley & Sons, Ltd. p. 86.
4140:
4088:
3839:
3771:"Random Numbers Fall Mainly in the Planes"
3756:
3584:
3582:
3580:
3578:
1181:The sequence produced by other choices of
4941:Article about another way of cracking LCG
4935:ACM Transactions on Mathematical Software
4785:
4727:
4598:Heath, David; Sanchez, Paul (June 1986).
4311:. Microsoft. 24 June 2004. Archived from
4233:
4146:
4125:
3984:
3944:
3907:
3896:ACM Transactions on Mathematical Software
3809:
3799:
3765:
3715:
3697:
3682:
3626:
3616:
3555:
3553:
3551:
3549:
3547:
3545:
3543:
2628:Learn how and when to remove this message
1867:Tables of good parameters are available.
368:constants that specify the generator. If
327:
279:
238:
199:
4574:O'Neill, Melissa E. (5 September 2014).
4369:
4367:
4174:"Random Numbers: Nothing Left to Chance"
4089:Hull, T. E.; Dobell, A. R. (July 1962).
4011:
4009:
3880:
3835:
3833:
3831:
3829:
2650:
1242:can be written as an affine function of
1193:is the prototypical sequence defined by
874:
778:
567:, which can be easily limited to one if
447: = 1 produces a simple modulo-
353:{\displaystyle X_{0},\,0\leq X_{0}<m}
18:
4759:
4067:
4016:Press, William H.; et al. (1992).
3664:
3575:
2448:bits 47..0 or bits 47..15, as required
2414:{\displaystyle {\frac {X_{n}}{134456}}}
2204:, MATLAB's v4 legacy generator mcg16807
894:, for all seed values. This will occur
683:, the first term is strictly less than
384: ≠ 0, the method is called a
4948:
4171:
3732:
3700:"A New Pseudo-Random Number Generator"
3649:
3540:
3529:Combined linear congruential generator
3525:(sometimes called the Park–Miller RNG)
4768:"Traditional Pseudo-random Sequences"
4451:"GNU Scientific Library: gsl_rng_vax"
4364:
4191:Implementation in glibc-2.26 release.
4015:
4006:
3826:
3559:
2946:{$ ifdef fpc}{$ mode delphi}{$ endif}
1939:parameters from Knuth and H. W. Lewis
1143:is a much higher-quality result than
374:multiplicative congruential generator
4773:Randomness Requirements for Security
4208:) and the period increases. See the
4042:
2610:adding citations to reliable sources
2581:
2286:bits 62..32 (46..32 for 16-bit int)
1114:is one of the most important tests.
423:While LCGs are capable of producing
4933:, May 2006, revised November 2006,
4678:The Nature of Mathematical Modeling
4068:Fenerty, Paul (11 September 2006).
1602:
1392:
13:
4465:"MATLAB Programming for Engineers"
3231:
2038:: Suggestion in the ISO/IEC 9899,
1865:many of these parameters are poor.
1758: + 1 mod 256; i.e.
1416:More generally, any two sequences
1107: ≡ 5 (mod 8).
14:
4972:
4937:, 33, 4, Article 22, August 2007.
4901:
4587:. pp. 6–7. HMC-CS-2014-0905.
4547:
3954:L'Ecuyer, Pierre (January 1999).
3605:Software: Practice and Experience
3398:A structure similar to LCGs, but
848:alternates ±1↔∓3 (all modulo 8).
483:
4180:. American Mathematical Society.
3636:Associated software and data at
3513:Inversive congruential generator
3491:List of random number generators
3349:Examples of this family include
2586:
1741: + 3 mod 256 and
1155:), so it is very commonly used.
578:may be used. To do this, factor
414:
298:{\displaystyle c,\,0\leq c<m}
74:The generator is defined by the
4700:
4664:
4644:
4624:
4567:
4541:
4529:
4509:
4504:"Introduction to Fortran 90/95"
4496:
4483:
4470:
4457:
4443:
4411:
4389:
4344:
4327:
4301:
4274:
4249:
4215:
4184:
4082:
4061:
4036:
3930:a multiplier about as small as
3569:The Art of Computer Programming
3503:Permuted congruential generator
3382:permuted congruential generator
3312:permuted congruential generator
3303:−1 and a power-of-2 multiplier
2597:needs additional citations for
1832:= 0, 1, 158, 231, 172, 125, ...
1826:= 233, 232, 75, 2, 61, 108, ...
1702:is determined by 1 ∓
1595:
1385:
1060:is the most common choice. If
1048:This form may be used with any
469:Historically, poor choices for
257:{\displaystyle a,\,0<a<m}
4956:Pseudorandom number generators
4222:K. Entacher (21 August 1997).
4149:System Modeling and Simulation
3691:
3658:
3643:
3638:https://github.com/vigna/CPRNG
3324:linear-feedback shift register
2919:
2770:
2765:
1606:
1596:
1396:
1386:
1358:
1332:
1303:
1294:
1282:
1269:
540: mod 2) +
497:Lehmer random number generator
1:
4909:Linear Congruential Generator
4813:"Section 7.1.1. Some History"
4804:
4538:IEEE Std 1003.1, 2013 Edition
4427:—pseudo-random numbers"
4333:In spite of documentation on
4022:(2nd ed.). p. 268.
3995:10.1090/S0025-5718-99-00996-5
1805: (mod 256) for all
809:This form has maximal period
360:— the "seed" or "start value"
183:of pseudo-random values, and
65:pseudorandom number generator
49:linear congruential generator
4618:10.1016/0167-6377(86)90092-1
4295:10.1016/0167-9473(91)90108-E
4172:Austin, David (March 2008).
2578:Advantages and disadvantages
2113:Microsoft Visual/Quick C/C++
1706: ≡ (1 −
1691:. The sign is determined by
1080:has repeated prime factors.
386:mixed congruential generator
7:
4929:P. L'Ecuyer and R. Simard,
4605:Operations Research Letters
3484:
3359:Lagged Fibonacci generators
3318:Comparison with other PRNGs
3295:PRNGs with a multiplier of
1174:must be odd), so the value
1162:sensitive to the choice of
840:alternates ±1↔±3, while if
532: = 2 −
71:by storage-bit truncation.
10:
4977:
4843:Gentle, James E., (2003).
4091:"Random Number Generators"
3964:Mathematics of Computation
3261:PRNGs with a word size of
1052:, but only works well for
871:achieves the full period.
494:
406:
212:{\displaystyle m,\,0<m}
4847:, 2nd edition, Springer,
4147:Severance, Frank (2001).
4043:Jain, Raj (9 July 2010).
3850:Communications of the ACM
3340:carry-less multiplication
2570:integers. The output is
1687:will remain true for all
1655:≡ ±1 (mod
1626:In the common case where
1072: ≡ 1 (mod
61:piecewise linear equation
3565:Seminumerical Algorithms
3534:
2934:
2785:
1847:Parameters in common use
1819:= 233 = 3×64 + 41:
1641:so that the denominator
1121: = 0: the low
1068:, this would only allow
4377:. ISO. 2 September 2011
3665:Thomson, W. E. (1958).
2648:for such applications.
1897:output bits of seed in
1178:=1 is commonly chosen.
513:of the integers modulo
3698:Rotenberg, A. (1960).
3257:'s add-with-carry and
2663:
2438:25214903917 (5DEECE66D
2415:
2357:25214903917 (5DEECE66D
2140:Microsoft Visual Basic
1766: = 157, and
1617:
1407:
1189:=1. Specifically, if
1170:is a power of 2, then
1099:is a power of 2, then
1035:
1015:
987:
963:
935:
915:
427:which can pass formal
354:
299:
258:
213:
173:
150:
44:
4738:10.1145/272991.272995
4431:Newlib git repository
3918:10.1145/168173.168414
3717:10.1145/321008.321019
3684:10.1093/comjnl/1.2.83
3241:least common multiple
2654:
2416:
2343:'s java.util.Random,
1618:
1408:
1036:
1021:is divisible by 4 if
1016:
988:
964:
936:
916:
505:−1 if the multiplier
397:affine transformation
355:
300:
259:
214:
174:
151:
22:
4583:(Technical report).
4506:. 1998. pp. 322–324.
4502:Stephen J. Chapman.
4480:. 2012. pp. 292–295.
4467:. 2015. pp. 253–256.
4375:"ISO/IEC 14882:2011"
3999:Be sure to read the
3801:10.1073/pnas.61.1.25
3671:The Computer Journal
3259:subtract-with-borrow
3135:2.32830643653870e-10
2606:improve this article
2522:3014898611 (B3B3B3B3
2391:
1630:is a power of 2 and
1431:
1253:
1095:than necessary. If
1025:
999:
977:
969:is divisible by all
947:
925:
905:
536:can be computed as (
429:tests for randomness
425:pseudorandom numbers
311:
270:
229:
190:
163:
85:
4885:10.1145/58562.59305
4780:. sec. 6.1.3.
4585:Harvey Mudd College
4110:1962SIAMR...4..230H
3977:1999MaCom..68..249L
3863:10.1145/63039.63042
3792:1968PNAS...61...25M
3518:Multiply-with-carry
3441: + ··· +
3353:generators and the
3293:Multiply-with-carry
2924:Free Pascal uses a
2779:, in the form of a
2718:Marsaglia's theorem
2495:826366247 (31415927
2299:6364136223846793005
2280:6364136223846793005
2265:1442695040888963407
2262:6364136223846793005
2182:−60 (7FFFFFC3
2175:−18 (7FFFFFED
1812:For example, using
1066:square-free integer
1014:{\displaystyle a-1}
962:{\displaystyle a-1}
443: = 1 and
76:recurrence relation
39: = 4 and
4961:Modular arithmetic
4872:Journal of the ACM
4522:2021-02-24 at the
4203:initialized using
4070:"Schrage's Method"
3769:(September 1968).
3704:Journal of the ACM
3596:(February 2022) .
3590:Steele, Guy L. Jr.
2751:video game console
2664:
2411:
2317:, old versions of
2098:134775813 (8088405
1762: = 256,
1613:
1403:
1041:is divisible by 4.
1031:
1011:
983:
959:
931:
911:
699:is chosen so that
509:is chosen to be a
350:
295:
264:— the "multiplier"
254:
209:
169:
146:
69:modular arithmetic
45:
4826:978-0-521-88068-8
4693:978-0-521-57095-4
4672:Gershenfeld, Neil
4158:978-0-471-49694-6
4029:978-0-521-43064-7
3857:(10): 1192–1201.
3767:Marsaglia, George
3594:Vigna, Sebastiano
3368:suite; a boolean
2638:
2637:
2630:
2556:
2555:
2515:16843009 (1010101
2488:16843009 (1010101
2409:
1931:Numerical Recipes
1857:runtime libraries
1592:
1535:
1486:
1158:The generator is
1034:{\displaystyle m}
986:{\displaystyle m}
934:{\displaystyle c}
914:{\displaystyle m}
844: ≡ −3,
836: ≡ +3,
511:primitive element
305:— the "increment"
172:{\displaystyle X}
4968:
4896:
4868:
4840:
4839:
4838:
4829:, archived from
4799:
4798:
4789:
4787:10.17487/RFC4086
4763:
4757:
4756:
4754:
4748:. Archived from
4731:
4713:
4704:
4698:
4697:
4681:
4668:
4662:
4661:
4659:
4648:
4642:
4641:
4639:
4628:
4622:
4621:
4595:
4589:
4588:
4582:
4571:
4565:
4564:
4562:
4560:
4545:
4539:
4533:
4527:
4513:
4507:
4500:
4494:
4487:
4481:
4474:
4468:
4461:
4455:
4454:
4447:
4441:
4440:
4438:
4437:
4426:
4422:
4415:
4409:
4408:
4406:
4404:
4393:
4387:
4386:
4384:
4382:
4371:
4362:
4361:
4359:
4358:
4348:
4342:
4331:
4325:
4324:
4322:
4320:
4315:on 17 April 2011
4305:
4299:
4298:
4278:
4272:
4271:
4269:
4267:
4261:
4253:
4247:
4246:
4244:
4242:
4237:
4219:
4213:
4188:
4182:
4181:
4169:
4163:
4162:
4144:
4138:
4137:
4135:
4134:
4129:
4095:
4086:
4080:
4079:
4077:
4076:
4065:
4059:
4058:
4056:
4055:
4050:. pp. 19–20
4049:
4040:
4034:
4033:
4013:
4004:
3998:
3988:
3971:(225): 249–260.
3960:
3951:
3942:
3941:
3938:
3937:
3911:
3893:
3884:
3878:
3877:
3846:
3837:
3824:
3823:
3813:
3803:
3775:
3763:
3754:
3753:
3747:
3736:
3730:
3729:
3719:
3695:
3689:
3688:
3686:
3662:
3656:
3655:
3647:
3641:
3635:
3630:
3628:10.1002/spe.3030
3620:
3602:
3586:
3573:
3572:
3557:
3370:circulant matrix
3355:Mersenne twister
3289: ± 1.
3277: >
3223:
3220:
3217:
3214:
3211:
3208:
3205:
3202:
3199:
3196:
3193:
3190:
3187:
3184:
3181:
3178:
3175:
3172:
3169:
3166:
3163:
3160:
3157:
3154:
3151:
3148:
3145:
3142:
3139:
3136:
3133:
3130:
3127:
3124:
3121:
3118:
3115:
3112:
3109:
3106:
3103:
3100:
3097:
3094:
3091:
3088:
3085:
3082:
3079:
3076:
3073:
3070:
3067:
3064:
3061:
3058:
3055:
3052:
3049:
3046:
3043:
3040:
3037:
3034:
3031:
3028:
3025:
3022:
3019:
3016:
3013:
3010:
3007:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2974:
2971:
2968:
2965:
2962:
2959:
2956:
2953:
2950:
2947:
2944:
2941:
2938:
2926:Mersenne Twister
2915:
2912:
2909:
2906:
2903:
2900:
2897:
2894:
2891:
2888:
2885:
2882:
2879:
2876:
2873:
2870:
2867:
2864:
2861:
2858:
2855:
2852:
2849:
2846:
2843:
2840:
2837:
2834:
2831:
2828:
2825:
2822:
2819:
2816:
2813:
2810:
2807:
2804:
2801:
2798:
2795:
2792:
2789:
2722:George Marsaglia
2712:
2711:
2710:
2689:
2687:
2686:
2676:Birthday theorem
2633:
2626:
2622:
2619:
2613:
2590:
2582:
2568:two's complement
2541:
2535:Formerly common:
2420:
2418:
2417:
2412:
2410:
2405:
2404:
2395:
2375:
2230:
2203:
2166:RtlUniform from
2155:12820163 (C39EC3
2148:16598013 (FD43FD
1936:
1870:
1869:
1717: (mod
1622:
1620:
1619:
1614:
1609:
1593:
1591:
1590:
1589:
1577:
1576:
1566:
1565:
1564:
1552:
1551:
1541:
1536:
1534:
1523:
1516:
1515:
1505:
1500:
1499:
1487:
1485:
1484:
1483:
1471:
1470:
1460:
1459:
1458:
1446:
1445:
1435:
1412:
1410:
1409:
1404:
1399:
1383:
1382:
1370:
1369:
1357:
1356:
1344:
1343:
1328:
1327:
1315:
1314:
1281:
1280:
1265:
1264:
1154:
1142:
1132:
1040:
1038:
1037:
1032:
1020:
1018:
1017:
1012:
992:
990:
989:
984:
968:
966:
965:
960:
940:
938:
937:
932:
920:
918:
917:
912:
813:/4, achieved if
771: <
735:
725:
662:
661:
651:
623:
609:
608:
598:
576:Schrage's method
554:
547:
439:. For example,
359:
357:
356:
351:
343:
342:
323:
322:
304:
302:
301:
296:
263:
261:
260:
255:
218:
216:
215:
210:
178:
176:
175:
170:
155:
153:
152:
147:
145:
144:
135:
131:
124:
123:
103:
102:
31: = 2,
27: = 9,
4976:
4975:
4971:
4970:
4969:
4967:
4966:
4965:
4946:
4945:
4907:The simulation
4904:
4866:
4836:
4834:
4827:
4807:
4802:
4790:. BCP 106.
4764:
4760:
4752:
4729:10.1.1.215.1141
4711:
4705:
4701:
4694:
4669:
4665:
4657:
4649:
4645:
4637:
4629:
4625:
4596:
4592:
4580:
4572:
4568:
4558:
4556:
4548:Cadot, Sidney.
4546:
4542:
4534:
4530:
4524:Wayback Machine
4514:
4510:
4501:
4497:
4489:S. J. Chapman.
4488:
4484:
4475:
4471:
4462:
4458:
4449:
4448:
4444:
4435:
4433:
4424:
4420:
4417:
4416:
4412:
4402:
4400:
4395:
4394:
4390:
4380:
4378:
4373:
4372:
4365:
4356:
4354:
4350:
4349:
4345:
4332:
4328:
4318:
4316:
4307:
4306:
4302:
4279:
4275:
4265:
4263:
4259:
4255:
4254:
4250:
4240:
4238:
4220:
4216:
4210:simplified code
4189:
4185:
4170:
4166:
4159:
4145:
4141:
4132:
4130:
4118:10.1137/1004061
4093:
4087:
4083:
4074:
4072:
4066:
4062:
4053:
4051:
4047:
4041:
4037:
4030:
4014:
4007:
3958:
3952:
3945:
3933:
3931:
3891:
3885:
3881:
3844:
3838:
3827:
3773:
3764:
3757:
3745:
3737:
3733:
3696:
3692:
3663:
3659:
3648:
3644:
3600:
3587:
3576:
3558:
3541:
3537:
3497:ACORN generator
3487:
3457:
3446:
3440:
3431:
3424:
3415:
3407:
3328:polynomial ring
3320:
3234:
3232:LCG derivatives
3225:
3224:
3221:
3218:
3215:
3212:
3209:
3206:
3203:
3200:
3197:
3194:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3161:
3158:
3155:
3152:
3149:
3146:
3143:
3140:
3137:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3089:
3086:
3083:
3080:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3056:
3053:
3050:
3047:
3044:
3041:
3038:
3035:
3032:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2999:
2996:
2993:
2990:
2987:
2984:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2922:
2917:
2916:
2913:
2910:
2907:
2904:
2901:
2898:
2895:
2892:
2889:
2886:
2883:
2880:
2877:
2874:
2871:
2868:
2865:
2862:
2859:
2856:
2853:
2850:
2847:
2844:
2841:
2838:
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2808:
2805:
2802:
2799:
2796:
2793:
2791:collections.abc
2790:
2787:
2773:
2768:
2729:
2720:, developed by
2702:
2700:
2699:
2682:
2680:
2679:
2634:
2623:
2617:
2614:
2603:
2591:
2580:
2537:
2525:
2518:
2498:
2491:
2471:
2468:4282663 (415927
2464:
2441:
2400:
2396:
2394:
2392:
2389:
2388:
2373:
2360:
2329:
2228:
2201:
2194:Apple CarbonLib
2185:
2178:
2158:
2151:
2142:(6 and earlier)
2130:
2127:2531011 (269EC3
2123:
2101:
2076:bits 63..32 of
2026:
1970:bits 30..16 in
1938:
1934:
1891:
1884:
1877:
1849:
1818:
1803:
1797:
1789:
1783:
1776:
1756:
1750:
1739:
1733:
1716:
1701:
1685:
1679:
1671:
1665:
1654:
1647:
1640:
1594:
1585:
1581:
1572:
1568:
1567:
1560:
1556:
1547:
1543:
1542:
1540:
1524:
1511:
1507:
1506:
1504:
1495:
1491:
1479:
1475:
1466:
1462:
1461:
1454:
1450:
1441:
1437:
1436:
1434:
1432:
1429:
1428:
1384:
1378:
1374:
1365:
1361:
1352:
1348:
1339:
1335:
1323:
1319:
1310:
1306:
1276:
1272:
1260:
1256:
1254:
1251:
1250:
1232:
1226:
1215:
1209:
1199:
1152:
1140:
1130:
1026:
1023:
1022:
1000:
997:
996:
978:
975:
974:
948:
945:
944:
926:
923:
922:
906:
903:
902:
884:
823:
788:
733:
723:
667: mod
659:
649:
633:
628: mod
624:. Then compute
611:
606:
596:
591:
552:
545:
526:Mersenne primes
499:
493:
417:
409:
338:
334:
318:
314:
312:
309:
308:
271:
268:
267:
230:
227:
226:
191:
188:
187:
164:
161:
160:
140:
136:
119:
115:
111:
107:
92:
88:
86:
83:
82:
17:
12:
11:
5:
4974:
4964:
4963:
4958:
4944:
4943:
4938:
4927:
4922:
4917:
4912:
4903:
4902:External links
4900:
4899:
4898:
4879:(1): 129–141.
4856:
4841:
4825:
4806:
4803:
4801:
4800:
4758:
4755:on 2017-11-07.
4699:
4692:
4663:
4643:
4623:
4590:
4566:
4540:
4528:
4515:Wu-ting Tsai.
4508:
4495:
4482:
4469:
4456:
4442:
4410:
4388:
4363:
4343:
4326:
4300:
4289:(1): 129–132.
4273:
4262:. p. 346f
4248:
4235:10.1.1.53.3686
4214:
4183:
4178:Feature Column
4164:
4157:
4139:
4104:(3): 230–254.
4081:
4060:
4035:
4028:
4005:
3986:10.1.1.34.1024
3943:
3909:10.1.1.52.3811
3902:(4): 489–495.
3879:
3825:
3755:
3731:
3690:
3657:
3642:
3611:(2): 443–458.
3574:
3538:
3536:
3533:
3532:
3531:
3526:
3520:
3515:
3510:
3505:
3500:
3494:
3486:
3483:
3449:
3444:
3435:
3429:
3419:
3413:
3405:
3344:logical shifts
3319:
3316:
3233:
3230:
3024:implementation
2935:
2921:
2918:
2786:
2772:
2769:
2767:
2764:
2727:
2636:
2635:
2594:
2592:
2585:
2579:
2576:
2554:
2553:
2551:
2548:
2545:
2542:
2531:
2530:
2527:
2523:
2520:
2516:
2513:
2510:
2504:
2503:
2500:
2496:
2493:
2489:
2486:
2483:
2477:
2476:
2473:
2469:
2466:
2462:
2459:
2456:
2450:
2449:
2446:
2443:
2439:
2436:
2433:
2422:
2421:
2408:
2403:
2399:
2386:
2383:
2380:
2377:
2369:
2368:
2365:
2362:
2358:
2355:
2352:
2337:
2336:
2334:
2331:
2327:
2324:
2321:
2307:
2306:
2303:
2300:
2297:
2294:
2288:
2287:
2284:
2281:
2278:
2275:
2269:
2268:
2266:
2263:
2260:
2257:
2247:
2246:
2240:
2237:
2234:
2231:
2221:
2220:
2214:
2211:
2208:
2205:
2190:
2189:
2187:
2183:
2180:
2176:
2173:
2170:
2163:
2162:
2160:
2156:
2153:
2149:
2146:
2143:
2136:
2135:
2132:
2128:
2125:
2121:
2118:
2115:
2109:
2108:
2106:
2103:
2099:
2096:
2093:
2081:
2080:
2074:
2071:
2068:
2065:
2063:Virtual Pascal
2059:Borland Delphi
2055:
2054:
2051:
2048:
2045:
2042:
2003:
2002:
1999:
1996:
1993:
1990:
1979:
1978:
1968:
1965:
1962:
1959:
1952:
1951:
1949:
1946:
1943:
1940:
1926:
1925:
1923:
1920:
1917:
1914:
1906:
1905:
1895:
1888:
1881:
1874:
1848:
1845:
1844:
1843:
1833:
1827:
1816:
1801:
1795:
1787:
1781:
1774:
1754:
1745:
1737:
1728:
1714:
1699:
1683:
1677:
1669:
1663:
1652:
1645:
1638:
1624:
1623:
1612:
1608:
1605:
1601:
1598:
1588:
1584:
1580:
1575:
1571:
1563:
1559:
1555:
1550:
1546:
1539:
1533:
1530:
1527:
1522:
1519:
1514:
1510:
1503:
1498:
1494:
1490:
1482:
1478:
1474:
1469:
1465:
1457:
1453:
1449:
1444:
1440:
1414:
1413:
1402:
1398:
1395:
1391:
1388:
1381:
1377:
1373:
1368:
1364:
1360:
1355:
1351:
1347:
1342:
1338:
1334:
1331:
1326:
1322:
1318:
1313:
1309:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1284:
1279:
1275:
1271:
1268:
1263:
1259:
1230:
1221:
1213:
1204:
1197:
1043:
1042:
1030:
1010:
1007:
1004:
994:
982:
958:
955:
952:
942:
930:
910:
896:if and only if
883:
878:a power of 2,
873:
821:
787:
782:a power of 2,
777:
495:Main article:
492:
482:
416:
413:
408:
405:
362:
361:
349:
346:
341:
337:
333:
330:
326:
321:
317:
306:
294:
291:
288:
285:
282:
278:
275:
265:
253:
250:
247:
244:
241:
237:
234:
224:
208:
205:
202:
198:
195:
168:
157:
156:
143:
139:
134:
130:
127:
122:
118:
114:
110:
106:
101:
98:
95:
91:
15:
9:
6:
4:
3:
2:
4973:
4962:
4959:
4957:
4954:
4953:
4951:
4942:
4939:
4936:
4932:
4928:
4926:
4923:
4921:
4918:
4916:
4913:
4910:
4906:
4905:
4894:
4890:
4886:
4882:
4878:
4874:
4873:
4865:
4861:
4857:
4854:
4853:0-387-00178-6
4850:
4846:
4842:
4833:on 2011-08-11
4832:
4828:
4822:
4818:
4814:
4809:
4808:
4796:
4793:
4788:
4783:
4779:
4775:
4774:
4769:
4762:
4751:
4747:
4743:
4739:
4735:
4730:
4725:
4721:
4717:
4710:
4703:
4695:
4689:
4685:
4680:
4679:
4673:
4667:
4656:
4655:
4647:
4636:
4635:
4627:
4619:
4615:
4611:
4607:
4606:
4601:
4594:
4586:
4579:
4578:
4570:
4555:
4551:
4544:
4537:
4532:
4525:
4521:
4518:
4512:
4505:
4499:
4492:
4486:
4479:
4473:
4466:
4460:
4452:
4446:
4432:
4428:
4414:
4398:
4392:
4376:
4370:
4368:
4353:
4347:
4340:
4339:Windows Vista
4336:
4330:
4314:
4310:
4304:
4296:
4292:
4288:
4284:
4277:
4258:
4252:
4236:
4231:
4227:
4226:
4218:
4211:
4207:
4206:
4200:
4196:
4192:
4187:
4179:
4175:
4168:
4160:
4154:
4150:
4143:
4128:
4123:
4119:
4115:
4111:
4107:
4103:
4099:
4092:
4085:
4071:
4064:
4046:
4039:
4031:
4025:
4021:
4020:
4012:
4010:
4002:
3996:
3992:
3987:
3982:
3978:
3974:
3970:
3966:
3965:
3957:
3950:
3948:
3940:
3936:
3927:
3923:
3919:
3915:
3910:
3905:
3901:
3897:
3890:
3883:
3876:
3872:
3868:
3864:
3860:
3856:
3852:
3851:
3843:
3836:
3834:
3832:
3830:
3821:
3817:
3812:
3807:
3802:
3797:
3793:
3789:
3785:
3781:
3780:
3772:
3768:
3762:
3760:
3751:
3744:
3743:
3735:
3727:
3723:
3718:
3713:
3709:
3705:
3701:
3694:
3685:
3680:
3676:
3672:
3668:
3661:
3653:
3646:
3639:
3634:
3629:
3624:
3619:
3614:
3610:
3606:
3599:
3595:
3591:
3585:
3583:
3581:
3579:
3570:
3566:
3562:
3561:Knuth, Donald
3556:
3554:
3552:
3550:
3548:
3546:
3544:
3539:
3530:
3527:
3524:
3521:
3519:
3516:
3514:
3511:
3509:
3506:
3504:
3501:
3498:
3495:
3492:
3489:
3488:
3482:
3480:
3476:
3471:
3469:
3465:
3461:
3456:
3452:
3448:
3438:
3434:
3428:
3422:
3418:
3412:
3408:
3401:
3396:
3394:
3390:
3385:
3383:
3379:
3375:
3371:
3367:
3362:
3360:
3356:
3352:
3347:
3345:
3341:
3337:
3333:
3329:
3325:
3315:
3313:
3308:
3306:
3302:
3298:
3294:
3290:
3288:
3285: ±
3284:
3280:
3276:
3272:
3268:
3264:
3260:
3256:
3252:
3250:
3246:
3245:Wichmann–Hill
3242:
3237:
3229:
2933:
2931:
2927:
2784:
2782:
2778:
2763:
2760:
2755:
2752:
2747:
2745:
2740:
2736:
2734:
2733:spectral test
2730:
2723:
2719:
2715:
2709:
2705:
2696:
2693:
2685:
2677:
2672:
2670:
2661:
2660:spectral test
2657:
2653:
2649:
2647:
2643:
2632:
2629:
2621:
2611:
2607:
2601:
2600:
2595:This section
2593:
2589:
2584:
2583:
2575:
2573:
2569:
2564:
2561:
2552:
2549:
2546:
2543:
2540:
2536:
2533:
2532:
2528:
2521:
2514:
2511:
2509:
2506:
2505:
2501:
2494:
2487:
2484:
2482:
2479:
2478:
2474:
2467:
2460:
2457:
2455:
2452:
2451:
2447:
2444:
2437:
2434:
2431:
2427:
2424:
2423:
2406:
2401:
2397:
2387:
2384:
2381:
2378:
2376:
2371:
2370:
2366:
2363:
2356:
2353:
2350:
2346:
2342:
2339:
2338:
2335:
2332:
2325:
2322:
2320:
2316:
2312:
2309:
2308:
2304:
2301:
2298:
2295:
2293:
2290:
2289:
2285:
2282:
2279:
2276:
2274:
2271:
2270:
2267:
2264:
2261:
2258:
2256:
2252:
2249:
2248:
2245:
2241:
2238:
2235:
2232:
2226:
2223:
2222:
2219:
2215:
2212:
2209:
2206:
2199:
2195:
2192:
2191:
2188:
2181:
2174:
2171:
2169:
2165:
2164:
2161:
2154:
2147:
2144:
2141:
2138:
2137:
2133:
2126:
2120:214013 (343FD
2119:
2116:
2114:
2111:
2110:
2107:
2104:
2097:
2094:
2092:
2091:
2086:
2083:
2082:
2079:
2075:
2072:
2069:
2066:
2064:
2060:
2057:
2056:
2052:
2049:
2046:
2043:
2041:
2037:
2033:
2029:
2024:
2023:IBM VisualAge
2020:
2016:
2012:
2008:
2005:
2004:
2000:
1997:
1994:
1991:
1988:
1984:
1981:
1980:
1977:
1973:
1969:
1966:
1963:
1960:
1957:
1954:
1953:
1950:
1947:
1944:
1941:
1933:
1932:
1928:
1927:
1924:
1921:
1918:
1915:
1913:
1912:
1908:
1907:
1904:
1900:
1896:
1894:
1889:
1887:
1882:
1880:
1875:
1872:
1871:
1868:
1866:
1862:
1858:
1855:functions in
1854:
1841:
1838: +
1837:
1834:
1831:
1828:
1825:
1822:
1821:
1820:
1815:
1810:
1808:
1804:
1798: −
1794:
1790:
1780:
1773:
1769:
1765:
1761:
1757:
1748:
1744:
1740:
1731:
1727:
1722:
1720:
1713:
1709:
1705:
1698:
1694:
1690:
1686:
1680: ±
1676:
1672:
1662:
1658:
1651:
1648: −
1644:
1637:
1633:
1629:
1610:
1603:
1599:
1586:
1582:
1578:
1573:
1569:
1561:
1557:
1553:
1548:
1544:
1537:
1531:
1528:
1525:
1520:
1517:
1512:
1508:
1501:
1496:
1492:
1488:
1480:
1476:
1472:
1467:
1463:
1455:
1451:
1447:
1442:
1438:
1427:
1426:
1425:
1423:
1419:
1400:
1393:
1389:
1379:
1375:
1371:
1366:
1362:
1353:
1349:
1345:
1340:
1336:
1329:
1324:
1320:
1316:
1311:
1307:
1300:
1297:
1291:
1288:
1285:
1277:
1273:
1266:
1261:
1257:
1249:
1248:
1247:
1245:
1241:
1237:
1234: +
1233:
1224:
1220:
1216:
1207:
1203:
1200:= 0 and
1196:
1192:
1188:
1184:
1179:
1177:
1173:
1169:
1165:
1161:
1156:
1150:
1146:
1139:
1135:
1128:
1124:
1120:
1115:
1113:
1112:spectral test
1108:
1106:
1102:
1098:
1094:
1090:
1086:
1081:
1079:
1075:
1071:
1067:
1063:
1059:
1055:
1051:
1046:
1028:
1008:
1005:
1002:
995:
980:
972:
971:prime factors
956:
953:
950:
943:
928:
908:
901:
900:
899:
897:
893:
889:
881:
877:
872:
870:
866:
860:
858:
854:
849:
847:
843:
839:
835:
831:
827:
820:
816:
812:
807:
805:
801:
798:, most often
797:
793:
785:
781:
776:
774:
770:
765:
763:
759:
755:
751:
747:
743:
739:
732:
728:
722:
718:
714:
710:
706:
703: ≤
702:
698:
694:
691: =
690:
686:
682:
678:
674:
670:
666:
658:
654:
648:
644:
640:
636:
631:
627:
622:
618:
614:
605:
601:
594:
589:
585:
582: =
581:
577:
572:
570:
566:
562:
558:
550:
543:
539:
535:
531:
527:
522:
520:
516:
512:
508:
504:
498:
490:
486:
481:
478:
476:
472:
467:
465:
464:Weyl sequence
461:
457:
454:
450:
446:
442:
438:
434:
430:
426:
421:
415:Period length
412:
404:
402:
398:
394:
389:
387:
383:
379:
375:
371:
367:
347:
344:
339:
335:
331:
328:
324:
319:
315:
307:
292:
289:
286:
283:
280:
276:
273:
266:
251:
248:
245:
242:
239:
235:
232:
225:
222:
206:
203:
200:
196:
193:
186:
185:
184:
182:
166:
141:
132:
128:
125:
120:
116:
112:
108:
104:
99:
96:
93:
89:
81:
80:
79:
77:
72:
70:
66:
62:
58:
54:
50:
42:
38:
34:
30:
26:
21:
4934:
4876:
4870:
4844:
4835:, retrieved
4831:the original
4816:
4772:
4761:
4750:the original
4719:
4715:
4702:
4677:
4666:
4653:
4646:
4633:
4626:
4609:
4603:
4593:
4576:
4569:
4557:. Retrieved
4553:
4543:
4531:
4511:
4498:
4485:
4472:
4459:
4445:
4434:. Retrieved
4430:
4413:
4401:. Retrieved
4391:
4379:. Retrieved
4355:. Retrieved
4346:
4329:
4317:. Retrieved
4313:the original
4303:
4286:
4282:
4276:
4264:. Retrieved
4251:
4239:. Retrieved
4224:
4217:
4205:minstd_rand0
4204:
4194:
4186:
4177:
4167:
4148:
4142:
4131:. Retrieved
4101:
4097:
4084:
4073:. Retrieved
4063:
4052:. Retrieved
4038:
4018:
3968:
3962:
3934:
3929:
3899:
3895:
3882:
3874:
3854:
3848:
3786:(1): 25–28.
3783:
3777:
3750:hal-01561551
3741:
3734:
3710:(1): 75–77.
3707:
3703:
3693:
3674:
3670:
3660:
3651:
3645:
3632:
3608:
3604:
3564:
3472:
3467:
3463:
3459:
3454:
3450:
3442:
3436:
3432:
3426:
3420:
3416:
3410:
3403:
3399:
3397:
3389:counter mode
3386:
3378:xoshiro256**
3363:
3348:
3336:exclusive-or
3321:
3309:
3304:
3300:
3296:
3291:
3286:
3282:
3278:
3274:
3270:
3266:
3265:=2 and lags
3262:
3253:
3238:
3235:
3226:
2923:
2774:
2756:
2748:
2743:
2741:
2737:
2725:
2707:
2703:
2697:
2691:
2683:
2673:
2665:
2641:
2639:
2624:
2615:
2604:Please help
2599:verification
2596:
2565:
2557:
2534:
2502:bits 31..16
2461:65793 (10101
2372:
2367:bits 47..16
2326:69069 (10DCD
2314:
2305:bits 63..33
2255:Donald Knuth
2202:minstd_rand0
2134:bits 30..16
2088:
2085:Turbo Pascal
2077:
2053:bits 30..16
2015:Digital Mars
1975:
1971:
1929:
1909:
1902:
1898:
1892:
1885:
1878:
1864:
1852:
1850:
1839:
1835:
1829:
1823:
1813:
1811:
1806:
1799:
1792:
1785:
1778:
1771:
1767:
1763:
1759:
1752:
1746:
1742:
1735:
1729:
1725:
1723:
1718:
1711:
1707:
1703:
1696:
1692:
1688:
1681:
1674:
1667:
1660:
1656:
1649:
1642:
1635:
1631:
1627:
1625:
1421:
1417:
1415:
1243:
1239:
1235:
1228:
1222:
1218:
1211:
1205:
1201:
1194:
1190:
1186:
1182:
1180:
1175:
1171:
1167:
1163:
1159:
1157:
1148:
1144:
1137:
1133:
1129:is desired,
1126:
1122:
1118:
1116:
1109:
1104:
1100:
1096:
1092:
1088:
1084:
1082:
1077:
1073:
1069:
1061:
1053:
1049:
1047:
1044:
941:are coprime,
891:
887:
885:
879:
875:
868:
864:
861:
856:
852:
850:
845:
841:
837:
833:
829:
825:
818:
814:
810:
808:
803:
799:
796:power of two
791:
789:
783:
779:
772:
768:
766:
761:
757:
753:
749:
745:
741:
737:
730:
726:
720:
716:
712:
708:
704:
700:
696:
692:
688:
684:
680:
676:
672:
668:
664:
656:
652:
646:
642:
638:
634:
629:
625:
620:
616:
612:
603:
599:
592:
587:
583:
579:
575:
573:
568:
564:
560:
556:
548:
541:
537:
533:
529:
523:
518:
514:
506:
502:
500:
488:
484:
479:
470:
468:
459:
452:
448:
444:
440:
436:
432:
422:
418:
410:
392:
390:
385:
381:
373:
369:
363:
158:
73:
52:
48:
46:
40:
36:
32:
28:
24:
4722:(1): 3–30.
4399:. MathWorks
4381:3 September
4098:SIAM Review
3458:) mod
2930:Free Pascal
2920:Free Pascal
2771:Python code
2766:Sample code
2714:hyperplanes
2656:Hyperplanes
2475:bits 22..8
2379:134456 = 27
2315:MTH$ RANDOM
2229:minstd_rand
2019:CodeWarrior
2001:bits 30..0
1974:, 30..0 in
1859:of various
4950:Categories
4860:Joan Boyar
4837:2011-08-10
4805:References
4612:(1): 3–6.
4526:. pp. 6–7.
4436:2024-01-13
4357:2024-01-13
4133:2016-06-26
4075:2017-10-31
4054:2017-10-31
3654:: 141–146.
3618:2001.05304
3523:Lehmer RNG
3508:Full cycle
3393:SplitMix64
2940:lcg_random
2759:randomness
2168:Native API
2078:(seed × L)
2047:1103515245
1995:1103515245
1948:1013904223
1883:multiplier
1751:= 157
1734:= 157
1153:X % r
707:(and thus
571:is small.
462:produce a
378:Lehmer RNG
376:(MCG), or
4724:CiteSeerX
4230:CiteSeerX
4127:1828/3142
3981:CiteSeerX
3904:CiteSeerX
3871:207575300
3677:(2): 83.
3409: = (
3255:Marsaglia
3150:LCGRandom
3096:LCGRandom
3063:134775813
2982:LCGRandom
2955:LCGRandom
2949:interface
2860:Generator
2797:Generator
2781:generator
2690:results.
2662:measures.
2618:July 2021
2070:134775813
1985:(used by
1903:Random(L)
1890:increment
1861:compilers
1579:−
1554:−
1529:−
1518:−
1473:−
1448:−
1346:−
1289:−
1238:mod
1058:word size
1006:−
954:−
790:Choosing
332:≤
284:≤
57:algorithm
4862:(1989).
4550:"rand.s"
4520:Archived
4199:stdlib.h
4003:as well.
3926:15238956
3820:16591687
3726:16770825
3563:(1997).
3485:See also
3425: +
3351:xorshift
3180:overload
3147:function
3108:overload
3102:extended
3093:function
3081:RandSeed
3057:RandSeed
3051:RandSeed
3036:cardinal
3027:function
3012:overload
2979:function
2967:overload
2961:extended
2952:function
2428:rand48,
2347:rand48,
1964:22695477
794:to be a
663:. Since
399:, not a
181:sequence
55:) is an
4893:3565772
4746:3332028
4493:. 2004.
4491:random0
4319:17 June
4241:16 June
4106:Bibcode
3973:Bibcode
3932:√
3788:Bibcode
3366:TestU01
3249:coprime
3174:longint
3165:longint
3006:longint
2997:longint
2908:modulus
2809:modulus
2701:√
2681:√
2669:TestU01
2374:random0
2090:et seq.
1976:lrand()
1956:Borland
1945:1664525
1876:modulus
1791:≡
1673:=
1227:=
1210:=
1064:were a
855:/4 and
802:= 2 or
590:, i.e.
487:prime,
456:coprime
407:History
366:integer
221:modulus
219:— the "
179:is the
4891:
4851:
4823:
4744:
4726:
4690:
4559:8 July
4403:7 June
4266:21 Dec
4232:
4195:rand()
4155:
4026:
4001:Errata
3983:
3924:
3906:
3869:
3818:
3811:285899
3808:
3724:
3479:xorwow
3243:; the
3195:Result
3186:inline
3123:Result
3114:inline
3075:Result
3042:inline
3018:inline
2973:inline
2794:import
2777:Python
2432:rand48
2407:134456
2351:rand48
2273:Newlib
2244:MINSTD
2218:MINSTD
2172:2 − 1
2011:Watcom
2007:ANSI C
1972:rand()
1935:ranqd1
1899:rand()
1873:Source
1853:rand()
544:
401:linear
159:where
4889:S2CID
4867:(PDF)
4753:(PDF)
4742:S2CID
4712:(PDF)
4658:(PDF)
4638:(PDF)
4581:(PDF)
4425:srand
4260:(PDF)
4094:(PDF)
4048:(PDF)
3959:(PDF)
3922:S2CID
3892:(PDF)
3867:S2CID
3845:(PDF)
3774:(PDF)
3746:(PDF)
3722:S2CID
3613:arXiv
3601:(PDF)
3535:Notes
3332:GF(2)
3330:over
3207:range
3192:begin
3159:range
3156:const
3120:begin
3048:begin
2991:range
2988:const
2911:yield
2869:while
2857:->
2572:as if
2547:65539
2539:RANDU
2430:glibc
2426:POSIX
2385:28411
2349:glibc
2345:POSIX
2319:glibc
2236:48271
2233:2 − 1
2225:C++11
2210:16807
2207:2 − 1
2198:C++11
2050:12345
2025:C/C++
1998:12345
1983:glibc
1958:C/C++
1916:2 + 1
886:When
859:≠ 0.
760:<
695:. If
671:<
475:RANDU
391:When
380:. If
4849:ISBN
4821:ISBN
4795:4086
4778:IETF
4688:ISBN
4561:2016
4554:cc65
4421:rand
4405:2021
4383:2011
4335:MSDN
4321:2011
4268:2014
4243:2012
4153:ISBN
4024:ISBN
3816:PMID
3779:PNAS
3475:KISS
3462:for
3380:and
3374:rank
3338:and
3269:and
2937:unit
2914:seed
2893:seed
2878:seed
2872:True
2845:seed
2788:from
2560:Java
2508:cc65
2481:cc65
2454:cc65
2382:8121
2341:Java
2292:Musl
2251:MMIX
2242:see
2216:see
2087:4.0
1911:ZX81
1420:and
1147:mod
1085:good
921:and
756:) ≤
645:) −
641:mod
619:mod
610:and
521:−1.
435:and
364:are
345:<
290:<
249:<
243:<
204:<
4881:doi
4792:RFC
4782:doi
4734:doi
4614:doi
4291:doi
4197:in
4122:hdl
4114:doi
3991:doi
3914:doi
3859:doi
3806:PMC
3796:doi
3712:doi
3679:doi
3623:doi
3477:or
3400:not
3219:end
3210:shr
3141:end
3087:end
2851:int
2839:int
2827:int
2815:int
2803:lcg
2800:def
2692:Any
2688:≈ 2
2608:by
2313:'s
2311:VMS
2253:by
2227:'s
2200:'s
2040:C17
2036:C11
2032:C99
2028:C90
1987:GCC
1901:or
1721:).
1600:mod
1390:mod
1160:not
973:of
882:≠ 0
786:= 0
491:= 0
458:to
138:mod
53:LCG
4952::
4887:.
4877:36
4875:.
4869:.
4815:,
4776:.
4770:.
4740:.
4732:.
4718:.
4714:.
4686:.
4684:59
4608:.
4602:.
4552:.
4429:.
4423:,
4366:^
4287:12
4285:.
4228:.
4176:.
4120:.
4112:.
4100:.
4096:.
4008:^
3989:.
3979:.
3969:68
3967:.
3961:.
3946:^
3928:.
3920:.
3912:.
3900:19
3898:.
3894:.
3873:.
3865:.
3855:31
3853:.
3847:.
3828:^
3814:.
3804:.
3794:.
3784:61
3782:.
3776:.
3758:^
3720:.
3706:.
3702:.
3673:.
3669:.
3631:.
3621:.
3609:52
3607:.
3603:.
3592:;
3577:^
3567:.
3542:^
3439:−2
3423:−1
3395:.
3310:A
3307:.
3301:ab
3213:32
3201:IM
3198::=
3129:IM
3126::=
3078::=
3054::=
3030:IM
2783::
2706:!⋅
2524:16
2517:16
2497:16
2490:16
2470:16
2463:16
2445:11
2440:16
2364:11
2359:16
2328:16
2196:,
2184:16
2177:16
2157:16
2150:16
2129:16
2122:16
2100:16
2061:,
2034:,
2030:,
2021:,
2017:,
2013:,
2009::
1989:)
1922:74
1919:75
1809:.
1749:+1
1732:+1
1666:,
1246::
1229:aX
1225:+1
1212:aY
1208:+1
1134:rX
898::
744:=
738:rx
736:≤
719::
685:am
675:≤
632:=
626:ax
615:=
595:=
584:qa
561:ad
551:/2
549:ax
538:ax
388:.
78::
47:A
4895:.
4883::
4855:.
4797:.
4784::
4736::
4720:8
4696:.
4620:.
4616::
4610:5
4563:.
4453:.
4439:.
4419:"
4407:.
4385:.
4360:.
4323:.
4297:.
4293::
4270:.
4245:.
4161:.
4136:.
4124::
4116::
4108::
4102:4
4078:.
4057:.
4032:.
3997:.
3993::
3975::
3935:m
3916::
3861::
3822:.
3798::
3790::
3752:.
3728:.
3714::
3708:7
3687:.
3681::
3675:1
3640:.
3625::
3615::
3468:m
3464:k
3460:m
3455:k
3453:−
3451:n
3447:X
3445:k
3443:a
3437:n
3433:X
3430:2
3427:a
3421:n
3417:X
3414:1
3411:a
3406:n
3404:X
3305:b
3297:a
3287:b
3283:b
3279:s
3275:r
3273:(
3271:s
3267:r
3263:b
3222:;
3216:;
3204:*
3189:;
3183:;
3177:;
3171::
3168:)
3162::
3153:(
3144:;
3138:;
3132:*
3117:;
3111:;
3105:;
3099::
3090:;
3084:;
3072:;
3069:1
3066:+
3060:*
3045:;
3039:;
3033::
3021:;
3015:;
3009:;
3003::
3000:)
2994::
2985:(
2976:;
2970:;
2964:;
2958::
2943:;
2905:%
2902:)
2899:c
2896:+
2890:*
2887:a
2884:(
2881:=
2875::
2863::
2854:)
2848::
2842:,
2836::
2833:c
2830:,
2824::
2821:a
2818:,
2812::
2806:(
2744:m
2728:n
2726:X
2716:(
2708:m
2704:n
2684:m
2642:m
2631:)
2625:(
2620:)
2616:(
2602:.
2550:0
2544:2
2526:)
2519:)
2512:2
2499:)
2492:)
2485:2
2472:)
2465:)
2458:2
2442:)
2435:2
2402:n
2398:X
2361:)
2354:2
2333:1
2330:)
2323:2
2302:1
2296:2
2283:1
2277:2
2259:2
2239:0
2213:0
2186:)
2179:)
2159:)
2152:)
2145:2
2131:)
2124:)
2117:2
2105:1
2102:)
2095:2
2073:1
2067:2
2044:2
1992:2
1967:1
1961:2
1942:2
1893:c
1886:a
1879:m
1840:Y
1836:X
1830:Y
1824:X
1817:0
1814:X
1807:n
1802:n
1800:Y
1796:0
1793:X
1788:n
1786:X
1782:0
1779:X
1775:0
1772:X
1768:c
1764:a
1760:m
1755:n
1753:Y
1747:n
1743:Y
1738:n
1736:X
1730:n
1726:X
1719:m
1715:0
1712:X
1710:)
1708:a
1704:c
1700:0
1697:X
1693:c
1689:n
1684:n
1682:Y
1678:0
1675:X
1670:n
1668:X
1664:0
1661:X
1657:m
1653:0
1650:X
1646:1
1643:X
1639:0
1636:X
1632:a
1628:m
1611:.
1607:)
1604:m
1597:(
1587:0
1583:Z
1574:1
1570:Z
1562:0
1558:Z
1549:n
1545:Z
1538:=
1532:1
1526:a
1521:1
1513:n
1509:a
1502:=
1497:n
1493:Y
1489:=
1481:0
1477:X
1468:1
1464:X
1456:0
1452:X
1443:n
1439:X
1422:Z
1418:X
1401:.
1397:)
1394:m
1387:(
1380:0
1376:X
1372:+
1367:n
1363:Y
1359:)
1354:0
1350:X
1341:1
1337:X
1333:(
1330:=
1325:0
1321:X
1317:+
1312:n
1308:Y
1304:)
1301:c
1298:+
1295:)
1292:1
1286:a
1283:(
1278:0
1274:X
1270:(
1267:=
1262:n
1258:X
1244:Y
1240:m
1236:c
1231:n
1223:n
1219:X
1214:n
1206:n
1202:Y
1198:0
1195:Y
1191:Y
1187:c
1183:c
1176:c
1172:c
1168:m
1164:c
1149:r
1145:X
1141:⌋
1138:m
1136:/
1131:⌊
1127:r
1123:k
1119:c
1105:a
1101:a
1097:m
1093:m
1089:a
1078:m
1074:m
1070:a
1062:m
1054:m
1050:m
1029:m
1009:1
1003:a
993:,
981:m
957:1
951:a
929:c
909:m
892:m
888:c
880:c
876:m
869:X
865:b
857:c
853:m
846:X
842:a
838:X
834:a
830:X
826:X
822:0
819:X
815:a
811:m
804:m
800:m
792:m
784:c
780:m
773:m
769:x
762:m
758:x
754:q
752:/
750:r
748:(
746:x
742:q
740:/
734:⌋
731:q
729:/
727:x
724:⌊
721:r
717:m
713:q
711:/
709:r
705:q
701:r
697:a
693:m
689:a
687:/
681:a
679:/
677:m
673:q
669:q
665:x
660:⌋
657:q
655:/
653:x
650:⌊
647:r
643:q
639:x
637:(
635:a
630:m
621:a
617:m
613:r
607:⌋
604:a
602:/
600:m
597:⌊
593:q
588:r
586:+
580:m
569:d
565:m
563:/
557:m
553:⌋
546:⌊
542:d
534:d
530:m
519:m
515:m
507:a
503:m
489:c
485:m
471:a
460:m
453:c
449:m
445:c
441:a
437:a
433:m
393:c
382:c
370:c
348:m
340:0
336:X
329:0
325:,
320:0
316:X
293:m
287:c
281:0
277:,
274:c
252:m
246:a
240:0
236:,
233:a
223:"
207:m
201:0
197:,
194:m
167:X
142:m
133:)
129:c
126:+
121:n
117:X
113:a
109:(
105:=
100:1
97:+
94:n
90:X
51:(
41:c
37:a
33:c
29:a
25:m
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
