MurmurHash/SMHasher author here. While I don't doubt this passes BigCrush etc, I do find it very surprising that it does.
The state update function is effectively "a = rotate(a, constant) + b; b = rotate(b, constant) + constant;" and the output derivation is "output = (a + b) * constant".
That update function is _barely_ nonlinear, and the output derivation is linear. The output would probably be slightly better as "(a ^ b) * constant".
The slow_loop thing to guarantee 2^128 period is probably not needed - anyone with an application that cares about a period that high is probably going to choose a more robust generator (a few rounds of hardware-accelerated AES in counter mode is your best bet there)
The use of the Z3 prover is neat and I should read up on that more.
When iterating I first tried to make fast_loop as random as possible by trying all possible rotational values and then having each option tested in PractRand 1000 times from 256M to 8GB. There was a wide range of performance by rotation. 47 was the best (for the GR constant) and resulted in the most tests being passed. The goal was a stronger than normal core for the PRNG that could feed actively into mix.
I found the multiplication to be necessary for passing PractRand and BigCrush with the state mixing as posted.
I had a variant which assigned mix as rotate(mix,constant) + (mix^fast_mix). That would pass cleanly with mix directly outputted (with no multiplication) - but I couldn’t get Z3 prover to show injectivity so I decided to go with the posted route.
I'm not sure that the claim "the mix function is injective" is sufficient to support the claim "The period is at least 2^128". If the mix is reversible then it forms a permutation on 2^192, but that does not imply that it forms a single cyclic permutation.
For example, if f(0) = 1 and f(1) = 0, even if the rest of f's domain is injective the period of f is still only 2 when the initial value is 0 or 1.
I wasn't able to analyze the cyclic behavior of the mix directly, but for the purpose of minimal period only fast_loop and slow_loop are used (as a 128bit counter).
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!
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.
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.
From the Github repo: "Created by Daniel Cota after he fell down the PRNG rabbit-hole by circumstance." I understand how that can happen.
Wondering how this PRNG compares to PCG PRNGs that also claim to be "simple fast space-efficient statistically good algorithms" and "hard to predict" [0].
In any case, it's good to see the excellent work being accomplished in this space.
Yes, indeed it is. While these PRNGs are all pretty decent, improvements are always welcome. Most impressive is the utter simplicity of the algorithms, including LoopMix128. Definitely makes it easy to incorporate high-quality PRNG functionality in applications.
Using only 32bit fast_loop and mix (for 64bits of state) passes PractRand with 64bit output up to 256GB with only one unusual. That's about a 100 bit 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.
- your test codes are not reproducible: running twice generates different sets of numbers because they have unknown seeds. As a result, if you change (a) compilers or compiler switches, (b) operating system versions, (c) host processors or (d) architectures, the question arises: what is wrong? What is different? This is known as a regression test.
- You only test a few times? I think one hundred BigCrush tests, using a set of 100 seeds, would be suitable. Takes a few days on an RPI 4 (with cooler). Run the same 100 tests on a Ryzen and Xeon, just to be sure. They should be bit-for-bit identical.
- 100 BigCrush tests should show only a handful (4 or fewer) duplicate test failures.
- your seeds are almost great: too many people think "42" is random in a space of 0 through 2^64. But 0xdeadbeef is so 1990s...
- you don't need different seeds per PRNG; you can generate reproducible ones (2x to 4x 64bit) from a single good 64-bit seed and your favourite PRNG. Your test code should read a seed or set from the command line (see first item).
- warmups? Really?
- Remember that BigCrush and other tests are created by mathematical people not practical people. Do they test for equal numbers of odd and even results? Hmmmm....
What a great set of feedback. Thank you! I'll look at it as an acton item list.
And you are so right about being just one month in. Every time I think I'm starting to understand what's going on here, I realize the maze just keeps getting deeper.
NOTE: I found a counterexample using Z3 Solver in which fast_loop maps to itself (0x5050a1e1d03b6432). A new version will be released with fast_loop and slow_loop as simple Weyl Sequences.
When do people both want (PRNG performance is a measurable fraction of total program performance) and can use (no security constraints) an extremely fast PRNG?
It's common in graphics and audio programming. In audio, maybe you're synthesizing noise or any of the myriad synthesis techniques that require noise. In graphics you have lighting, textures, etc that can use this. And when you're doing something every audio sample or every pixel, "extremely fast" is desirable. The question of whether to use a pre-rendered lookup table or a fast algorithm often comes up (and has no universal answer... though I always go for the latter)
MurmurHash/SMHasher author here. While I don't doubt this passes BigCrush etc, I do find it very surprising that it does.
The state update function is effectively "a = rotate(a, constant) + b; b = rotate(b, constant) + constant;" and the output derivation is "output = (a + b) * constant".
That update function is _barely_ nonlinear, and the output derivation is linear. The output would probably be slightly better as "(a ^ b) * constant".
The slow_loop thing to guarantee 2^128 period is probably not needed - anyone with an application that cares about a period that high is probably going to choose a more robust generator (a few rounds of hardware-accelerated AES in counter mode is your best bet there)
The use of the Z3 prover is neat and I should read up on that more.
Hello! Awesome work on your hashing by the way!
When iterating I first tried to make fast_loop as random as possible by trying all possible rotational values and then having each option tested in PractRand 1000 times from 256M to 8GB. There was a wide range of performance by rotation. 47 was the best (for the GR constant) and resulted in the most tests being passed. The goal was a stronger than normal core for the PRNG that could feed actively into mix.
I found the multiplication to be necessary for passing PractRand and BigCrush with the state mixing as posted.
I had a variant which assigned mix as rotate(mix,constant) + (mix^fast_mix). That would pass cleanly with mix directly outputted (with no multiplication) - but I couldn’t get Z3 prover to show injectivity so I decided to go with the posted route.
I'm not sure that the claim "the mix function is injective" is sufficient to support the claim "The period is at least 2^128". If the mix is reversible then it forms a permutation on 2^192, but that does not imply that it forms a single cyclic permutation.
For example, if f(0) = 1 and f(1) = 0, even if the rest of f's domain is injective the period of f is still only 2 when the initial value is 0 or 1.
That is correct. The permutations will likely break up into multiple cycles, and the cycle lengths follow a poisson distribution.
https://dms.umontreal.ca/~andrew/PDF/CycleLengths1.pdf
I wasn't able to analyze the cyclic behavior of the mix directly, but for the purpose of minimal period only fast_loop and slow_loop are used (as a 128bit counter).
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
I'll have to re-optimize the rotations for the smaller state size, but I will do it and report here.
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...
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.
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.
Super useful link. Thank you!
From the Github repo: "Created by Daniel Cota after he fell down the PRNG rabbit-hole by circumstance." I understand how that can happen.
Wondering how this PRNG compares to PCG PRNGs that also claim to be "simple fast space-efficient statistically good algorithms" and "hard to predict" [0].
In any case, it's good to see the excellent work being accomplished in this space.
[0] https://www.pcg-random.org/
I just added PGC64 to benchmark.c in the Github. PCG64 speed looks to be about the same as xoroshiro128++.
Yes, indeed it is. While these PRNGs are all pretty decent, improvements are always welcome. Most impressive is the utter simplicity of the algorithms, including LoopMix128. Definitely makes it easy to incorporate high-quality PRNG functionality in applications.
How does this compare to a 128 bit MCG or LCG?
See https://www.pcg-random.org/posts/does-it-beat-the-minimal-st... for examples and constants
Using only 32bit fast_loop and mix (for 64bits of state) passes PractRand with 64bit output up to 256GB with only one unusual. That's about a 100 bit 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.
Some comments, in random order:
- your test codes are not reproducible: running twice generates different sets of numbers because they have unknown seeds. As a result, if you change (a) compilers or compiler switches, (b) operating system versions, (c) host processors or (d) architectures, the question arises: what is wrong? What is different? This is known as a regression test.
- try shishua as another speedy PRNG. See https://espadrine.github.io/blog/posts/shishua-the-fastest-p...
- You only test a few times? I think one hundred BigCrush tests, using a set of 100 seeds, would be suitable. Takes a few days on an RPI 4 (with cooler). Run the same 100 tests on a Ryzen and Xeon, just to be sure. They should be bit-for-bit identical.
- 100 BigCrush tests should show only a handful (4 or fewer) duplicate test failures.
- your seeds are almost great: too many people think "42" is random in a space of 0 through 2^64. But 0xdeadbeef is so 1990s...
- you don't need different seeds per PRNG; you can generate reproducible ones (2x to 4x 64bit) from a single good 64-bit seed and your favourite PRNG. Your test code should read a seed or set from the command line (see first item).
- warmups? Really?
- Remember that BigCrush and other tests are created by mathematical people not practical people. Do they test for equal numbers of odd and even results? Hmmmm....
- try Collatz, see https://news.ycombinator.com/item?id=39733685
- the tests are very cache-friendly; nobody does this. It's true that everybody compares against this unrealistic scenario, however.
- if you've spent a month in twisty little PRNG passages, all alike, you are on the first steps of your journey. Take a towel.
J
What a great set of feedback. Thank you! I'll look at it as an acton item list.
And you are so right about being just one month in. Every time I think I'm starting to understand what's going on here, I realize the maze just keeps getting deeper.
NOTE: I found a counterexample using Z3 Solver in which fast_loop maps to itself (0x5050a1e1d03b6432). A new version will be released with fast_loop and slow_loop as simple Weyl Sequences.
Also interesting to include PCG for comparison.
Just added to benchmark.c in the Github. Performance is comparable to xoroshiro128++.
How does this compare performance wise with RomuQuad and RomuDuoJr? (romu-random.org/)
Added the Romu variants to benchmark.c. Here are the current results:
LoopMix128 ns/call: 0.380 ns
xoroshiro128++ ns/call: 0.757 ns
wyrand ns/call: 0.379 ns
PCG64 ns/call: 0.757 ns
RomuQuad ns/call: 0.575 ns
RomuDuoJr ns/call: 0.416 ns
> after he fell down the PRNG rabbit-hole by circumstance
Curious to learn more about the circumstance :)
I have an offline poker app, and a user asked me what the algorithm was to generate the random numbers. That was a month ago. :)
I feel this in my bones. I’m not qualified to comment on the quality of the result, but I certainly appreciate and identify with the circumstances.
That's funny that for poker you made your own thing instead of implementing ChaCha or something. Cool though!
When do people both want (PRNG performance is a measurable fraction of total program performance) and can use (no security constraints) an extremely fast PRNG?
It's common in graphics and audio programming. In audio, maybe you're synthesizing noise or any of the myriad synthesis techniques that require noise. In graphics you have lighting, textures, etc that can use this. And when you're doing something every audio sample or every pixel, "extremely fast" is desirable. The question of whether to use a pre-rendered lookup table or a fast algorithm often comes up (and has no universal answer... though I always go for the latter)
That seems like it would be well served by deterministic dithering. (The terminology is not precise, but I'm not sure what else to call it.)
For graphics you probably want a quasirandom https://en.m.wikipedia.org/wiki/Low-discrepancy_sequence
A purely random function can lead to clumping and aliasing.
Monte Carlo simulations would be the obvious example.
Benchmarking. fio and iperf
Path tracing