Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: math/rand/v2: PCG Jump #63361

zephyrtronium opened this issue Oct 4, 2023 · 0 comments

proposal: math/rand/v2: PCG Jump #63361

zephyrtronium opened this issue Oct 4, 2023 · 0 comments


Copy link

Now that #61716 is accepted, I propose the following additional method on PCG:

// Jump advances the PCG state as if Uint64 were called 2^96 times. This
// can be used to produce up to 2^32 PRNG states which do not overlap for 2^96
// steps each.
func (p *PCG) Jump() {
	// We can model the state transition function as an affine F2^128 matrix:
	//  A = mul inc
	//        0   1
	// Then jumping by n steps is equivalent to using A^n instead of A to
	// compute the state transition. Since we use a fixed jump length of 2^96,
	// we can precompute:
	//  A^2^96 = 0x53cd8fbc000000000000000000000001 0x8bcf2d31000000000000000000000000
	//                                            0                                  1
	// Applying this to the state is straightforward, especially because we
	// do not need the low 64 bits of each operand.
	p.hi += 0x53cd8fbc00000000*p.lo + 0x8bcf2d3100000000

An example of using this would be:

func ExamplePCG_Jump() {
	states := make([]rand.PCG, 4)
	for i := 1; i < len(states); i++ {
		states[i] = states[i-1]

	for i := range states {
	// Output:
	// 4107282207882862730
	// 9529632109660410545
	// 17247399138676694270
	// 11354220120759235734

Jump is a useful operation for situations that call for many independent PRNG states. Seeding states at random is vulnerable to the birthday problem, especially because it is typical to produce long sequences from each state. (Vigna gives bounds on the probability of overlap.) Creating one arbitrarily seeded state and using successively jumped copies provides a strong guarantee that there will be no overlap for any feasible length of computation.

I propose Jump as an in-place operation for convenience when used with PCG states composed in other structures. Although it is possible to compute A^n (where x^y is exponentiation) efficiently for any n, we fix n=2^96 to avoid confusion about the meaning of or correct choices for a parameter. These choices intentionally contrast with the NumPy API for the PCG jump operation.

While it is possible (in fact, trivial) to define a jump operation on ChaCha8, its larger state size makes it substantially less vulnerable to random seeding overlaps. Additionally, I believe PCG's smaller size makes it an increasingly preferable choice as the number of PRNGs grows, which is exactly where jumping becomes appropriate. Therefore, I propose Jump only for PCG.

@gopherbot gopherbot added this to the Proposal milestone Oct 4, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Status: Incoming

No branches or pull requests

2 participants