You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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
}
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.
The text was updated successfully, but these errors were encountered:
Now that #61716 is accepted, I propose the following additional method on PCG:
An example of using this would be:
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.
The text was updated successfully, but these errors were encountered: