/
minStdRandGenC.c
73 lines (56 loc) · 3.63 KB
/
minStdRandGenC.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/* -*- Mode:C; Coding:us-ascii-unix; fill-column:132 -*- */
/* ****************************************************************************************************************************** */
/**
@file minStdRandGenC.c
@author Mitch Richling <https://www.mitchr.me/>
@Copyright Copyright 1997, 2001, 2006, 2014 by Mitch Richling. All rights reserved.
@brief minimal implementation of the minimal standard random number generator@EOL
@Keywords none
@Std C99
Generate Random Numbers via the "minimal standard" Linear Congruence Generator (LCG)
This is just a simple LCG with a=16807 & m=2147483647. The idea of the LCG was first proposed by Lehmer (1949/1951). This choice
of parameters was first suggested by Lewis, Goodman, & miller (1969). Later, Park and Miller (1998) provided better grounds for
it's use and suggested it as a "minimal standard generator". The name stuck, and they are generally given credit for the choice
of parameters. Note that different values, probably better ones, have been suggested. For example, Park & Miller (1988) suggest
a=48271 or a=69621 because of better spectral test results for randomness -- they have a much tighter hyperplane spacing when
consecutive points are plotted. Still, the minimal standard is widely used.
The random numbers are integers. The period is 2^(31)-1. The random numbers are uniformly distributed.
The period of this generator is is 2^(31)-1; however, it is best to stick with sequences shorter than 46340. For more
information see L'Ecuyer & Hellekalek (1998) and L'Ecuyer, Cordeau, & Simard (2000).
The method of overflow avoidance follows the ideas of L'Ecuyer (1988) and Scharage (1979). Note: The algorithm presented by
Carta (1990) is quite bad, and should be avoided.
Learmonth & Lewis (1973) provide extensive tests of this particular generator.
James Gentle's book "Random Number Generation and Monte Carlo Methods", 2nd Ed, 2005, provides a good overview of all the above
references and solid coverage of this algorithm. I highly recommend it.
This random number generator is sufficient for many non-critical applications. For example, while it exhibits the lattice
structure all LCGs suffer from, it is fine enough to use for Monte Carlo integration of well behaved functions. It can also form
a fine base for shuffle & shift filters.
History:
- Aug 1997: Original version
- Jul 2000: Added doxygen tags to top comment
- Dec 2001: Added safe period comments
- Feb 2006: Added comment regarding Gentle's book Changed comments to c99 style
- Apr 2014 Changed to 132 cols
*/
/* ------------------------------------------------------------------------------------------------------------------------------ */
#include <stdio.h> /* I/O lib ISOC */
#include <stdlib.h> /* Standard Lib ISOC */
/* ------------------------------------------------------------------------------------------------------------------------------ */
int main(int argc, char *argv[]) {
long i, randN, q, r;
long m = 2147483647L; // 2**(31)-1 for MSLCG
long a = 16807; // 7**5 for MSLCG
q = m/a; // 127773 for MSLCG
r = m%a; // 2836 for MSLCG
randN = 1; // Set the seed (first random number)
for(i=0; i<10; i++) {
// Simple (bad) : randN = (a*randN)%m
// L'Ecuyer (1988) : k = randN/q; randN = a * (randN-k*q) - r*k;
// Scharage (1979) : randN = a*(randN%q) - r*(randN/q);
randN = a*(randN%q) - r*(randN/q);
if(randN<0)
randN+=m;
printf("%12ld\n", randN);
}
return 0;
}