@MichaelTJones perhaps you might be interested in this issue, as you already have an implementation of Melissa O'Neill's PCG generator at https://github.com/MichaelTJones/pcg.

I would very much support this change. In fact my careful PCG implementation is because of the weaknesses mentioned here. I long ago switched to this code and will not use the present library PRNG. In addition to being technically excellent, a new generator can be created in 2.72ns, makes new 64-bit values in 5.56ns, and has small state. Examine the tests in my implementation for details.

why not bring it to Go 1

@dongweigogo please read the proposal text carefully, it is explained.

To put it another way, with a separate Source for each goroutine, no locking would be required, but the current implementation is impractically large for such an approach.

For some random generators, generating a bunch of new streams is worse statistically for once stream. Section 4.3.2 of the paper suggests that this is not a problem with PCG if the seeding is done properly. Just wanted to comment for anyone curious.

@MichaelTJones Notice how the bounded functions are significantly slower, that's because of the divisions. You can follow the new implementation at go/src/math/rand/rand.go and avoid divisions (with high probability) and get something faster...

MichaelTJones/pcg#2

Once Go gets something like a full 64-bit multiplication (outputting both the high and low 64-bit values), then we will be able to similarly speed up Bounded64.

@robpike The implementation of the bounded RNGs at https://github.com/golang/exp/blob/master/rand/rand.go implies one or two 64-bit division per call, assuming no magical tricks from the compiler. It costs dozens of cycles. The divisions probably cost more than the generation of the random number itself! The 64-bit division is a monster on x64 processors. Even the 32-bit division is surprisingly expensive. It is not very different on ARM processors.

A better alternative is to do a multiply followed by a shift...
https://github.com/golang/go/blob/master/src/math/rand/rand.go#L138-L160

There are at least three parts of math/rand: the source, the conversion/distribution routines, and the concurrency strategy. I think that it is worth revisiting all three for Go 2 and that all three should be considered together.

This proposal as written addresses the source.

The conversion routines changes include #16213 and a handful of other math/rand decisions that were made to preserve existing output, e.g. #8013, #6721, #12290, #16124, #8731, and probably others.

For the concurrency strategy, see #20387 and #21393.

If get per-P storage in Go 2, or if we are willing to let math/rand have privileged runtime access, I think we should consider adding a global Source that:

• stores state in a P
• is lock-free
• is explicitly documented not to have Any reproducibility
• is seeded at startup or on first use
• panics if Seed is called

This would allow people not to have to manually thread PRNG state around through goroutines, which seems to be a significant complaint.

Maybe it should even be the default Source, and have people opt in to reproducibility by making their own Source.

cc @cespare for that last comment

I have stumbled in the code for PCGSource (we decided to teach Go as first language to undergrads at my university), and in case you are considering it for inclusion in the standard library, I think it would IMHO a good idea to add to the code some documentation about the perils of seeding the generator with states that share a large number of lower bits. For example:

package main
import . "fmt"
import . "github.com/golang/exp/rand"

func main() {
   var pcg0, pcg1 PCGSource

   pcg0.UnmarshalBinary([]byte { 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 });
   pcg1.UnmarshalBinary([]byte { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 });

   for i := 0; i < 1000000000; i++ {
      pcg0.Uint64()
      pcg1.Uint64()
   }

   for i := 0; i < 10; i++ { Printf("0x%x\t0x%x\n", pcg0.Uint64(), pcg1.Uint64()) }
}

This program creates two PCGSource instances whose initial states differ only in the upper bit by unmarshaling; then, it advances the generators a billion times, and then prints ten outputs:

0xd8e3ee0662fca74c	0x62fca74cd8e2ee06
0x2e769d76dc6e4f1c	0xdc4e4f1c2e769d76
0x73a027a3ae1b700f	0xae1b700f53a027a3
0x746dd81a74fe2b99	0x74de2b99746dd81a
0xc0fb5795c97c77e7	0xc97c77e7e0fb5795
0xd2a86c8b49b7c14d	0x49b7c14d52a86c8b
0xce996d79a596d046	0xa596d446ce996d79
0xa5df4766d500990b	0xd500994ba5df4766
0x12681951f83f039c	0xf83f039c52681951
0x4616238466319291	0x663192914616238c

