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.wu-wien.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.wu-wien.ac.at. Please let us also know about your experiencies with the library.
Fixed parameter PRNG (external generators):
plus the following methods (meta-generators):
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 object-oriented.
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
NULLis returned. Thus the pointer returned by this routine must be checked againstNULLbefore using it. Otherwise the program aborts with a segmentation fault.
Sample from generator (get next pseudo-random 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.
TRUEif g is a congruential generator.
TRUEif 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_subisTRUE. (see also SUB).
TRUEif 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_conisTRUE. (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_{n-1}) + b (mod p) n > 0
"icg(p,a,b,y_0)"
TRUE.
TRUE. y_{n-1} 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_{n-1} + b (mod p) n > 0
"lcg(p,a,b,y_0)".
TRUE.
TRUE.
The parameter of prng_seed will be used as
y_{n-1} in the next call to get_next.
TRUE. If p is prime and b = 0 then any prime-root modulo p as a will guarantee period length p-1. (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:331-344 (1990);
L'Ecuyer, P., "Efficient and portable combined random number generators" Comm. ACM 31:742-749, 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:87-98 (1993)
The LCG is the classical method. I refer to: Knuth, D. E. "The Art of Computer Programming, Vol. 2 Seminumerical Algorithms", Addison-Wesley, second edition, 1981
y_n = a * y_{n-1}^2 + b *y_{n-1} + c (mod p) n > 0
"qcg(p,a,b,c,y0)".
TRUE.
TRUE. y_{n-1} 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", Addison-Wesley, second edition, 1981
"mt19937(seed)".
TRUE.
TRUE. FALSE.
Matsumoto, M. and Nishimura, T., "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random 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
Eichenauer-Hermann, J. "Modified explicit inverive congruential pseudorandom numbers with power of 2 modulus" Statistics and Computing 6:31-36 (1996)
y_n = a * inv(y_{n-1}) + 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_{n-1} in the next call to get_next
FALSE.
Tricky.
Eichenauer-Herrmann and Niederreiter, "Digital inversive pseudorandom numbers", ACM Transactions on Modeling and Computer Simulation, 4:339-349 (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 i-th is used. (0 <= i < s)
FALSE.
This is a "meta"-generator wich returns 1-U instead of U as random number.
"anti(gen)".
The output of gen (U) is changed to 1-U.
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 i-th 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 Quasi-Monte Carlo Methods in Scientific Computing", Lecture Notes in Statistics, Springer.
Hellekalek, P. "Inversive pseudorandom number generators: Concepts, Results and Links"
Eichenauer-Herrmann, J. "Pseudorandom Number Generation by Nonlinear Methods" Int. Statistical Review 63:247-255 (1995)
L'Ecuyer, P. "Uniform random number generation" Ann. Oper. Res. 53:77-120 (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_{n-1} + 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. 1192-1201 (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. 331-344.
| 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. 249-260. (constant b = 0.)
Generators with short periods can be used for generating quasi-random numbers (Quasi-Monte 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_{n-1}) + 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. 255-262:
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
|