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.
the_othernet 1 days ago [-]
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.
aappleby 1 days ago [-]
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.
grumbelbart 20 hours ago [-]
That is correct. The permutations will likely break up into multiple cycles, and the cycle lengths follow a poisson distribution.
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).
Straw 1 days 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!
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 1 days 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.
the_othernet 1 days ago [-]
Super useful link. Thank you!
the_othernet 4 hours ago [-]
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.
jrapdx3 1 days ago [-]
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.
I just added PGC64 to benchmark.c in the Github. PCG64 speed looks to be about the same as xoroshiro128++.
jrapdx3 1 days ago [-]
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.
j_not_j 9 hours ago [-]
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.
- 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....
- 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
the_othernet 7 hours ago [-]
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.
zX41ZdbW 1 days ago [-]
Also interesting to include PCG for comparison.
the_othernet 1 days ago [-]
Just added to benchmark.c in the Github. Performance is comparable to xoroshiro128++.
camel-cdr 1 days ago [-]
How does this compare performance wise with RomuQuad and RomuDuoJr?
(romu-random.org/)
the_othernet 1 days ago [-]
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
zX41ZdbW 1 days ago [-]
> after he fell down the PRNG rabbit-hole by circumstance
Curious to learn more about the circumstance :)
the_othernet 1 days ago [-]
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. :)
kstrauser 1 days 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.
01HNNWZ0MV43FF 1 days ago [-]
That's funny that for poker you made your own thing instead of implementing ChaCha or something. Cool though!
RainyDayTmrw 1 days ago [-]
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?
pierrec 1 days ago [-]
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)
RainyDayTmrw 1 days ago [-]
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.)
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.
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.
https://dms.umontreal.ca/~andrew/PDF/CycleLengths1.pdf
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
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...
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.
I did have to alter the output to be "(GR * mix) + fast_loop" and change the rotation constants to be 12 and 5.
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/
See https://www.pcg-random.org/posts/does-it-beat-the-minimal-st... for examples and constants
- 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
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.
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
Curious to learn more about the circumstance :)
A purely random function can lead to clumping and aliasing.