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 a SeedSequence 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 a Generator 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 a SeedSequence. 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

[1] (1,2)

“PCG, A Family of Better Random Number Generators”, https://www.pcg-random.org/

[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 a SeedSequence.

>>> 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([seed, inc])

Seed the generator

state

Get or set the PRNG state

Parallel generation

advance(delta)

Advance the underlying RNG as-if delta draws have occurred.

jumped([iter])

Returns a new bit generator with the state jumped

Extending

cffi

CFFI interface

ctypes

ctypes interface

Testing

random_raw([size, output])

Return randoms as generated by the underlying BitGenerator