It is visible even to the naked eye that the outputs are the same, modulo a 16-bit rotation and single-bit change, whereas we would expect to obtain, maybe after a few iterations, different and uncorrelated streams.

The problem lies in the basic flaw of LCGs with power-of-2 modulus: if you create two LCGs with the same multiplier and additive constant, and start them from states with the same k lower bits, this will be true forever—the next-state operations all propagate bit changes to the left, never to the right. So the two generators above, even starting from different states, will have forever the same 127 lower bits.

This is an extreme example—127 lower bits in common. But you can still experience a strong correlation between streams generate by different seeds with less low bits in common, even if you cannot see the correlation as easily. For example, the following program uses the standard seeding interface to create two different generators, and then write their output to standard output in binary:

package main
import . "os"
import eb "encoding/binary"
import . "github.com/golang/exp/rand"

func main() {
   var pcg0, pcg1 PCGSource

   pcg0.Seed(0);
   pcg1.Seed(uint64(1) << 63);

   for i := 0; i < 1000000000; i++ {
      pcg0.Uint64()
      pcg1.Uint64()
   }

   b := make([]byte, 8)
   for {
      eb.LittleEndian.PutUint64(b, pcg0.Uint64())
      Stdout.Write(b)
      eb.LittleEndian.PutUint64(b, pcg1.Uint64())
      Stdout.Write(b)
   }
}

Since we are using two different seeds, we expect the two associated streams, which are non-overlapping, to be uncorrelated. In particular, if we interleave the streams the resulting stream should still look random. But if we pipe the output of the program in PractRand, we obtain after few seconds of testing

rng=RNG_stdin, seed=unknown
length= 32 megabytes (2^25 bytes), time= 9.2 seconds

  Test Name                         Raw       Processed     Evaluation
  BCFN(0+1,13-3,T)                  R= +17.9  p =  3.0e-8   very suspicious
  BCFN(0+2,13-4,T)                  R= +30.8  p =  2.0e-13    FAIL
  ...and 935 test result(s) without anomalies

All classical PRNGs (MCGs with prime modulus, F₂-linear, (C)MWC, etc.) mix wholly their state even after the smallest state change (e.g., one bit). Some are very slow (e.g., the Mersenne Twister with 19937 bits takes a few million iterations), but sooner or later the state change will propagate to all bits. At that point, they will pass the interleaving test above. All PRNGs based on cryptographic primitives will, too, as the smallest change in state generates a random perturbation of the output.

This is not true for PCG because of the very weak base LCG.

For the same reason, I suggest that in case the "jump" functionality of PCG is made available in the future, the documentation should state clearly that jumping by a large power of 2 is very dangerous, as it will yield a new state with a large number of lower bits in common with the starting state, leading to the consequences above.

Shouldn't there be a discussion regarding the other potential alternative Source implementations? And regarding the requirements that such a replacement will have to fulfill?

Currently math/rand is explicitly meant for applications that are not "security sensitive", but wouldn't it be in the spirit of Go to provide safe defaults? Standard library users will not always know or figure out in time that their application requires resistance to attacks on the PRNG. I think that this applies in the case of an algorithm that uses randomization being exposed on the public Internet, for example.

Randen is an alternative to PCG that seems to pass the relevant statistical tests (as PCG likewise does), but should also provide resistance against prediction of future inputs and empirical indistinguishability from randomness while the generator state is not compromised, and also it ensures that past outputs can't be reconstructed even after the state is compromised.

The Randen paper also shows that, given hardware acceleration of AES, Randen can be faster than PCG in real world applications like shuffling and sampling.

The Randen paper on Arxiv (it includes a kind of overview of other available "modern" PRNGs): https://arxiv.org/abs/1810.02227

The Randen Git repository: https://github.com/google/randen

However, considering Randen raises the question of whether the alternate Go PRNG should, given the same seed, generate the same pseudorandom bits across all supported computer architectures; because presumably one wouldn't want to use Randen on, e.g., the old ARMs or Pentiums (because of the lack of AES acceleration instructions). I guess PCG is good enough to be a default for the low-powered machines?

There seems to be much discussion on the PCG family on the Numpy Github, a lot of which is probably relevant to this issue:
numpy/numpy#13635
numpy/numpy#16313

