flyingmutant / rand Goto Github PK

Implementation in math/rand (and golang.org/x/exp/rand) suffers from a correlation: see golang/go#8731 and An improved ziggurat method to generate normal random samples for analysis. Also, they can probably be made faster.

#2 is about a general purpose Sample, but a relatively common case is func Pick2(n int) (i int, j int). Is it worth adding as a separate function, given that it will only be marginally better than a straightforward loop-based implementation?

Hi there!

Do you have some benchmarks regarding https://github.com/valyala/fastrand ?

In "global_go119.go", maphash.Bytes(maphash.MakeSeed(), nil) can not generate zero, because rthash(nil, 0, state) returns state directly and state must not be 0.

Sample was added in ce7c277, however there are several problematic things:

• as of go1.18, compiler can't allocate the result on the stack, even when Sample was inline and the k is constant (!); see:
  • golang/go#20533
  • golang/go#27625
  • however, changing the signature introduces inconsistency with Perm
• the map is not reused between different calls
  • however, placing it into Rand increases its size, and introduces a pointer in a previously pointer-free struct
• Floyd's sampling algorithm does not guarantee random order, so people are required to read the docs and don't forget to Shuffle if required
• potential PartialShuffle is much faster and guarantees random order (although it requires mutable slice of size n)
• having all 4 of Perm, Sample, PartialShuffle and Shuffle is maybe too much

On the other hand, Sample runs in O(k) for both time and memory. Also, algorithm is simple but non-obvious (a bit like Shuffle), as is the linear-search-instead-of-map optimization.

Also, with #1, Sample may be not required at all.

See permute() for an explanation of the design. Main problem is that I am not aware of simple, fast, high-quality (passing 2^42+ of PractRand) permutations of n bits, for all n in 1..64.

NASAM does the trick for 64 bits, but what about other cases?