History of Uniform Random Number Generation (2017) [pdf]

https://www.informs-sim.org/wsc17papers/includes/files/016.pdf

by pncnmnp • 2 years ago

58 11 2 years ago

pixelpoet2• 2 years ago

For enjoyers of French-Canadian random number generation papers/books, there's also this excellent book on non-uniform random variate generation by Luc Devroye: http://luc.devroye.org/rnbookindex.html

marcle• 2 years ago

The article references the SSJ Java package which is developed by the author and his colleagues. This provides implementations for many RNGs -- and some nice tools for simulations: https://github.com/umontreal-simul/ssj

camel-cdr3• 2 years ago

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

eutectic3• 2 years ago

What if you don't truncate? I fell like it might still be OK.

eutectic3• 2 years ago

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;
  }

camel-cdr3• 2 years ago

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).

pixelpoet2• 2 years ago

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

nyrikki• 2 years ago

Implementing the Blum Blum Shub algorithm was my first real programming task for a gaming website in 95.

Way too slow on Alphas at the time for primary use but OK for seed at the time.

I still remember SGI publishing LavaRand, using lava lamps and cc'd cameras as an entropy source around the same time.

chunkyks• 2 years ago

I developed an unhealthy obsession with the RAND book in 2020,which culminated in an article on the front page of the wsj. https://www.wsj.com/articles/rand-million-random-digits-numb...

RAND used to cut copies of the punch card deck for anyone who asked, but I'm sadly unable to find anyone who's still got a copy.

History of Uniform Random Number Generation (2017) [pdf]

Related Stories