Just a few days ago I had the need to implement a random function with a niche proprietary language, where you have no binary data type. Only strings, integers, and floats. Thats fun! I instead used a Lehmer generator with 32-bit arithmetics. I also wondered if there are any better solutions.
It is high time we let go of the Mersenne Twister (2019)
41–50 of 56 posts
Re: It is high time we let go of the Mersenne Twister (2019)
#42Earlier quoted context omitted.
> 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.
PractRand seems to have [1] last had a (pre-)release in 2019, and seems to have basic I/O problems that haven't been fixed [2]. There seem to be forks [3] and patches (mentioned in [2]) floating around, to fix such issues ad-hoc. But it seems unlikely that the rest of the code is free of bugs that need fixing too.
And yet, it seems to be the tool that comes up in any discussion of tests of PRNG, and seems to be a fixture of the field. It's always a bit sad (and kind of weird) when core tools that a community depends upon are taken for granted and not given the support and attention they need.
[1] https://sourceforge.net/projects/pracrand/files/ [2] https://www.johndcook.com/blog/2020/02/05/using-practrand-to... [3] https://github.com/MartyMacGyver/PractRand
Re: It is high time we let go of the Mersenne Twister (2019)
#43Earlier 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…
Thanks! It appears that Wikipedia has led me astray. The article in the top-level comment states, "if the generator is modified to return only the high 32 bits, then it passes BigCrush with zero failures."
Following through to the document Wikipedia cites, I'm unable to find the original source for that claim. I suppose I'll look again after I have my coffee.
Ah. Found it. From the PCG paper, "also of note, RanQ1[42] and XorShift* 64/32 are essentially the exact same generator, yet the former fails the test suite and the latter passes. The difference is that the former markets itself as a 64-bit generator and fails because its low-order bits are weak, whereas the latter only returns the top 32 bits." The claim of zero Big Crush failures also appears in Figure 2. http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
I suppose the next question is if the claim is wrong or I screwed up the implementation.
Re: It is high time we let go of the Mersenne Twister (2019)
#44Use 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 } } }
Unfortunately, any PCG code is not complete without a seeding procedure. That is, if you enter non-random seeds, you can get correlated streams, which is very bad for randomness.
Re: It is high time we let go of the Mersenne Twister (2019)
#45Use 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 } } }
Unfortunately, any PCG code is not complete without a seeding procedure. That is, if you enter non-random seeds, you can get correlated streams, which is very bad for randomness.
You need 128 random bits to seed the generator (i.e., two uint64 variables).
The bits1 and bits2 arguments to pcg32.New() should each be 64 bits of "noise".
They may be drawn from /dev/urandom or whatever. You can use crypto/rand.Read() from Go's standard library, for example. Just read 16 bytes using crypto/rand.Read() and use encoding/binary.LittleEndian.Uint64() to produce bits1 and bits2.
Or you can use a hash to produce bits1 and bits2. If you want to use a constant seed, take 32 hex digits from an arbitrary git commit id. Like this: bits1=0xd240853866f20fc3 bits2=0xe536cb3bca86c86c
It's an orthogonal issue.
Re: It is high time we let go of the Mersenne Twister (2019)
#46Earlier 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…
Can we get a reference on that lemire64 generator?
Re: It is high time we let go of the Mersenne Twister (2019)
#47Earlier 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…
Can we get a reference on that lemire64 generator?
It's Lemire's Lehmer Generator or LEMUR 64 for short
https://arxiv.org/pdf/1805.10941.pdf
https://archive.org/details/proceedings_of_a_second_symposiu...
Re: It is high time we let go of the Mersenne Twister (2019)
#48Earlier 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…
Thanks! It appears that Wikipedia has led me astray. The article in the top-level comment states, "if the generator is modified to return only the high 32 bits, then it passes BigCrush with zero failures." Following through to the document Wikipedia cites, I'm unable to find the original source for that claim. I suppose I'll look again after I have my coffee. Ah. Found it. From the PCG paper, "also of note, RanQ1[42]…
[deleted]
Re: It is high time we let go of the Mersenne Twister (2019)
#49Earlier 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…
Thanks! It appears that Wikipedia has led me astray. The article in the top-level comment states, "if the generator is modified to return only the high 32 bits, then it passes BigCrush with zero failures." Following through to the document Wikipedia cites, I'm unable to find the original source for that claim. I suppose I'll look again after I have my coffee. Ah. Found it. From the PCG paper, "also of note, RanQ1[42]…
It looks like https://de.wikipedia.org/wiki/Benutzer:Megatherium edited the German article to add Vigna's public domain multiplicative xorshift variants, and he misattributed xorshift64star to Marsaglia. https://github.com/jj1bdx/xorshiftplus/blob/5b345e2a2f32f1c5... Vigna obviously knows better than to multiply and not shift but that's not going to be obvious to an anonymous wikipedia editor since you really have to dig through the gpl framework code to find where he does that: https://github.com/jj1bdx/xorshiftplus/blob/1425aae20cd42324... The xorshift variant section should be deleted because if it's multiplying it's not a xorshift. The Lehmer generators show that multiplication alone with a 128-bit word size is enough to confound all the randomness tests experts wrote the last century on 32-bit computers. The value of something like xorshift is on a microcontroller that isn't good at multiplying.
Re: It is high time we let go of the Mersenne Twister (2019)
#50my latest PRNG's shootout is here https://rurban.github.io/dieharder/QUALITY.html
with quality and speed comparison of all known implementations.