← Back to context

Comment by Straw

2 months ago

I'd be very interested to see a state-size capacity analysis in the style of PCG- if you make cut down versions of your generator with reduced state size, say by reducing the word size of all three words of state, how low can you go while still passing PractRand/BigCrush? This gives a much better idea of how "close" to danger you are than simply passing.

Basically any generator with a 192 bit state can pass BigCrush/PranctRand- even known terrible ones like middle square!

https://www.pcg-random.org/posts/too-big-to-fail.html

5 comments

Straw

Reply
the_othernet  2 months ago

I'll have to re-optimize the rotations for the smaller state size, but I will do it and report here.

  • Straw  2 months ago

    I'm looking forward to seeing your results!

    Here are corresponding results for LCGs, interestingly there's a clear affine relationship between state size and log(bytes to practrand failure).

    https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...

    • Veedrac  2 months ago

      Fun fact, you can extend this logic to measure the upper limit for how discriminating your RNG's test is, by shuffling a 2^n long vector with a CSRPNG and testing that until failure the same way. When I tried this ~8y ago, I believe these tested about 2 bits better on PractRand than PCG for 32 bit outputs. Sadly it's not really plausible to run this algorithm for 64 bit outputs.

      The main thing this knowledge is worth when designing RNGs is that it tells you how reasonable it is to 'lose' N bits. Eg. if you're 2 bits worse than PCG, you're about twice as much worse than ideal.

    • the_othernet  2 months ago

      Using only 32bit fast_loop and mix (for 64bits of state) passes PractRand up to 256GB with only one unusual. That's about a 90 bit state LCG equivalent?

      I did have to alter the output to be "(GR * mix) + fast_loop" and change the rotation constants to be 12 and 5.