News for hackers. Stuff that matters.
Re:History of Uniform Random Number Generation (2017) [pdf] by camel-cdr on Sunday March 17, 2024 @07:05PM (#39738872)
I like how the earliest and easiest PRNGs are making a comeback:

First middle square method, just add a weyl sequence to it, and all statistical tests stop failing [0]

    uint64_t x, weyl;
    uint32_t msws(void) {
        x = x * x + (weyl += 0xB5AD4ECEDA1CE2A9);
        return x = (x >> 32) | (x << 32);
    }
And now Collatz, just add a weyl sequence to it, and all statistical tests stop failing [1]

    __uint128_t x;
    uint64_t a, weyl;
    __uint128_t CWG128_64(void) {
        x = (x | 1) * ((a += x) >> 1) ^ (weyl += 0xB5AD4ECEDA1CE2A9);
        return a >> 48 ^ x;
    }
The fun part is that the constant used in the weyl sequence is pretty much arbitrary, it just needs to be odd and not too regular.

The more state of the art xoshiro, pcg, Romu, sfc64, tylo64, ... are still faster and probably safer tp use, but I like how especially the middle square weyl sequence PRNG can be very easily memorized: Square + weyl sequence, swap upper and lower bits, and return the truncated result. The weyl sequemce constant can be created with a rule of thumb: try choosing mostly destinct hex digits and make it odd.

[0] https://arxiv.org/abs/1704.00358

[1] https://arxiv.org/abs/2312.17043

Re:History of Uniform Random Number Generation (2017) [pdf] by eutectic on Monday March 18, 2024 @12:02AM (#39740417)
What if you don't truncate? I fell like it might still be OK.
Re:History of Uniform Random Number Generation (2017) [pdf] by eutectic on Monday March 18, 2024 @11:04AM (#39745561)
Here's a variant which gives 64-bit output:

  uint64_t x = 0, w = 1;
  uint64_t msws64(void) {
      x = x * x + (w *= 0xe9acc0f334e93bd5ULL);
      return (x = (x >> 32) | (x << 32)) ^ w;
  }
Re:History of Uniform Random Number Generation (2017) [pdf] by camel-cdr on Tuesday March 19, 2024 @03:16AM (#39753581)
I wouldn't recemmend that without a 128 bit variables. The truncation is required to make the generator non predictable, otherwise you leak to much state.

Alternatively, you can just call the 32 bit one twice and build a 64 bit value from the results.

Edit: I didn't see that you changed the algorithm more than removing the truncation. It is honestly suprizingly good for exposing that much state, but it fails PractRand after 16 GB.

It is honestly suprizingly good and hasn't failed PractRand yet (I'm at >64 GB).

Re:History of Uniform Random Number Generation (2017) [pdf] by eutectic on Friday March 22, 2024 @01:05PM (#39792704)
Your edit is confusing me. Which variant fails and which variant passes?
Re:History of Uniform Random Number Generation (2017) [pdf] by camel-cdr on Saturday March 23, 2024 @06:08AM (#39798733)
Your msws64 did not seem to fail
Re:History of Uniform Random Number Generation (2017) [pdf] by pixelpoet on Monday March 18, 2024 @08:49PM (#39751846)
You also have to love that the middle square method is by von Neumann[0], infinitely quotable about random numbers ("Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin"), way back in 1949. As a small child he saw his mother daydreaming, and asked her what she was computing...

[0] https://en.wikipedia.org/wiki/Middle-square_method