from Hacker News

A Primer on Randomness

by ThisIsMyAltAcct on 3/8/24, 12:52 AM with 1 comments

• by camel-cdr on 3/8/24, 12:32 PM

  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