randomgen.pcg32.PCG32.advance

PCG32.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:

PCG32

Warning

Do not use advance with a large power of two, such as 2**63 (half of the period), to split a single stream (the same seed and inc) into several. The state is an LCG modulo 2**64, whose lowest e bits repeat every 2**e steps, so advancing by 2**e leaves them unchanged. After advance(2**63), the two states differ only in their top bit at every step, and each output is the other with its 16-bit halves swapped and one bit flipped.

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

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**64. The period of PCG32 is short enough for this to limit real applications, for example to about 1.4 * 10**7 streams of 10**12 draws. Use PCG64, or the related PCG64DXSM or LCG128Mix, when many streams or many draws per stream are needed. 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.

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 32 of the 64 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**64, so n streams are only guaranteed not to overlap when n * step <= 2**64.

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 = 32 gives 0x9e3779b9, about 2.7 * 10**9 draws per stream, and XX = 64 gives 0x9e3779b97f4a7c15, the step of jumped. With XX = 64 the multiples of the step wrap around the period, and the golden ratio spreads the streams evenly around it.

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

The period of PCG32, 2**64, is short enough for n * step <= 2**64 to limit the number of streams in practice. With the step from advance_step, the largest number of streams that are guaranteed not to overlap is

Draws per stream

Streams

10**6

1.4 * 10**13

10**9

1.4 * 10**10

10**12

1.4 * 10**7

10**15

13,254

10**18

12

The step from advance_step is less than twice the number of draws per stream, so n streams of m draws always fit when n * m <= 2**63. When many streams or many draws per stream are needed, use PCG64, or the related PCG64DXSM or LCG128Mix. Their period of 2**128 allows about 2.5 * 10**26 streams of 10**12 draws.

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. 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.