Linear congruential generator - Wikipedia

Linear congruential generator - Wikipedia
Jump to content
From Wikipedia, the free encyclopedia
Algorithm for generating pseudo-randomized numbers
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
= 9,
= 2,
= 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
= 4 and
= 1 (bottom row) gives a cycle length of 9 with any seed in [0, 8].
linear congruential generator
LCG
) is an
algorithm
that yields a sequence of pseudo-randomized numbers calculated with a discontinuous
piecewise linear equation
. The method represents one of the oldest and best-known
pseudorandom number generator
algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide
modular arithmetic
by storage-bit truncation.
The generator is defined by the
recurrence relation
mod
{\displaystyle X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}}
where
{\displaystyle X}
is the
sequence
of pseudo-random values, and
{\displaystyle m,\,0— the "
modulus
{\displaystyle a,\,0— the "multiplier"
{\displaystyle c,\,0\leq c— the "increment"
{\displaystyle X_{0},\,0\leq X_{0}— the "seed" or "start value"
are
integer
constants that specify the generator. If
= 0, the generator is often called a
multiplicative congruential generator
(MCG), or
Lehmer RNG
. If
≠ 0, the method is called a
mixed congruential generator
: 4-
When
≠ 0, a mathematician would call the recurrence an
affine transformation
, not a
linear
one, but the
misnomer
is well-established in computer science.
: 1
History
edit
The Lehmer generator was published in 1951
and the Linear congruential generator was published in 1958 by W. E. Thomson and A. Rotenberg.
Period length
edit
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.
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
and
10
For example,
= 1 and
= 1 produces a simple modulo-
counter, which has a long period, but is obviously non-random. Other values of
coprime
to
produce a
Weyl sequence
, which is better distributed but still obviously non-random.
Historically, poor choices for
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 the use of this poor LCG.
11
: 1198–9
There are three common families of parameter choice:
prime,
= 0
edit
Main article:
Lehmer random number generator
This is the original Lehmer RNG construction. The period is
−1 if the multiplier
is chosen to be a
primitive element
of the integers modulo
. The initial state must be chosen between 1 and
−1.
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
Mersenne primes
31
−1 and 2
61
−1 are popular), so that the reduction modulo
= 2
can be computed as (
ax
mod 2
) +
ax
/2
. This must be followed by a conditional subtraction of
if the result is too large, but the number of subtractions is limited to
ad
, which can be easily limited to one if
is small.
If a double-width product is unavailable, and the multiplier is chosen carefully,
Schrage's method
12
13
may be used. To do this, factor
qa
, i.e.
and
mod
. Then compute
ax
mod
mod
) −
. Since
mod
, the first term is strictly less than
am
. If
is chosen so that
(and thus
≤ 1), then the second term is also less than
rx
) ≤
. Thus, both products can be computed with a single-width product, and the difference between them lies in the range [1−
−1], so can be reduced to [0,
−1] with a single conditional add.
14
The most expensive operation in Schrage's method is the division (with remainder) of
by
; fast
algorithms for division by a constant
are not available since they also rely on double-width products.
A second disadvantage of a prime modulus is that it is awkward to convert the value 1 ≤
to uniform random bits. If a prime just less than a power of 2 is used, sometimes the missing values are simply ignored.
a power of 2,
= 0
edit
Choosing
to be a
power of two
, most often
= 2
32
or
= 2
64
, 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.
This form has maximal period
/4, achieved if
≡ ±3 (mod 8) and the initial state
is odd. Even in this best case, the low three bits of
alternate between two values and thus only contribute one bit to the state.
is always odd (the lowest-order bit never changes), and only one of the next two bits ever changes. If
≡ +3,
alternates ±1↔±3, while if
≡ −3,
alternates ±1↔∓3 (all modulo 8).
It can be shown that this form is equivalent to a generator with modulus
/4 and
≠ 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 the fact that bits are never affected by higher-order bits, so the low
bits of such a generator form a modulo-2
LCG by themselves, repeating with a period of 2
−2
. Only the most significant bit of
achieves the full period.
a power of 2,
≠ 0
edit
When
≠ 0, correctly chosen parameters allow a period equal to
, for all seed values. This will occur
if and only if
: 17–19
{\displaystyle m}
and
{\displaystyle c}
are coprime,
{\displaystyle a-1}
is divisible by all
prime factors
of
{\displaystyle m}
{\displaystyle a-1}
is divisible by 4 if
{\displaystyle m}
is divisible by 4.
These three requirements are referred to as the Hull–Dobell Theorem.
15
16
This form may be used with any
, but only works well for
with many repeated prime factors, such as a power of 2; using a computer's
word size
is the most common choice. If
were a
square-free integer
, this would only allow
≡ 1 (mod
), which makes a very poor PRNG; a selection of possible full-period multipliers is only available when
has repeated prime factors.
Although the Hull–Dobell theorem provides maximum period, it is not sufficient to guarantee a
good
generator.
: 1199
For example, it is desirable for
− 1 to not be any more divisible by prime factors of
than necessary. If
is a power of 2, then
− 1 should be divisible by 4 but not divisible by 8, i.e.
≡ 5 (mod 8).
: §3.2.1.3
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
: §3.3.3
is quite challenging.
The
spectral test
is one of the most important tests.
17
Note that a power-of-2 modulus shares the problem as described above for
= 0: the low
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
is desired,
rX
is a much higher-quality result than
mod
. 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
, as long as it is relatively prime to the modulus (e.g. if
is a power of 2, then
must be odd), so the value
=1 is commonly chosen.
The sequence produced by other choices of
can be written as a simple function of the sequence when
=1.
: 11
Specifically, if
is the prototypical sequence defined by
= 0 and
+1
aY
+ 1 mod m, then a general sequence
+1
aX
mod
can be written as an affine function of
mod
{\displaystyle X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.}
More generally, any two sequences
and
with the same multiplier and modulus are related by
mod
{\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}}.}
In the common case where
is a power of 2 and
≡ 5 (mod 8) (a desirable property for other reasons), it is always possible to find an initial value
so that the denominator
≡ ±1 (mod
), producing an even simpler relationship. With this choice of
will remain true for all
: 10-11
The sign is determined by
≡ ±1 (mod 4), and the constant
is determined by 1 ∓
≡ (1 −
(mod
).
As a simple example, consider the generators
+1
= 157
+ 3 mod 256 and
+1
= 157
+ 1 mod 256; i.e.
= 256,
= 157, and
= 3. Because 3 ≡ −1 (mod 4), we are searching for a solution to 1 + 3 ≡ (1 − 157)
(mod 256). This is satisfied by
≡ 41 (mod 64), so if we start with that, then
(mod 256) for all
For example, using
= 233 = 3×64 + 41:
= 233, 232, 75, 2, 61, 108, ...
= 0, 1, 158, 231, 172, 125, ...
mod 256 = 233, 233, 233, 233, 233, 233, ...
Parameters in common use
edit
The following table lists the parameters of LCGs in common use, including built-in
rand()
functions in
runtime libraries
of various
compilers
. This table is to show popularity, not examples to emulate;
many of these parameters are poor.
Tables of good parameters are available.
10
Source
modulus
multiplier
increment
output bits of seed in
rand()
or
Random(L)
ZX81
ZX Spectrum
18
16
+ 1
75
− 1) / 2
16
Numerical Recipes
ranqd1
, Chapter 7.1, §An Even Quicker Generator, Eq. 7.1.6
parameters from Knuth and H. W. Lewis
32
1664525
1013904223
Borland
C/C++
31
22695477
bits 30..16 in
rand()
, 30..0 in
lrand()
glibc
(used by
GCC
19
31
1103515245
12345
bits 30..0
ANSI C
Watcom
Digital Mars
CodeWarrior
IBM VisualAge
C/C++
20
C90
C99
C11
: Suggestion in the ISO/IEC 9899,
21
C17
31
1103515245
12345
bits 30..16
Borland Delphi
Virtual Pascal
32
134775813
bits 63..32 of
(seed × L)
Turbo Pascal
4.0
et seq.
22
32
134775813 (8088405
16
Microsoft Visual/Quick C/C++
31
214013 (343FD
16
2531011 (269EC3
16
bits 30..16
Microsoft Visual Basic
(6 and earlier)
23
24
1140671485 (43FD43FD
16
12820163 (C39EC3
16
RtlUniform from
Native API
24
25
31
− 1
−18 (7FFFFFED
16
−60 (7FFFFFC3
16
Apple CarbonLib
C++11
's
minstd_rand0
26
MATLAB's v4 legacy generator mcg16807
27
31
− 1
16807
see
MINSTD
C++11
's
minstd_rand
26
31
− 1
48271
see
MINSTD
rsixfour.c
, from the
MMIX
Suppliment
28
64
6364136223846793005
9754186451795953191
Newlib
29
63
6364136223846793005
bits 62..32 (46..32 for 16-bit int)
Musl
64
6364136223846793005
bits 63..33
VMS
's
MTH$RANDOM
30
old versions of
glibc
32
69069 (10DCD
16
Java
's java.util.Random,
POSIX
[ln]rand48,
glibc
[ln]rand48[_r]
48
25214903917 (5DEECE66D
16
11
bits 47..17
POSIX
31
[dejm]rand48,
glibc
[dejm]rand48[_r]
48
25214903917 (5DEECE66D
16
11
bits 47..0 or bits 47..16, as required
random0
32
33
34
35
36
134456 = 2
8121
28411
134456
{\displaystyle {\frac {X_{n}}{134456}}}
cc65
's rand
37
32
16843009 (1010101
16
826366247 (31415927
16
[orig] bits 22..8 {effective modulus 2
24
[2016] bits 22..16,31..24 {change #323}
cc65
's rand
38
32
16843009 (1010101
16
3014898611 (B3B3B3B3
16
[2019] bits 22..16,31..24 {change #951}
[2020] bits 22..16,31..24 xor bits 6..0,15..8 {change #1107}
Formerly common:
RANDU
11
31
65539
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 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 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.
Advantages and disadvantages
edit
This section
needs additional citations for
verification
Please help
improve this article
by
adding citations to reliable sources
in this section. Unsourced material may be challenged and removed.
July 2021
Learn how and when to remove this message
LCGs are fast and require minimal memory (one modulo-
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
cryptographically secure pseudorandom number generator
for such applications.
Hyperplanes
of a linear congruential generator in three dimensions. This structure is what the
spectral test
measures.
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; a modulo-2
64
LCG which returns the high 32 bits passes
TestU01
's SmallCrush suite,
citation needed
and a 96-bit LCG passes the most stringent BigCrush suite.
39
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
≈ 2
16
results.
Any
PRNG whose output is its full, untruncated state will not produce duplicates until its full period elapses, an easily detectable statistical flaw.
40
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 period of 2
64
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,
!⋅
hyperplanes
Marsaglia's theorem
, developed by
George Marsaglia
).
This is due to serial correlation between successive values of the sequence
. 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 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
64
Another flaw specific to LCGs is the short period of the low-order bits when
is chosen to be a power of 2. In particular, any full-cycle LCG, when m is a power of 2, will produce alternately odd and even results. 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 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, as mentioned above.)
LCGs should be evaluated very carefully for suitability in non-cryptographic applications where high-quality
randomness
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
21
random samples (a little over two million), etc. For this reason, in practice LCGs are not suitable for large-scale Monte Carlo simulations.
Sample code
edit
Python code
edit
The following is an implementation of an LCG in
Python
, in the form of a
generator
from
collections.abc
import
Generator
def
lcg
modulus
int
int
int
seed
int
->
Generator
int
None
None
]:
"""Linear congruential generator."""
while
True
seed
seed
modulus
yield
seed
Haskell code
edit
The following is an implementation of an LCG in
Haskell
utilizing a
lazy evaluation
strategy to generate an infinite stream of output values in a list:
-- Allowing a generic choice for a, c, m and x_0
linearCongruentialGenerator
::
Integer
->
Integer
->
Integer
->
Integer
->
Integer
linearCongruentialGenerator
modulus
seed
lcgacmx0
where
lcgacmx0
seed
map
->
mod
modulus
lcgacmx0
-- Specific parameters can be easily specified (eg. Knuth's MMIX parameters):
mmixLCG
::
Integer
->
Integer
mmixLCG
linearCongruentialGenerator
6364136223846793005
1442695040888963407
64
::
Integer
))
Free Pascal
edit
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.
unit
lcg_random
{$ifdef fpc}{$mode delphi}{$endif}
interface
function
LCGRandom
extended
overload
inline
function
LCGRandom
const
range
longint
longint
overload
inline
implementation
function
IM
cardinal
inline
begin
RandSeed
:=
RandSeed
134775813
Result
:=
RandSeed
end
function
LCGRandom
extended
overload
inline
begin
Result
:=
IM
2.32830643653870e-10
end
function
LCGRandom
const
range
longint
longint
overload
inline
begin
Result
:=
IM
range
shr
32
end
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 avoid equal sequences of random numbers on simultaneously executing threads.
LCG derivatives
edit
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.
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 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
=2
and lags
and
) are equivalent to LCGs with a modulus of
± 1.
41
42
Multiply-with-carry
PRNGs with a multiplier of
are equivalent to LCGs with a large prime modulus of
ab
−1 and a power-of-2 multiplier
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.
Comparison with other PRNGs
edit
The other widely used primitive for obtaining long-period pseudorandom sequences is the
linear-feedback shift register
construction, which is based on arithmetic in GF(2)[
], the
polynomial ring
over
GF(2)
. Rather than integer addition and multiplication, the basic operations are
exclusive-or
and
carry-less multiplication
, which is usually implemented as a sequence of
logical shifts
. 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
43
Examples of this family include
xorshift
generators and the
Mersenne twister
. The latter provides a very long period (2
19937
−1) and variate uniformity, but it fails some statistical tests.
44
Lagged Fibonacci generators
also fall into this category; although they use arithmetic addition, their period is ensured by an LFSR among the least-significant bits.
It is easy to detect the structure of a linear-feedback shift register with appropriate tests
45
such as the linear complexity test implemented in the
TestU01
suite; a Boolean
circulant matrix
initialized from consecutive bits of an LFSR will never have
rank
greater than the degree of the polynomial. Adding a non-linear output mixing function (as in the
xoshiro256**
and
permuted congruential generator
constructions) can greatly improve the performance on statistical tests.
Another structure for a PRNG is a very simple recurrence function combined with a powerful output mixing function. This includes
counter mode
block ciphers and non-cryptographic generators such as
SplitMix64
A structure similar to LCGs, but
not
equivalent, is the multiple-recursive generator:
= (
−1
−2
+ ··· +
) mod
for
≥ 2. With a prime modulus, this can generate periods up to
−1, so is a useful extension of the LCG structure to larger periods.
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
KISS
or
xorwow
constructions) can do very well at some cost in speed.
See also
edit
List of random number generators
– other PRNGs including some with better statistical qualities
ACORN generator
– not to be confused with ACG which term appears to have been used for variants of LCG and LFSR generators
Permuted congruential generator
Full cycle
Inversive congruential generator
Multiply-with-carry
Lehmer RNG
(sometimes called the Park–Miller RNG)
Combined linear congruential generator
Notes
edit
Knuth, Donald
(1997).
Seminumerical Algorithms
The Art of Computer Programming
. Vol. 2 (3rd ed.). Reading, MA: Addison-Wesley Professional. pp.
10–
26.
Steele, Guy L. Jr.
Vigna, Sebastiano
(February 2022) [15 January 2020].
"Computationally easy, spectrally good multipliers for congruential pseudorandom number generators"
Software: Practice and Experience
52
(2):
443–
458.
arXiv
2001.05304
doi
10.1002/spe.3030
hdl
2434/891395
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.
Associated software and data at
Lehmer, Derrick H. (1951). "Mathematical methods in large-scale computing units".
Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery
141–
146.
Thomson, W. E. (1958).
"A Modified Congruence Method of Generating Pseudo-random Numbers"
The Computer Journal
(2): 83.
doi
10.1093/comjnl/1.2.83
Rotenberg, A. (1960).
"A New Pseudo-Random Number Generator"
Journal of the ACM
(1):
75–
77.
doi
10.1145/321008.321019
S2CID
16770825
L'Ecuyer, Pierre (13 July 2017). Chan, W. K. V.; D'Ambrogio, A.; Zacharewicz, G.; Mustafee, N.; Wainer, G.; Page, E. (eds.).
History of Uniform Random Number Generation
(PDF)
. Proceedings of the 2017 Winter Simulation Conference (to appear). Las Vegas, United States.
hal-01561551
Marsaglia, George
(September 1968).
"Random Numbers Fall Mainly in the Planes"
(PDF)
PNAS
61
(1):
25–
28.
Bibcode
1968PNAS...61...25M
doi
10.1073/pnas.61.1.25
PMC
285899
PMID
16591687
Park, Stephen K.; Miller, Keith W. (October 1988).
"Random Number Generators: Good Ones Are Hard To Find"
(PDF)
Communications of the ACM
31
(10):
1192–
1201.
doi
10.1145/63039.63042
S2CID
207575300
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.
Hörmann, Wolfgang; Derflinger, Gerhard (1993).
"A Portable Uniform Random Number Generator Well Suited for the Rejection Method"
(PDF)
ACM Transactions on Mathematical Software
19
(4):
489–
495.
CiteSeerX
10.1.1.52.3811
doi
10.1145/168173.168414
S2CID
15238956
a multiplier about as small as
, produces random numbers with a bad one-dimensional distribution.
L'Ecuyer, Pierre (January 1999).
"Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure"
(PDF)
Mathematics of Computation
68
(225):
249–
260.
Bibcode
1999MaCom..68..249L
CiteSeerX
10.1.1.34.1024
doi
10.1090/S0025-5718-99-00996-5
Be sure to read the
Errata
as well.
Press, William H.; et al. (1992).
Numerical Recipes in Fortran 77: The Art of Scientific Computing
(2nd ed.). Cambridge University Press. p. 268.
ISBN
978-0-521-43064-7
Schrage, Linus (June 1979).
"A more portable Fortran random number generator"
(PDF)
ACM Transactions on Mathematical Software
(2):
132–
138.
doi
10.1145/355826.355828
Jain, Raj (9 July 2010).
"Computer Systems Performance Analysis Chapter 26: Random-Number Generation"
(PDF)
. pp.
19–
20
. Retrieved
2017-10-31
Fenerty, Paul (11 September 2006).
"Schrage's Method"
. Archived from
the original
on 2018-12-30
. Retrieved
2017-10-31
Hull, T. E.; Dobell, A. R. (July 1962).
"Random Number Generators"
(PDF)
SIAM Review
(3):
230–
254.
Bibcode
1962SIAMR...4..230H
doi
10.1137/1004061
hdl
1828/3142
. Retrieved
2016-06-26
Severance, Frank (2001).
System Modeling and Simulation
. John Wiley & Sons, Ltd. p. 86.
ISBN
978-0-471-49694-6
Austin, David (March 2008).
"Random Numbers: Nothing Left to Chance"
Feature Column
. American Mathematical Society.
"SINCLAIR ZX SPECTRUM - BASIC Programming, chapter 11"
. Retrieved
14 Mar
2025
Implementation in glibc-2.26 release.
See the code after the test for "TYPE_0"; the GNU C library's
rand()
in
stdlib.h
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 (
initialized using
minstd_rand0
) and the period increases. See the
simplified code
that reproduces the random sequence from this library.
K. Entacher (21 August 1997).
A collection of selected pseudorandom number generators with linear structures
CiteSeerX
10.1.1.53.3686
. Retrieved
16 June
2012
"Last public Committee Draft from April 12, 2011"
(PDF)
. p. 346f
. Retrieved
21 Dec
2014
Dohmann, Birgit; Falk, Michael; Lessenich, Karin (August 1991). "The random number generators of the Turbo Pascal family".
Computational Statistics & Data Analysis
12
(1):
129–
132.
doi
10.1016/0167-9473(91)90108-E
"How Visual Basic Generates Pseudo-Random Numbers for the RND Function"
. Microsoft. 24 June 2004. Archived from
the original
on 17 April 2011
. Retrieved
17 June
2011
In spite of documentation on
MSDN
, RtlUniform uses LCG, and not Lehmer's algorithm, implementations before
Windows Vista
are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied
"WINE source identifier search: RtlUniform"
. Retrieved
2024-01-13
"ISO/IEC 14882:2011"
. ISO. 2 September 2011
. Retrieved
3 September
2011
"Creating and Controlling a Random Number Stream"
. MathWorks
. Retrieved
7 June
2021
"The MMIX Supplement to The Art of Computer Programming"
mmix.cs.hm.edu
. Retrieved
2026-02-10
rand
srand
—pseudo-random numbers"
Newlib git repository
. Retrieved
2024-01-13
"GNU Scientific Library: gsl_rng_vax"
The Open Group Base Specifications Issue 7
IEEE Std 1003.1, 2013 Edition
Stephen J. Chapman.
"Example 6.4 – Random Number Generator".
"MATLAB Programming for Engineers"
2015.
pp. 253–256.
Stephen J. Chapman.
"Example 6.4 – Random Number Generator".
"MATLAB Programming with Applications for Engineers"
2012.
pp. 292–295.
S. J. Chapman.
random0
2004.
Stephen J. Chapman.
"Introduction to Fortran 90/95"
1998.
pp. 322–324.
Wu-ting Tsai.
"'Module': A Major Feature of the Modern Fortran"
Archived
2021-02-24 at the
Wayback Machine
pp. 6–7.
Cadot, Sidney.
"rand.s"
cc65
. Retrieved
8 July
2016
Cadot, Sidney.
"rand.s"
cc65
. Retrieved
10 March
2025
O'Neill, Melissa E. (5 September 2014).
PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
(PDF)
(Technical report).
Harvey Mudd College
. pp.
6–
7. HMC-CS-2014-0905.
Heath, David; Sanchez, Paul (June 1986).
"On the adequacy of pseudo-random number generators (or: How big a period do we need?)"
Operations Research Letters
(1):
3–
6.
doi
10.1016/0167-6377(86)90092-1
Tezuka, Shu; L'Ecuyer, Pierre (October 1993).
On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators
(PDF)
. Workshop on Stochastic Numerics. Kyoto University.
Tezuka, Shi; L'Ecuyer, Pierre (December 1992).
Analysis of Add-with-Carry and Subtract-with-Borrow Generators
(PDF)
. Proceedings of the 1992 Winter Simulation Conference. pp.
443–
447.
Gershenfeld, Neil
(1999). "Section 5.3.2: Linear Feedback".
The Nature of Mathematical Modeling
(First ed.). Cambridge University Press. p.
59
ISBN
978-0-521-57095-4
Matsumoto, Makoto; Nishimura, Takuji (January 1998).
"Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator"
(PDF)
ACM Transactions on Modeling and Computer Simulation
(1):
3–
30.
CiteSeerX
10.1.1.215.1141
doi
10.1145/272991.272995
S2CID
3332028
. Archived from
the original
(PDF)
on 2017-11-07.
Eastlake, Donald E. 3rd; Schiller, Jeffrey I.; Crocker, Steve (June 2005).
"Traditional Pseudo-random Sequences"
Randomness Requirements for Security
IETF
. sec. 6.1.3.
doi
10.17487/RFC4086
. BCP 106.
RFC
4086
References
edit
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007),
"Section 7.1.1. Some History"
Numerical Recipes: The Art of Scientific Computing
(3rd ed.), New York: Cambridge University Press,
ISBN
978-0-521-88068-8
, archived from
the original
on 2011-08-11
, retrieved
2011-08-10
Gentle, James E., (2003).
Random Number Generation and Monte Carlo Methods
, 2nd edition, Springer,
ISBN
0-387-00178-6
Joan Boyar
(1989).
"Inferring sequences produced by pseudo-random number generators"
(PDF)
Journal of the ACM
36
(1):
129–
141.
doi
10.1145/58562.59305
S2CID
3565772
. Archived from
the original
(PDF)
on 2013-04-30
. Retrieved
2019-03-25
(in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).
External links
edit
The simulation
Linear Congruential Generator
visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
Security of Random Number Generation: An Annotated Bibliography
Linear Congruential Generators post to sci.math
The "Death of Art" computer art project at Goldstein Technologies LLC, uses an LCG to generate 33,554,432 images
P. L'Ecuyer and R. Simard,
"TestU01: A C Library for Empirical Testing of Random Number Generators"
, May 2006, revised November 2006,
ACM Transactions on Mathematical Software
, 33, 4, Article 22, August 2007.
Article about another way of cracking LCG
Retrieved from "
Categories
Pseudorandom number generators
Modular arithmetic
Hidden categories:
Webarchive template wayback links
Articles with short description
Short description is different from Wikidata
Articles needing additional references from July 2021
All articles needing additional references
All articles with unsourced statements
Articles with unsourced statements from November 2017
Articles with example Python (programming language) code
Linear congruential generator
Add topic