It's a bit much to consume, but I noticed at least these important facts:

1. The author of PCG published a new member of the family on her Github in 2019. There was no blog post and I think the only announcement was on one of the linked Numpy Github issues, but the DXSM variants are supposed to be faster and have even better statistical qualities according to the relevant empirical tests, as well as being immune to some of the peculiarities of the earlier PCG schemes. Here's the commit: imneme/pcg-cpp@871d049

2. Prof Vigna (appears a couple posts above here), a rival non-crypto PRNG designer (a small but "lively" field, it seems), proposes some supposed improvements applicable to PCG, even though he doesn't recommend using generators like PCG.

Another thing that may be of import is how nontrivial or "challenging" predictability is explicitly a design goal for the PCG family. AFAIK, "challenging" just means (in the context of PCG) that there are/were no publicly known efficient attacks, but without a stronger kind of guarantee, such as applicable to a CSPRNG or to Randen, making the claim imprecise in such a way that it is somewhat deceptive, coming from an expert. This "challenging" stuff seems to come at the cost of trade-offs at the expense of speed or statistical quality, even though it is of dubious utility (considering that no real guarantee is given, and that a relatively efficient attack has recently been demonstrated).

Sebastiano Vigna wrote a pretty scathing review of some of the claims made in O'Neill's paper:
http://pcg.di.unimi.it/pcg.php
Edit: apologies for stirring up something that's seemingly already been discussed to death here!

Dr. Vigna's criticisms are mostly about (extraordinarily) highly correlated sequences given nearby initial states. This is a very important concern for people performing intensive mathematical, scientific, or statistical work. However, based on discussion here and in #26263, that does not seem to be the Go team's target audience for math/rand. In particular, such people are more likely to understand the reasons for choosing or avoiding a particular class of PRNG.

Instead, the goals for a new math/rand generator seem to be speed, reasonable distribution quality, and a state size small enough that many goroutines can use independent generators. PCG fits these traits[n1][n2], as do many other generators, including several mentioned here.

Now, since this proposal is for PCG, suggesting other generators here does not make progress. Instead, we should be looking at how people currently use math/rand – keeping in mind that it is already a weak generator – to verify that the problems proven with PCG are, in a sense, beside the point. Another idea is to look at how many projects implement or import specific PRNG algorithms such as PCG, xoshiro, Mersenne Twister, &c., or collections like gonum/mathext/prng that provide several PRNGs, to see the reasons people choose those algorithms over math/rand.

[n1] The issue with speed on 32-bit platforms mentioned in #21835 (comment) does seem like an important concern, especially as Wasm becomes more prominent.

[n2] Notably, the idea mentioned in the proposal to seed different PCGs with the generators' respective addresses, or having many goroutines each seed with the current nanosecond time, may exacerbate its problems with highly correlated states. On the other hand, a high-quality seeding algorithm might avoid that.

@zephyrtronium I was under the impression that wasm did have 64-bit integer support universally today? Is this not the case? Or do you mean to refer to something else with the remark "especially as Wasm becomes more prominent". Or is there a particular issue with how Go generate wasm outputs?

cc @jfbastien

Sebastiano Vigna wrote a pretty scathing review of some of the claims made in O'Neill's paper:
http://pcg.di.unimi.it/pcg.php

It's worth noting that I responded to his critiques here.

@zephyrtronium I was under the impression that wasm did have 64-bit integer support universally today? Is this not the case? Or do you mean to refer to something else with the remark "especially as Wasm becomes more prominent". Or is there a particular issue with how Go generate wasm outputs?

So it does, my mistake. I must have misread something about Wasm at some point.

Also, as observed by some of the commentators here, more recently Vigna has raised concerns about self-similarity in PCG. If we interleave outputs from carefully chosen seedings of PCG, although the outputs are superficially different, the closer scrutiny applied by sensitive PRNG tests will reveal correlations of some kind indicating that the generator exhibits self-similarity between distant parts of its output.

I think this kind of self-similarity is interesting (and well known for the LCGs that underlie PCG), but Vigna's apparent grave concern about this issue was rather undercut when, on the NumPy mailing list, Tyge Løvset pointed out that similar issues affected Vigna's own most-recent PRNG, xoshift** (comment, code).

