5 ms·

As just a datapoint from some random person, I needed a pseudo-random number generator just last week. My use-case is semi-embedded, with two applications runn

by unwind 5y ago

As just a datapoint from some random person, I needed a pseudo-random number generator just last week. My use-case is semi-embedded, with two applications running on different hardware and operating systems, that both needed to generate streams of the same random data. I first naively went with just rand() to get it running, but obviously there's no guerantee that two completely different platforms' C libraries have the same PRNGs. So that didn't work. Like many (?), the Mersenne Twister is the first name that pops into my head if I think of "known" PRNG implementations, so I investigated it. I quickly came to the conclusion that it was kind of large in terms of amount of code and state for many applications, so I kept looking. Eventually I went with xorshift32 [1] and am very happy with that choice. The core of the implementation is ~10 lines of C, and my entire module (header+implementation, with mild commenting and a faux-main() test "driver") is sitting at 60 lines. It needs a whopping 32 bits of state, which I could manage to squeeze in just fine. :) [1]: https://en.wikipedia.org/wiki/Xorshift https://en.wikipedia.org/wiki/Xorshift

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 ago
  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~= 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 ago
    where do these two constants come from? knuth?
    - klaussilveira 5y ago
      I'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 ago
    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_generator https://en.wikipedia.org/wiki/Permuted_congruential_generato...
  - slavik81 5y ago
    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 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]
somat 5y ago
if it needs to be the same, or repeatable, you don't actually want a random function, you want a hash function. might as well call it such.
- JoachimS 5y ago
  No. The PRNG does not take an arbitrary large input and generates a digest/checksum. The PRNG accepts a single (short) input - a seed used to set the initial state. And can then generate a large number of values by updating the state. This is almost the opposite of a hash function. You could build the state update function using a hash function. But that does not make the PRNG a hash function.
  - charcircuit 5y ago
    >This is almost the opposite of a hash function. I would hesitate to say that. Look at hash functions built upon a sponge construction. One way to describe a sponge is that it absorbs a seed and then you can squeeze out random numbers. When building a hash function you absorb the input data and just squeeze out N bytes.
    - JoachimS 5y ago
      Yes, and no. The Sponge function in this context operates as a eXtended Output Function. It has an internal state and a state update function. But it does not in this context absorb a large input and output a digest. Sponges as a kernel/function that can be used to build hash functions, XOFs, PRNGs are interesting. That does not make the OP general statement that a PRNG should be called a hash function more correct. At least IMHO.
      - charcircuit 5y ago
        I am only pointing out the similarities between hash functions and PRNGs. I was not trying to disagree with your main point that a PRNG is a hash function. Though perhaps you could call them opposites in that usually you have a fixed input and infinite output for a PRNG and an infinite input and a fixed output for hash functions.
eternityforest 5y ago
Xorshift is one of my favorites. I always worry about default random numbers in the standard library, because there might still be that awful and badly performing(On embedded without multiply) LCG hiding.
daneel_w 5y ago
https://github.com/stolendata/ranrot_bi https://github.com/stolendata/ranrot_bi

by unwind 5y ago

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 ago
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~= 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 ago
  where do these two constants come from? knuth?
  - klaussilveira 5y ago
    I'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 ago
  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_generator https://en.wikipedia.org/wiki/Permuted_congruential_generato...
- slavik81 5y ago
  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 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]

somat 5y ago

if it needs to be the same, or repeatable, you don't actually want a random function, you want a hash function. might as well call it such.

JoachimS 5y ago
No. The PRNG does not take an arbitrary large input and generates a digest/checksum. The PRNG accepts a single (short) input - a seed used to set the initial state. And can then generate a large number of values by updating the state. This is almost the opposite of a hash function. You could build the state update function using a hash function. But that does not make the PRNG a hash function.
- charcircuit 5y ago
  >This is almost the opposite of a hash function. I would hesitate to say that. Look at hash functions built upon a sponge construction. One way to describe a sponge is that it absorbs a seed and then you can squeeze out random numbers. When building a hash function you absorb the input data and just squeeze out N bytes.
  - JoachimS 5y ago
    Yes, and no. The Sponge function in this context operates as a eXtended Output Function. It has an internal state and a state update function. But it does not in this context absorb a large input and output a digest. Sponges as a kernel/function that can be used to build hash functions, XOFs, PRNGs are interesting. That does not make the OP general statement that a PRNG should be called a hash function more correct. At least IMHO.
    - charcircuit 5y ago
      I am only pointing out the similarities between hash functions and PRNGs. I was not trying to disagree with your main point that a PRNG is a hash function. Though perhaps you could call them opposites in that usually you have a fixed input and infinite output for a PRNG and an infinite input and a fixed output for hash functions.

eternityforest 5y ago

Xorshift is one of my favorites. I always worry about default random numbers in the standard library, because there might still be that awful and badly performing(On embedded without multiply) LCG hiding.

daneel_w 5y ago

https://github.com/stolendata/ranrot_bi https://github.com/stolendata/ranrot_bi