5 ms·
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 cour
by slavik81 5y ago
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/a906355343dc0d320858a7b00504040d04c053f7/misc/rng.c https://github.com/cgmb/euler/blob/a906355343dc0d320858a7b00...
- jart 5y agoIt'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~= 5e-2043 FAIL !!!!!!!! BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! BRank(12):1K(2) R=+29077 p~= 4e-8754 FAIL !!!!!!!! BRank(12):1536(1) R=+31582 p~= 2e-9508 FAIL !!!!!!!! BRank(12):2K(1) R=+42604 p~= 0 FAIL !!!!!!!! [Low8/32]BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! [Low8/32]BRank(12):256(4) R= +8055 p~= 4e-4285 FAIL !!!!!!!! [Low8/32]BRank(12):384(1) R= +6783 p~= 5e-2043 FAIL !!!!!!!! [Low8/32]BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! [Low8/32]BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! [Low8/32]BRank(12):1K(2) R=+29077 p~= 4e-8754 FAIL !!!!!!!! [Low8/32]BRank(12):1536(1) R=+31582 p~= 2e-9508 FAIL !!!!!!!! [Low1/32]BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! [Low1/32]BRank(12):256(2) R= +5696 p~= 1e-1715 FAIL !!!!!!!! [Low1/32]BRank(12):384(1) R= +6783 p~= 5e-2043 FAIL !!!!!!!! [Low1/32]BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! [Low1/32]BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! ...and 160 test result(s) without anomalies Consider using this instead if you want a simple PRNG: uint64_t lemire64(void) { static uint128_t s = (uint128_t)426679527491843471 << 64 | 2131259787901769494; return (s *= 15750249268501108917ull) >> 64; }
- enriquto 5y agowhere do these two constants come from? knuth?
- klaussilveira 5y agoI'm assuming from here: https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/ https://lemire.me/blog/2019/06/06/nearly-divisionless-random...
- phkahler 5y agoAnd 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_generator https://en.wikipedia.org/wiki/Permuted_congruential_generato...
- slavik81 5y agoThanks! 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 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.
- deleted 5y ago[deleted]