randomgen.pcg64.PCG64.advance¶

PCG64.advance(delta)¶

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

Parameters:¶

delta¶: Number of draws to advance the RNG. Must be less than the size state variable in the underlying RNG.

Returns:¶

self – RNG advanced delta steps

Return type:¶

PCG64

Warning

Do not use advance with a large power of two, such as 2**127 (half of the period), to split a single stream (the same seed and inc) into several. The state is an LCG modulo 2**128, whose lowest e bits repeat every 2**e steps, so advancing by 2**e leaves them unchanged. After advance(2**127), the two states differ only in their top bit at every step, and the outputs are strongly related:

"xsl-rr": each output is the other with its 32-bit halves swapped and one bit flipped. More generally, advancing by 2**(128 - t) gives outputs that are rotations of each other with at most t bits flipped.
"dxsm", "dxsm-128" and PCG64DXSM: the two outputs are never congruent modulo 4, so their last hexadecimal digits never coincide, and PractRand fails the interleaved streams at 1 MB.

After advance(2**64), the states differ in about 32 of their 128 bits and never in the lowest 64.

The size of the step also matters. Stream i, advanced by i * step, can make at most step draws before it reaches the start of stream i + 1, and n streams are only guaranteed not to overlap when n * step <= 2**128. advance_step returns an odd step for a given number of draws per stream, and the Notes explain how to choose one.

See also

advance_step: Step for splitting one stream into several.

Notes

Advancing a RNG updates the underlying RNG state as-if a given number of calls to the underlying RNG have been made. In general there is not a one-to-one relationship between the number output random values from a particular distribution and the number of draws from the core RNG. This occurs for two reasons:

The random values are simulated using a rejection-based method and so, on average, more than one value from the underlying RNG is required to generate an single draw.
The number of bits required to generate a simulated value differs from the number of bits generated by the underlying RNG. For example, two 16-bit integer values can be simulated from a single draw of a 32-bit RNG.

Advancing the RNG state resets any pre-computed random numbers. This is required to ensure exact reproducibility.

To split one stream into several, advance stream i by i * step with an odd step. With an odd step, the states of two streams differ in their lowest bit at every step and their other bits differ as if at random: about 64 of the 128 bits differ, with the spread of a binomial distribution. Only the lowest few bits follow a fixed pattern, since in any LCG they repeat every few steps. This holds for an odd step of any size. The size sets how far apart the streams are: stream i reaches the start of stream i + 1 after step draws, so step must be at least the number of draws that any stream makes. The starts i * step are taken modulo the period, 2**128, so n streams are only guaranteed not to overlap when n * step <= 2**128. This is not a practical limit: streams of 10**12 draws allow about 2.5 * 10**26 streams.

A convenient step is the odd integer closest to 2**XX / phi, where phi is the golden ratio and XX is chosen so that the step is at least the number of draws per stream. advance_step(max_draws) returns this step for the smallest XX that works, using only integer arithmetic. For example, XX = 48 gives 0x9e3779b97f4b, about 1.7 * 10**14 draws per stream, XX = 64 gives 0x9e3779b97f4a7c15, about 1.1 * 10**19, and XX = 128 gives 0x9e3779b97f4a7c15f39cc0605cedc835, the step of jumped and of NumPy’s PCG64.jumped. With XX = 128 the multiples of the step wrap around the period, and the golden ratio spreads the streams evenly around it.

>>> step = PCG64.advance_step(10**10)
>>> hex(step)
'0x278dde6e5'
>>> streams = [PCG64(1234).advance(i * step) for i in range(8)]

Streams i and j are (j - i) * step draws apart, so they share the lowest v bits of their states, where 2**v is the largest power of two that divides j - i. With fewer than 2**20 streams that is at most 19 bits. NumPy reports that two XSL-RR streams that share their lowest 58 bits and their increment fail PractRand when interleaved. jumped(iter) advances by iter times a golden-ratio step, so it is also a good choice when iter is not a large power of two.