@@ -7,14 +7,19 @@ Random Number Generation
77In order to sample probability distributions, one must be able to produce random
88numbers. The standard technique to do this is to generate numbers on the
99interval :math: `[0 ,1 )` from a deterministic sequence that has properties that
10- make it appear to be random, e.g. being uniformly distributed and not exhibiting
10+ make it appear to be random, e.g., being uniformly distributed and not exhibiting
1111correlation between successive terms. Since the numbers produced this way are
1212not truly "random" in a strict sense, they are typically referred to as
1313pseudorandom numbers, and the techniques used to generate them are pseudorandom
1414number generators (PRNGs). Numbers sampled on the unit interval can then be
1515transformed for the purpose of sampling other continuous or discrete probability
1616distributions.
1717
18+ There are many different algorithms for pseudorandom number generation. OpenMC
19+ currently uses `permuted congruential generator `_ (PCG), which builds on top of
20+ the simpler linear congruential generator (LCG). Both algorithms are described
21+ below.
22+
1823------------------------------
1924Linear Congruential Generators
2025------------------------------
@@ -37,8 +42,8 @@ be generated with a method chosen at random. Some theory should be used."
3742Typically, :math: `M` is chosen to be a power of two as this enables :math: `x
3843\mod M` to be performed using the bitwise AND operator with a bit mask. The
3944constants for the linear congruential generator used by default in OpenMC are
40- :math: `g = 2806196910506780709 `, :math: `c = 1 `, and :math: `M = 2 ^{63 }` (see
41- `L'Ecuyer `_).
45+ :math: `g = 2806196910506780709 `, :math: `c = 1 `, and :math: `M = 2 ^{63 }` (from
46+ `L'Ecuyer < https://doi.org/10.1090/S0025-5718-99-00996-5 > `_).
4247
4348Skip-ahead Capability
4449---------------------
@@ -50,23 +55,35 @@ want to skip ahead :math:`N` random numbers and :math:`N` is large, the cost of
5055sampling :math: `N` random numbers to get to that position may be prohibitively
5156expensive. Fortunately, algorithms have been developed that allow us to skip
5257ahead in :math: `O(\log _2 N)` operations instead of :math: `O(N)`. One algorithm
53- to do so is described in a paper by Brown _. This algorithm relies on the following
58+ to do so is described in a `paper by Brown
59+ <https://www.osti.gov/biblio/976209> `_. This algorithm relies on the following
5460relationship:
5561
5662.. math ::
5763 :label: lcg-skipahead
5864
5965 \xi _{i+k} = g^k \xi _i + c \frac {g^k - 1 }{g - 1 } \mod M
6066
61- Note that equation :eq: `lcg-skipahead ` has the same general form as equation :eq: ` lcg `, so
62- the idea is to determine the new multiplicative and additive constants in
63- :math: `O(\log _2 N)` operations.
67+ Note that equation :eq: `lcg-skipahead ` has the same general form as equation
68+ :eq: ` lcg `, so the idea is to determine the new multiplicative and additive
69+ constants in :math: `O(\log _2 N)` operations.
6470
65- .. only :: html
6671
67- .. rubric :: References
72+ --------------------------------
73+ Permuted Congruential Generators
74+ --------------------------------
6875
76+ The `permuted congruential generator `_ (PCG) algorithm aims to improve upon the
77+ LCG algorithm by permuting the output. The algorithm works on the basic
78+ principle of first advancing the generator state using the LCG algorithm and
79+ then applying a permutation function on the LCG state to obtain the output. This
80+ results in increased statistical quality as measured by common statistical tests
81+ while exhibiting a very small performance overhead relative to the LCG algorithm
82+ and an equivalent memory footprint. For further details, see the original
83+ technical report by `O'Neill
84+ <https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf> `_. OpenMC uses the
85+ PCG-RXS-M-XS variant with a 64-bit state and 64-bit output.
6986
70- .. _L'Ecuyer : https://doi.org/10.1090/S0025-5718-99-00996-5
71- .. _Brown : https://laws.lanl.gov/vhosts/mcnp.lanl.gov/pdf_files/anl-rn-arb-stride.pdf
7287.. _linear congruential generator : https://en.wikipedia.org/wiki/Linear_congruential_generator
88+
89+ .. _permuted congruential generator : https://en.wikipedia.org/wiki/Permuted_congruential_generator
0 commit comments