PRNG is a collection of algorithms for generating pseudorandom numbers as a library of C functions, released under the GPL. It has been written by Otmar Lendl (lendl@cosy.sbg.ac.at) and is now maintained by Josef Leydold (leydold@statistik.wuwien.ac.at).
The current version of this package can always be found on the ARVAG (Automatic Random VAriate Generation) project group in Vienna, or the pLab server in Salzburg.
In the case of any troubles, bug reports or need of assistance please contact the maintainer via prng@statistik.wuwien.ac.at. Please let us also know about your experiencies with the library.
Fixed parameter PRNG (external generators):
plus the following methods (metagenerators):
While the code is plain ANSI C and thus quite portable, the following adaptions might be neccessary for compile this library.
All configurations are done in the file src/prng.h. Each option is extensively commented there. Here is a quick rundown on what to expect there:
prng_num
. It is not
recommended to change this. For 32 and 64 bit computers all
neccessary auxiliary definitions will be made automatically.
For other architectures, please edit prng.h according to the comments.
prng_inverse
. In previous versions, there was no
algorithm which was fastest on all architectures, thus is was
necessary configure the library for the each platform.
Now prng_inverse_own, which combines the speedups of all
old algorithms is the fastest one on all tested architectures
and thus no configuration is necessary any more.
The code is optimized for GNU CC (gcc). If your compiler supports the type
(long long int
), too, you can use this feature by defining
HAVE_LONGLONG
in prng.h.
Then do:
./configure prefix=<prefix_path> make
This should compile the library (libprng.a) and example programs.
To install the library (see also GNU generic installation instructions in file INSTALL) type:
make install
which installs <prefix_path>/lib/libprng.a,
<prefix_path>/include/prng.h, and
<prefix_path>/info/prng.info.
If prefix
is omitted, then /usr/local
is used as
default.
It is possible to remove these files by
make uninstall
I could not test this code in many environments, thus it might be necessary to tweak the code to compile it. Please mail me any changes you made, so that I can include them in the next official release.
A manual can be found in directory doc in various formats, including PS, PDF, HTML, Info and plain text.
Do
make check
to make and run the following executables:
euclid_table
algorithm. It's NOT kept up to date.
Use at own risk.
The interface has changed dramatically in version 2.0. As more and more generator types were added to this package, a new generic interface was needed. While still plain Ansi C, the architecture is now objectoriented.
All generators are identified by a textual description. This description
is either of the form "type(parameter1,parameter2, ...)"
or is a
shortcut name for a common PRNG as defined in src/prng_def.h.
Calling prng_new with such a description as the only argument will
allocate a new generator object, initialize it, and return its handle
(struct prng *
).
All further calls need this handle as the first argument. They are best explained by example:
#include <prng.h> /* make sure that the compiler can find this file. */ main() { struct prng *g; prng_num seed, n, M; double next, *array; int count; g = prng_new("eicg(2147483647,111,1,0)"); if (g == NULL) /* always check whether prng_new has been successful */ { fprintf(stderr,"Initialisation of generator failed.\n"); exit (1); } printf("Short name: %s\n",prng_short_name(g)); /* definition as in call to prng_new */ printf("Expanded name: %s\n",prng_long_name(g)); /* Shortcuts expanded */ next = prng_get_next(g); /* get next number 0 <= next < 1 */ prng_get_array(g,array,count); /* fill array with count numbers */ prng_reset(g); /* reset the generator */ prng_free(g); /* deallocate the generator object */ }
These functions work with all generators. For certain generators, the following functions are available, too:
if (prng_is_congruential(g)) { n = prng_get_next_int(g); /* return next *unscaled* number */ M = prng_get_modulus(g); /* return the modulus of the prng */ } if (prng_can_seed(g)) prng_seed(g,seed); /* reseed the generator */ if (prng_can_fast_sub(g)) puts(prng_get_sub_def(g,20,0)); /* Get subsequence definition */ if (prng_can_fast_con(g)) puts(prng_get_con_def(g,20,1)); /* Get block definition */
NOTE
prng_new performs only a rudimentary check on the parameters.
The user is responsible for enforcing all restrictions
on the parameters, such as checking that the modulus of an [E]ICG is
prime, or that LCG and ICG are maximum period generators.
Most of these functions are implemented as macros, so be
careful with autoincrements (++
) in parameters.
Create a new generator object. If initialisation of the generator object fails then
NULL
is returned. Thus the pointer returned by this routine must be checked againstNULL
before using it. Otherwise the program aborts with a segmentation fault.
Sample from generator (get next pseudorandom number from stream).
Sample array of length count.
Sample integer random number from generator.
Get name of generator as in call to prng_new.
Get name of generator with shortcuts expanded.
TRUE
if g is a congruential generator.
TRUE
if subsequences of the random stream can computed directly.
Get definition for the generator of the subsequence stream of g with starting point i and stepwidth s. It returns a character string that can be used a argument for prng_new. For generators where
prng_can_fast_sub
isTRUE
. (see also SUB).
TRUE
if blocks of the random stream can computed directly.
Get definition for the generator of the blocked stream of g with position i and block length l. It returns a character string that can be used a argument for prng_new. For generators where
prng_can_fast_con
isTRUE
. (see also CON).
examples/pairs.c is an example how to generate overlapping pairs of PRN using this package.
examples/tuples.c is a more general version of pairs.
This chapter lists the implemented generators plus a few recommendations on the parameters.
and disable the check for power of
two moduli in mult_mod_setup
(support.c). Run the supplied
validate program if you have doubts about this.
IT IS THUS NOT A GOOD IDEA TO JUST USE ARBITRARY NUMBERS.
This chapter contains recommended values for all implemented generator types.
TeX notation is used.
Most generators operate in the group (or field) Z_p and generate a sequence y_n, n >= 0 of numbers in Z_p. p is called modulus. In order to generate U([0,1[) distributed numbers, the y_n are scaled: x_n = y_n / p.
Notice: If p is prime, one can define the inversion inv() so that
inv(a)*a mod p = 1 (a != 0) inv(0) = 0
y_n = inv(a*(n_0 + n) + b) (mod p) n >= 0
"eicg(p,a,b,n_0)"
TRUE
TRUE
. TRUE
.
y_n = a * inv(y_{n1}) + b (mod p) n > 0
"icg(p,a,b,y_0)"
TRUE
.
TRUE
. y_{n1}
in the next call to get_next.
FALSE
.
If ICG(p,a,1) has period length p, then ICG(p,a*c^2,c) will have period length p, too. For recommended parameters see Table_ICG.
y_n = a * y_{n1} + b (mod p) n > 0
"lcg(p,a,b,y_0)"
.
TRUE
.
TRUE
.
The parameter of prng_seed will be used as
y_{n1}
in the next call to get_next.
TRUE
. If p is prime and b = 0 then any primeroot modulo p as a will guarantee period length p1. (y_0 != 0 )
For recommended parameters see Table_LCG.
See also the file src/prng_def.h for a list of frequently used LCGs.
Hint: A rule of thumb suggests not to use more than sqrt(p) random numbers from an LCG.
References:
Fishman, G.S. "Multiplicative congruential random number generators ..." Math. Comp. 54:331344 (1990);
L'Ecuyer, P., "Efficient and portable combined random number generators" Comm. ACM 31:742749, 774 (1988)
L'Ecuyer, P., Blouin, F. and Couture R. "A search for good multiple recursive random number generators" ACM Trans. Modelling and Computer Simulation 3:8798 (1993)
The LCG is the classical method. I refer to: Knuth, D. E. "The Art of Computer Programming, Vol. 2 Seminumerical Algorithms", AddisonWesley, second edition, 1981
y_n = a * y_{n1}^2 + b *y_{n1} + c (mod p) n > 0
"qcg(p,a,b,c,y0)"
.
TRUE
.
TRUE
. y_{n1}
in the next call to get_next.
FALSE
.
If p is a power of 2, then a even, b == a + 1 mod 4, and c odd will guarantee period length = p.
No table of good parameters has been published.
Knuth, D. E. "The Art of Computer Programming, Vol. 2 Seminumerical Algorithms", AddisonWesley, second edition, 1981
"mt19937(seed)"
.
TRUE
.
TRUE
. FALSE
.
Matsumoto, M. and Nishimura, T., "Mersenne Twister: A 623Dimensionally Equidistributed Uniform PseudoRandom Number Generator", ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3–30.
y_n = n * inv(a*(n_0 + n) + b) (mod p) n >= 0
"meicg(p,a,b,n_0)"
.
TRUE
.
TRUE
.
The parameter of prng_seed will be used as
"n" in the next call to get_next.
FALSE
.
Experimental generator: USE AT OWN RISK
EichenauerHermann, J. "Modified explicit inverive congruential pseudorandom numbers with power of 2 modulus" Statistics and Computing 6:3136 (1996)
y_n = a * inv(y_{n1}) + b (mod p) n > 0
All operations are in the field F_{2^k} !!
"dicg(k,a,b,y_0)"
.
TRUE
.
TRUE
.
The parameter of prng_seed will be used as
y_{n1}
in the next call to get_next
FALSE
.
Tricky.
EichenauerHerrmann and Niederreiter, "Digital inversive pseudorandom numbers", ACM Transactions on Modeling and Computer Simulation, 4:339349 (1994)
These generators are included to provide a uniform interface to a wider range of PRNG. The only enhancements from the published code is the support for multiple streams of these generators, as the original code used global variables.
See the file src/external.c for the references. Included are
This is a "meta"generator which combines a number of PRNG into one single generator by adding the respective numbers modulo 1.
"c(generator1,generator2, ...)"
.
Up to PRNG_MAX_COMPOUNDS
generators are permitted.
generatorX may be any valid generator definition, including
a compound generator.
FALSE
.
TRUE
.
"sub(gen,s,i)"
.
The output of "gen" is spliced into s streams, and the ith is used. (0 <= i < s)
FALSE
.
This is a "meta"generator wich returns 1U instead of U as random number.
"anti(gen)"
.
The output of gen (U) is changed to 1U.
This is a "meta"generator which takes a block of numbers out of the output of another generator.
"con(gen,l,i)"
.
The output of "gen" is divided into blocks of length l, and the ith is used. (0 <= i < l)
FALSE
.
This generator takes its numbers from the named file. It expects each number in plain ascii (atof must be able to parse it) and on its own line. If EOF is reached, a warning is printed to stderr and reading continues at the beginning of the file.
"afile(some_file_name)"
.
FALSE
.
FALSE
.
FALSE
.
This generator takes its numbers from the named file. In order to get good numbers, the file should contain random bytes. If EOF is reached, a warning is printed to stderr and reading continues at the beginning of the file.
"bfile(some_file_name)"
.
WARNING: The conversion between bytes and numbers in [0,1) is NOT guaranteed to yield the same results on different computers.
FALSE
.
FALSE
.
FALSE
.
Niederreiter, H. "New developments in uniform pseudorandom number and vector generation" in "Monte Carlo and QuasiMonte Carlo Methods in Scientific Computing", Lecture Notes in Statistics, Springer.
Hellekalek, P. "Inversive pseudorandom number generators: Concepts, Results and Links"
EichenauerHerrmann, J. "Pseudorandom Number Generation by Nonlinear Methods" Int. Statistical Review 63:247255 (1995)
L'Ecuyer, P. "Uniform random number generation" Ann. Oper. Res. 53:77120 (1994)
Wegenkittl, S. "Empirical testing of pseudorandom number generators" Master's thesis, Universitaet Salzburg, 1995
This chapter lists the implemented generators plus a few recommendations on the parameters.
y_n = a * y_{n1} + b (mod p) n > 0
Hint: A rule of thumb suggests not to use more than sqrt(p) random numbers from an LCG.
Notice that moduli larger than 2^32 require a computer with
sizeof(long)>32
.
Generators recommended by Park and Miller (1988), "Random number generators: good ones are hard to find", Comm. ACM 31, pp. 11921201 (Minimal standard).
modul p  multiplicator a
 
—————–  —————————————
 
2^31  1 =  2147483647  16807 (b = 0)

Generators recommended by Fishman (1990), “Multiplicative congruential random number generators with modulus 2^beta: An exhaustive analysis for beta=32 and a partial analysis for beta=48”, Math. Comp. 54, pp. 331344.
modul p  multiplicator a
 
—————–  —————————————
 
2^31  1 =  2147483647  950706376 (b = 0)

Generators recommended by L'Ecuyer (1999), "Tables of linear congruential generators of different sizes and good lattice structure", Math.Comp. 68, pp. 249260. (constant b = 0.)
Generators with short periods can be used for generating quasirandom numbers (QuasiMonte Carlo methods). In this case the whole period should be used.
(These figures are listed without warranty. Please see also the original paper.)
modul p  multiplicator a
 
—————–  —————————————
 
2^8  5 =  251  33

55
 
 
2^9  3 =  509  25

110
 
273
 
349
 
 
2^10  3 =  1021  65

331
 
 
2^11  9 =  2039  995

328
 
393
 
 
2^12  3 =  4093  209

235
 
219
 
3551
 
 
2^13  1 =  8191  884

1716
 
2685
 
 
2^14  3 =  16381  572

3007
 
665
 
12957
 
 
2^15  19 =  32749  219

1944
 
9515
 
22661
 
 
2^16  15 =  65521  17364

33285
 
2469
 
 
2^17  1 =  131071  43165

29223
 
29803
 
 
2^18  5 =  262139  92717

21876
 
 
2^19  1 =  524287  283741

37698
 
155411
 
 
2^20  3 =  1048573  380985

604211
 
100768
 
947805
 
22202
 
1026371
 
 
2^21  9 =  2097143  360889

1043187
 
1939807
 
 
2^22  3 =  4194301  914334

2788150
 
1731287
 
2463014
 
 
2^23  15 =  8388593  653276

3219358
 
1706325
 
6682268
 
422527
 
7966066
 
 
2^24  3 =  16777213  6423135

7050296
 
4408741
 
12368472
 
931724
 
15845489
 
 
2^25  39 =  33554393  25907312

12836191
 
28133808
 
25612572
 
31693768
 
 
2^26  5 =  67108859  26590841

19552116
 
66117721
 
 
2^27  39 =  134217689  45576512

63826429
 
3162696
 
 
2^28  57 =  268435399  246049789

140853223
 
29908911
 
104122896
 
 
2^29  3 =  536870909  520332806

530877178
 
 
2^30  35 =  1073741789  771645345

295397169
 
921746065
 
 
2^31  1 =  2147483647  1583458089

784588716
 
 
2^32  5 =  4294967291  1588635695

1223106847
 
279470273
 
 
2^33  9 =  8589934583  7425194315

2278442619
 
7312638624
 
 
2^34  41 =  17179869143  5295517759

473186378
 
 
2^35  31 =  34359738337  3124199165

22277574834
 
8094871968
 
 
2^36  5 =  68719476731  49865143810

45453986995
 
 
2^37  25 =  137438953447  76886758244

2996735870
 
85876534675
 
 
2^38  45 =  274877906899  17838542566

101262352583
 
24271817484
 
 
2^39  7 =  549755813881  61992693052

486583348513
 
541240737696
 
 
2^40  87 =  1099511627689  1038914804222

88718554611
 
937333352873
 
 
2^41  21 =  2199023255531  140245111714

416480024109
 
1319743354064
 
 
2^42  11 =  4398046511093  2214813540776

2928603677866
 
92644101553
 
 
2^43  57 =  8796093022151  4928052325348

4204926164974
 
3663455557440
 
 
2^44  17 =  17592186044399  6307617245999

11394954323348
 
949305806524
 
 
2^45  55 =  35184372088777  25933916233908

18586042069168
 
20827157855185
 
 
2^46  21 =  70368744177643  63975993200055

15721062042478
 
31895852118078
 
 
2^47  115 =  140737488355213  72624924005429

47912952719020
 
106090059835221
 
 
2^48  59 =  281474976710597  49235258628958

51699608632694
 
59279420901007
 
 
2^49  81 =  562949953421231  265609885904224

480567615612976
 
305898857643681
 
 
2^50  27 =  1125899906842597  1087141320185010

157252724901243
 
791038363307311
 
 
2^51  129 =  2251799813685119  349044191547257

277678575478219
 
486848186921772
 
 
2^52  47 =  4503599627370449  4359287924442956

3622689089018661
 
711667642880185
 
 
2^53  111 =  9007199254740881  2082839274626558

4179081713689027
 
5667072534355537
 
 
2^54  33 =  18014398509481951  9131148267933071

3819217137918427
 
11676603717543485
 
 
2^55  55 =  36028797018963913  33266544676670489

19708881949174686
 
32075972421209701
 
 
2^56  5 =  72057594037927931  4595551687825993

26093644409268278
 
4595551687828611
 
 
2^57  13 =  144115188075855859  75953708294752990

95424006161758065
 
133686472073660397
 
 
2^58  27 =  288230376151711717  101565695086122187

163847936876980536
 
206638310974457555
 
 
2^59  55 =  576460752303423433  346764851511064641

124795884580648576
 
573223409952553925
 
 
2^60  93 =  1152921504606846883  561860773102413563

439138238526007932
 
734022639675925522
 
 
2^61  1 =  2305843009213693951  1351750484049952003

1070922063159934167
 
1267205010812451270
 
 
2^62  57 =  4611686018427387847  2774243619903564593

431334713195186118
 
2192641879660214934
 
 
2^63  25 =  9223372036854775783  4645906587823291368

2551091334535185398
 
4373305567859904186
 
 
2^64  59 =  18446744073709551557  13891176665706064842

2227057010910366687
 
18263440312458789471

y_n = a * inv(y_{n1}) + b (mod p) n > 0
Notice that moduli larger than 2^32 require a computer with
sizeof(long)>32
.
Parameters suggested by P. Hellekalek (1995), “Inversive pseudorandom number generators: Concepts, Results and Links”, in: C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman (eds.), Proceedings of the 1995 Winter Simulation Conference, pp. 255262:
There are no results that give reason to prefer one set of parameters over another.
(These figures are listed without warranty. Please see also the original paper.)
p  a  b

————  ————  ————

1031  849  1

345  1
 
55  1
 
116  1
 
441  1
 
 
1033  413  1

878  1
 
595  1
 
522  1
 
818  1
 
 
1039  173  1

481  1
 
769  1
 
1028  1
 
136  1
 
 
2027  579  1

1877  1
 
390  1
 
837  1
 
1048  1
 
 
2147483053  858993221  1

22211  11926380
 
579  24456079
 
11972  62187060
 
21714  94901263
 
4594  44183289
 
 
2147483647  1288490188  1

9102  36884165
 
14288  758634
 
21916  71499791
 
28933  59217914
 
31152  48897674
