128-bit Linear Congruential Generator (LCG) with Output Mixing¶
- class randomgen.pcg64.LCG128Mix(seed=None, inc=None, *, multiplier=47026247687942121848144207491837523525, output='xsl-rr', dxsm_multiplier=15750249268501108917, post=True)¶
Customizable 128-bit LCG bit generator with output mixing
Support changing the LCG’s multiplier and the output function, including support for user-defined output functions. This big generator is based on the PCG64 generator in [1] and [2] but adds additional options that allow the multiplier to be changed (see [3] for a list of good multipliers). It has been added based on the discussion in [4].
- Parameters:
- seed{None, int, array_like[int] SeedSequence}, optional
Random seed initializing the pseudo-random number generator. Can be an integer, a sequence of integers, a SeedSequence instance or None (the default). If seed is None, then
PCG64
use aSeedSequence
initialized with system-provided entropy.- inc{None, int}, optional
The increment in the LCG. Can be an integer in [0, 2**128) or None. If inc is None, then it is initialized using the same``SeedSequence`` used by seed.
- multiplierint, optional
The multipler to use in the LCG. Must be an odd integer in (0, 2**128).
- output{str, CFunction, FuncPtr}
The name of the output function or a ctypes function or function pointer with a signature uint64(uint64, uint64). Supported options are:
“xsl-rr” - Use the XSL-RR output mixed. This mixer is used in PCG 1.0.
“dxsm” - Use the DXSM output mixer. This mixer is used in PCG 2.0.
“upper” - Use the upper 64 bits of the LCG’s state.
“lower” - Use the lower 64 bits of the LCG’s state.
“murmur3” - Apply the MurMur3 hash to the upper 64 bits of the LCG’s state.
- dxsm_multiplierint, optional
The multiplier to use in the DXSM output function. The default is the DXSM multipler in PCG 2.0.
- postbool, optional
Whether the mix the output before or after the next increment of the LCG is computed. True updates the state and then mixes the updated state.
Notes
LCG128Mix is a 128-bit of O’Neill’s permuted congruential generator ([1], [2]). Assuming an appropriate multiplier is used (see [3]), LCG128Mix has a period of \(2^{128}\) and supports advancing an arbitrary number of steps.
Random variates are generated by permuting the output of a 128-bit LCG
\[s_{n+1} = m s_{n} + i \mod 2^{128}\]where \(s\) is the state of the generator, \(m\) is the multipler and \(i\) is the increment. The multipler is a 128-bit unsigned integer that should be chosen to have good spectral properties. The output of the LCG is the permuted using a predefined method or a user-defined function.
LCG128Mix
provides a capsule containing function pointers that produce doubles, and unsigned 32 and 64- bit integers. These are not directly consumable in Python and must be consumed by aGenerator
or similar object that supports low-level access.Supports the method advance to advance the RNG an arbitrary number of steps. The state of the LCG128Mix RNG is represented by a 128-bit unsigned integer.
State and Seeding
The
LCG128Mix
state vector consists of an unsigned 128-bit value, which is represented externally as a Python int.LCG128Mix
is seeded using an integer, a sequence of integers, or aSeedSequence
. In addition, a second 128-bit unsigned integer is used as the increment in the LCG.Compatibility Guarantee
LCG128Mix
makes a guarantee that a fixed seed and will always produce the same random integer stream.References
[2] (1,2)O’Neill, Melissa E. “PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation”
[3] (1,2)L’ecuyer, P. (1999). Tables of linear congruential generators of different sizes and good lattice structure. Mathematics of Computation, 68(225), 249-260.
[4]NumPy GitHub Repository. 2020. The PCG Implementation Provided By Numpy Has Significant, Dangerous Self-Correlation. [online] Available at: <https://github.com/numpy/numpy/issues/16313> [Accessed 16 June 2020].
Examples
Custom generators can be created using different multipliers.
>>> lcg_mult = 0x1DA942042E4DD58B5 >>> dxsm_mult = 0xff37f1f758180525 >>> from randomgen import LCG128Mix >>> LCG128Mix(multiplier=lcg_mult, dxsm_multiplier=dxsm_mult, output="dxsm")
Writing an output function in numba. This example uses a Murmur3 hash function to permute the upper half of the LCG’s output.
>>> from numba import cfunc, types >>> @cfunc(types.uint64(types.uint64,types.uint64)) ... def murmur3_mix(hi, lo): ... z = (hi ^ (lo >> 30)) * 0xbf58476d1ce4e5b9 ... z = (z ^ (z >> 27)) * 0x94d049bb133111eb ... return z ^ (z >> 31) >>> cpcg = LCG128Mix(0xDEAD10CC, output=murmur3_mix.ctypes)
Parallel Features
The preferred method to use a
LCG128Mix
is to couple it with aSeedSequence
.>>> from randomgen import SeedSequence, LCG128Mix >>> ss = SeedSequence(37548236789240574857439075) >>> children = ss.spawn(10) >>> bit_gens = [LCG128Mix(child) for child in children]
- Attributes:
- lockthreading.Lock
Lock instance that is shared so that the same bit git generator can be used in multiple Generators without corrupting the state. Code that generates values from a bit generator should hold the bit generator’s lock.
- seed_seq{None, SeedSequence}
The SeedSequence instance used to initialize the generator if mode is “sequence” or is seed is a SeedSequence. None if mode is “legacy”.
Seeding and State¶
| Seed the generator |
Get or set the PRNG state |
Parallel generation¶
| Advance the underlying RNG as-if delta draws have occurred. |
| Returns a new bit generator with the state jumped |
Extending¶
CFFI interface | |
ctypes interface |
Testing¶
| Return randoms as generated by the underlying BitGenerator |