Skip to content

Commit d9e5c2b

Browse files
rzehumatMatej Rzehulkapaulromano
authored
[docs] theory on PCG random number generator (openmc-dev#3134)
Co-authored-by: Matej Rzehulka <matej.rzehulka@suro.cz> Co-authored-by: Paul Romano <paul.k.romano@gmail.com>
1 parent 98510f0 commit d9e5c2b

2 files changed

Lines changed: 30 additions & 12 deletions

File tree

‎docs/source/methods/random_numbers.rst‎

Lines changed: 28 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -7,14 +7,19 @@ Random Number Generation
77
In order to sample probability distributions, one must be able to produce random
88
numbers. The standard technique to do this is to generate numbers on the
99
interval :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
1111
correlation between successive terms. Since the numbers produced this way are
1212
not truly "random" in a strict sense, they are typically referred to as
1313
pseudorandom numbers, and the techniques used to generate them are pseudorandom
1414
number generators (PRNGs). Numbers sampled on the unit interval can then be
1515
transformed for the purpose of sampling other continuous or discrete probability
1616
distributions.
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
------------------------------
1924
Linear Congruential Generators
2025
------------------------------
@@ -37,8 +42,8 @@ be generated with a method chosen at random. Some theory should be used."
3742
Typically, :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
3944
constants 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

4348
Skip-ahead Capability
4449
---------------------
@@ -50,23 +55,35 @@ want to skip ahead :math:`N` random numbers and :math:`N` is large, the cost of
5055
sampling :math:`N` random numbers to get to that position may be prohibitively
5156
expensive. Fortunately, algorithms have been developed that allow us to skip
5257
ahead 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
5460
relationship:
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

‎src/random_lcg.cpp‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,8 @@ constexpr uint64_t prn_stride {152917LL}; // stride between particles
1717
//==============================================================================
1818

1919
// 64 bit implementation of the PCG-RXS-M-XS 64-bit state / 64-bit output
20-
// geneator Adapted from: https://github.com/imneme/pcg-c
20+
// geneator Adapted from: https://github.com/imneme/pcg-c, in particular
21+
// https://github.com/imneme/pcg-c/blob/83252d9c23df9c82ecb42210afed61a7b42402d7/include/pcg_variants.h#L188-L192
2122
// @techreport{oneill:pcg2014,
2223
// title = "PCG: A Family of Simple Fast Space-Efficient Statistically Good
2324
// Algorithms for Random Number Generation", author = "Melissa E. O'Neill",

0 commit comments

Comments
 (0)