I'd rather read the prompt (claytonwramsey.com)

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

the_othernet · 43m ago

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

Straw · 7m 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...

aappleby · 3h ago

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.

aappleby · 3h 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.

the_othernet · 3h ago

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

the_othernet · 3h 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.

jrapdx3 · 3h 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.

[0] https://www.pcg-random.org/

the_othernet · 3h ago

I just added PGC64 to benchmark.c in the Github. PCG64 speed looks to be about the same as xoroshiro128++.

jrapdx3 · 1h 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.

zX41ZdbW · 4h ago

Also interesting to include PCG for comparison.

the_othernet · 3h ago

Just added to benchmark.c in the Github. Performance is comparable to xoroshiro128++.

RainyDayTmrw · 3h 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 · 3h 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)

986aignan · 3h ago

Monte Carlo simulations would be the obvious example.

zX41ZdbW · 4h ago

> after he fell down the PRNG rabbit-hole by circumstance

Curious to learn more about the circumstance :)

the_othernet · 3h 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 · 2h 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.