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:¶
Warning
Do not use
advancewith a large power of two, such as2**63(half of the period), to split a single stream (the same seed andinc) into several. The state is an LCG modulo2**64, whose lowestebits repeat every2**esteps, so advancing by2**eleaves them unchanged. Afteradvance(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 byi * step, can make at moststepdraws before it reaches the start of streami + 1, andnstreams are only guaranteed not to overlap whenn * step <= 2**64. The period ofPCG32is short enough for this to limit real applications, for example to about1.4 * 10**7streams of10**12draws. UsePCG64, or the relatedPCG64DXSMorLCG128Mix, when many streams or many draws per stream are needed.advance_stepreturns an odd step for a given number of draws per stream, and the Notes explain how to choose one.See also
advance_stepStep 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
ibyi * stepwith an oddstep. 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: streamireaches the start of streami + 1afterstepdraws, sostepmust be at least the number of draws that any stream makes. The startsi * stepare taken modulo the period,2**64, sonstreams are only guaranteed not to overlap whenn * step <= 2**64.A convenient step is the odd integer closest to
2**XX / phi, where phi is the golden ratio andXXis chosen so that the step is at least the number of draws per stream.advance_step(max_draws)returns this step for the smallestXXthat works, using only integer arithmetic. For example,XX = 32gives0x9e3779b9, about2.7 * 10**9draws per stream, andXX = 64gives0x9e3779b97f4a7c15, the step ofjumped. WithXX = 64the 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 forn * step <= 2**64to limit the number of streams in practice. With the step fromadvance_step, the largest number of streams that are guaranteed not to overlap isDraws per stream
Streams
10**61.4 * 10**1310**91.4 * 10**1010**121.4 * 10**710**1513,254
10**1812
The step from
advance_stepis less than twice the number of draws per stream, sonstreams ofmdraws always fit whenn * m <= 2**63. When many streams or many draws per stream are needed, usePCG64, or the relatedPCG64DXSMorLCG128Mix. Their period of2**128allows about2.5 * 10**26streams of10**12draws.Streams
iandjare(j - i) * stepdraws apart, so they share the lowestvbits of their states, where2**vis the largest power of two that dividesj - i.jumped(iter)advances byitertimes a golden-ratio step, so it is also a good choice wheniteris not a large power of two.