For games, Squirrel Noise 3 is great.
It is high time we let go of the Mersenne Twister (2019)
31–40 of 56 posts
Re: It is high time we let go of the Mersenne Twister (2019)
#32The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise. So, f…
> I found some discussion here[2] where it's suggested it has some fatal flaws as well
The described flaws are not really flaws. The author of the blog post has a strange perspective on what a PRNG should be.
> obvious patterns in what should have been random noise.
> So, for simulations where predictability etc is not a concern, what's the state of the art?
Can't you just try different ones? E.g., try xoshiro256++, xoshiro256** and some CSPRNG, and compare for visible patterns.
The reality is that AFAIK the state of the art doesn't exist, there seems to be little scientific interest for non-secure fast pseudo-random generators with good statistical properties.
Usually one checks for bad statistical properties with ad-hoc tools like Practrand, basically test suites. But Practrand is buggy and unmaintained and there's no better option AFAIK.
In summary, test the PRNG on a per-application basis yourself, or just use xoshiro256++. Just my impressions.
Re: It is high time we let go of the Mersenne Twister (2019)
#33The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise. So, f…
> The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. PRNGs are complicated, and sometimes we don’t find out flaws in them until long after they are widely deployed – although test suites like U01 Big Crush and PractRand should really help that situation out. Part of…
> test suites like U01 Big Crush and PractRand should really help that situation out
Reminder: the test suites are buggy and unmantained.
Re: It is high time we let go of the Mersenne Twister (2019)
#34Earlier quoted context omitted.
Sebastiano Vigna seems to have a beef. For all I've seen M.E. O'Neill has handled the situation really well. Taking Vignas claims and critique seriously. https://www.pcg-random.org/posts/on-vignas-pcg-critique.html
Here's Vigna's random function if anyone's curious. uint64_t vigna_r(uint64_t state[static 1]) { uint64_t z = (state[0] += 0x9e3779b97f4a7c15); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; z = (z ^ (z >> 27)) * 0x94d049bb133111eb; return z ^ (z >> 31); } It passes bigcrush and practrand plus -ftree-vectorize makes it faster than xorshift.
[deleted]
Re: It is high time we let go of the Mersenne Twister (2019)
#35Earlier quoted context omitted.
I came to a similar conclusion when I was looking for a simple RNG. I chose the top 32 bits of xorshift64* [1], as it was noted that it passes BigCrush. Of course, that probably comes at a performance cost. [1]: https://github.com/cgmb/euler/blob/a906355343dc0d320858a7b00...
It's unlikely xorshift64 top bits pass bigcrush. RNG_test using PractRand version 0.95 RNG = RNG_stdin32, seed = unknown test set = core, folding = standard (32 bit) rng=RNG_stdin32, seed=unknown length= 512 megabytes (2^29 bytes), time= 3.1 seconds Test Name Raw Processed Evaluation BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! BRank(12):256(4) R= +8055 p~= 4e-4285 FAIL !!!!!!!! BRank(12):384(1) R= +6783 p~= 5…
where do these two constants come from? knuth?
Re: It is high time we let go of the Mersenne Twister (2019)
#36Use PCG: https://www.pcg-random.org/
Here is a stand-alone implementation of PCG32 in Go:
package pcg32
type Src [2]uint64
func New(bits1, bits2 uint64) *Src {
return &Src{bits1, bits2 | 1}
}
func (s *Src) Uint32() uint32 {
var (
x = s[0]
y = uint32(x >> 59)
z = uint32((x>>18 ^ x) >> 27)
)
s[0] = s[1] + x*6364136223846793005
return z>>y | z= min {
return r % n
}
}
}Re: It is high time we let go of the Mersenne Twister (2019)
#37Earlier quoted context omitted.
It's unlikely xorshift64 top bits pass bigcrush. RNG_test using PractRand version 0.95 RNG = RNG_stdin32, seed = unknown test set = core, folding = standard (32 bit) rng=RNG_stdin32, seed=unknown length= 512 megabytes (2^29 bytes), time= 3.1 seconds Test Name Raw Processed Evaluation BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! BRank(12):256(4) R= +8055 p~= 4e-4285 FAIL !!!!!!!! BRank(12):384(1) R= +6783 p~= 5…
where do these two constants come from? knuth?
I'm assuming from here: https://lemire.me/blog/2019/06/06/nearly-divisionless-random...
Re: It is high time we let go of the Mersenne Twister (2019)
#38Earlier quoted context omitted.
I came to a similar conclusion when I was looking for a simple RNG. I chose the top 32 bits of xorshift64* [1], as it was noted that it passes BigCrush. Of course, that probably comes at a performance cost. [1]: https://github.com/cgmb/euler/blob/a906355343dc0d320858a7b00...
It's unlikely xorshift64 top bits pass bigcrush. RNG_test using PractRand version 0.95 RNG = RNG_stdin32, seed = unknown test set = core, folding = standard (32 bit) rng=RNG_stdin32, seed=unknown length= 512 megabytes (2^29 bytes), time= 3.1 seconds Test Name Raw Processed Evaluation BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! BRank(12):256(4) R= +8055 p~= 4e-4285 FAIL !!!!!!!! BRank(12):384(1) R= +6783 p~= 5…
And if that's not random enough you should be able to fix it by applying a non-multiplicative function (shifts and booleans for example) to the output values. Feeding one random sequence into a different form of pseudo-random mapping has been shown to be highly effective even when the two functions themselves fail test of randomness.
Edit: This is the concept I was thinking of: https://en.wikipedia.org/wiki/Permuted_congruential_generato...
Re: It is high time we let go of the Mersenne Twister (2019)
#39The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise. So, f…
I would take that with a pinch of salt. The PCG and Xoshiro guys seem to have some kind of feud so some of the criticisms might not be as big a problem as they are made out to be in practice. Here's a partial rebuttal: https://www.reddit.com/r/programming/comments/8gx2d3/new_lin... For a bit of "social proof" xoshiro256++ is the default PRNG is Julia.
My practical takeaway from these discussions is that for most people, in most situations, any of these modern choices are good enough for purpose - the differences (in whichever direction they lay) come in only when you're pushing the PRNG to its extremes, while operating with a specific set of constraints.
Re: It is high time we let go of the Mersenne Twister (2019)
#40Use PCG: https://www.pcg-random.org/ Here is a stand-alone implementation of PCG32 in Go: package pcg32 type Src [2]uint64 func New(bits1, bits2 uint64) *Src { return &Src{bits1, bits2 | 1} } func (s *Src) Uint32() uint32 { var ( x = s[0] y = uint32(x >> 59) z = uint32((x>>18 ^ x) >> 27) ) s[0] = s[1] + x*6364136223846793005 return z>>y | z = min { return r % n } } }
Multipliers for other widths: https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...