If users follow good practice for seeding PRNGs (which they should for a wide variety of other reasons), these kinds of issues won't arise (or rather, they are vanishingly unlikely). An alternative is to scramble the output more aggressively, but the trade-off is execution time. PCG's newest output permutation, DXSM, does represent an attempt to scramble better at no added cost on many platforms, but it is still making a trade off in this space.

I wasn't sure of the impact of the claims made, but the general tone was harsh enough it made it more difficult to take his critiques seriously, although I felt there was some interesting points mentioned. I'm happy you took the time to address them, and thank you for providing that information here. His post was certainly at best unintentionally misleading.

@zephyrtronium I was under the impression that wasm did have 64-bit integer support universally today? Is this not the case? Or do you mean to refer to something else with the remark "especially as Wasm becomes more prominent". Or is there a particular issue with how Go generate wasm outputs?

@lemire sorry for missing this, I don't look at github notifications often.

Yes, wasm supports 64-bit integers universally as a first-class type. The initial discussion in 2016 hedged a bit in case there were JS-based implementations in some browsers, but now all relevant browsers support wasm natively (that's 92% of all users on the web). Non-browser implementations of wasm also support 64-bit integers natively.

Maybe the confusion is around "32-bit platforms"? wasm is currently ILP32, thought there's a proposal for wasm64 with 64-bit address spaces. Limiting the address space to 32 bits doesn't limit the use of 64-bit integers.

There is no mention of a multiply-with-carry generator in these discussions. Unlike many of these other algorithms, it is listed on wikipedia and is simply a LCG with less constants.

If the multiply-with-carry generator had a lag of at least 2 (according to the parlance used), it would be parallelizable by typical cpu dispatch units as there would be less dependencies.

Hopefully whatever the generator used, it will allow for 64-bit seeds or at least frequent reseeding.

Randen is an alternative to PCG that seems to pass the relevant statistical tests (as PCG likewise does), but should also provide resistance against prediction of future inputs and empirical indistinguishability from randomness while the generator state is not compromised, and also it ensures that past outputs can't be reconstructed even after the state is compromised.

This AES-NI accelerated RNG is faster and has performance nearly that of a CPU's memory transfer limit: dragontamer/aesrand

Adding an extra AES round might make it cryptographic.

Hi everyone! I'm a numpy developer with a particular focus on our PRNG capabilities. For some background, the older PCG64 with the XSL-RR output function is our current default PRNG for the past couple of years. The next release will have an optional implementation with the stronger DXSM output function. We expect we will make it the default some undetermined time down the road.

I have written up a what I hope to be an accessible explanation of the consequences so you don't have to reconstruct everything from those long digressing threads. My prose style is prone to long, complicated sentences, so please ask if anything needs to be clarified; that will help me edit this down for my own audience. I hope to provide a point of view as a PRNG library maintainer that is helpfully complementary to those of our PRNG algorithm authors. To be clear about where I'm writing from, numpy is an anchor library for scientific computing and machine learning, so we have a particular risk profile that is driving our decisions. The extreme conditions that would make this weakness non-negligibly likely are not really a practical use case right now, but you can see it on the horizon, at least for my audience. This is likely a different risk profile for you, but I try to give the information needed to evaluate things for yourself rather than boil everything down to a universal safe/unsafe declaration.

If I were still asked my opinion for what you should do, if you do decide to use a PCG algorithm, I would recommend using the DXSM variant over the XSL-RR. While the risks of XSL-RR are rare outside of extreme use cases and usually inconsequential, I think they are still worth documenting. And it's a pain to document and a pain for the user to work through the math to determine that yes, they are safe using it. DXSM provides an extra safety margin that renders those computations (and my article) unnecessary. I can think about the DXSM variant with a mental model that is a lot less complicated than one I would now use for XSL-RR. As a library maintainer and documenter, that's golden.

@rkern

My prose style is prone to long, complicated sentences,...

You sir have no idea what long and complicated sentences are... :-)

Thanks for the write up! Nicely done.

(It might be too tangential to include, but the only thing I'd add is that detectable self-similarity is not unique to LCGs (and PCG); it's findable in a number of non-cryptographic PRNGs.)

See #60751 for a GitHub Discussion that I hope will lead to a math/rand/v2. Closing as duplicate of that.