Random Stream Generators - openmpp/openmpp.github.io GitHub Wiki
Home > Model Development Topics > Random Stream Generators
Describes the available random number generators and how to select one.
OpenM++ includes four drop-in choices of random number generator (RNG) which can be used by models with no need to change substantive model code.
One of these choices (lcg200) is identical to the Linear Congruential Generator (LCG) family used in Modgen, but includes 200 optimal generators rather than Modgen’s 41 generators. These 200 generators have the best statistical properties in the family of ~500M similar generators, and all are superior to the 41 Modgen RNG’s. There are known issues with some members of the lcg41 family, so it’s probably best to use the lcg200 family if x-compatibility is not required.
The Modgen RNG family (lcg41) is retained so that a model built with OpenM++ can produce identical results to the same model built with Modgen. The lcg41 and lcg200 generators are very fast and very memory efficient.
Another choice is the Mersenne Twister (mt19937). This modern RNG has very good properties, but is slow and memory intensive. Yet another is the ranlux48 generator, which has good properties and is faster and less memory intensive than mt19937. Both these generators are noticeably slowed compared to lcg41 or lcg200. They can be useful to probe that the lcg41 and lcg200 generators are performing reasonably well for a given model.
The use source code modules which implement mt19937 and ranlux48 can be copied and adapted mechanically by changing several lines of C++ code to implement other of the many
RNG families in the C++ standard library.
Each of the random number generators is implemented in a shared use model code module, specified conventionally in a model source file named ompp_framework.ompp. Here’s a line from that file for a case-based model:
use "random/random_lcg41.ompp";This line instructs omc to read that file and compile it to become part of the model. To specify a different RNG family, change the name of the file to one of the code modules in the OM_ROOT/use/random folder, e.g.
use "random/random_mt19937.ompp";or
use "random/random_lcg200.ompp";Case-based models (but not time-based models) use RNG’s not only in model code which calls RandUniform, RandNormal, etc., but also to generate the starting seed of each case. To ensure independence of simulation members (aka subsample, replicate), a distinct RNG is used for each simulation member to generate the starting seeds for each case. Modgen reserves 41 RNG’s for this purpose, so that each simulation member has its own RNG to generate case seeds and its own RNG to implement the random number streams in each simulation member. OpenM++ follows the same approach.
The code module which implements the RNG’s to generate case seeds in case-based models is also specified in ompp_framework.ompp. Case-based models can specify either
use "case_based/case_based_lcg41.ompp";or
use "case_based/case_based_lcg200.ompp";The second option reserves 200 RNG’s to generate case seeds and 200 RNG’s to implement the random number streams using random/random_lcg200.ompp.
Other RNG’s are not supported for case seed generation at this time.
The ~85 generators used in Modgen came from a journal article published in the early 1980’s. I don’t recall how the authors picked those ~85. The article evaluated the randomness properties of the ~85 generators using various criteria. Some were good and some were not so good. Also included was the very widely-used generator with multiplier 16807 which has known defects. Modgen used most, maybe all, of the generators in the article, including not-so-good ones, because it needed that many. A special probe model was designed and run to 'reverse engineer' the Modgen generators and their order to implement the equivalent in OpenM++, because the Modgen source code was not available.
The 400 generators in random_lcg200.ompp and case_based_lcg200.ompp come from a 1986 SIAM article “An Exhaustive Analysis of Multiplicative Congruential Random Number Generators with Modulus 2^31 – 1”. The authors did an exhaustive search of all possible RNG’s in the family (over 500M) and identified those with good lattice properties in {2,3,4,5,6} dimensions. Actually, a mathematical property of this family of generators means that the authors only had to search half of the possible generators, since each generator has a dual generator with identical statistical properties which produces the identical random sequence but in reverse order. Entertainingly (to the authors, perhaps), they only published half of the optimal generators, and teasingly described in a table footnote how to find the other half from the first half. But, SFAIK there is no efficient way to compute a discrete logarithm (if there was, some modern cryptography would fail), so an exhaustive search was required. So I wrote a little C++ program to do that, which enumerated the ~2 billion candidate primitive roots to find the twin of each of the 205 generators in the table published in the article.
I found a typographical error in the article appendix which listed the best multipliers, which I corrected in the two lcg200 use modules.
For more, including the C++ code to find the complementary generators using the primitive roots, see comments in the module use/random/random_lcg200.ompp.