Show HN: LoopMix128 – Fast C PRNG (.46ns), 2^128 Period, BigCrush/PractRand Pass

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.

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

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/

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.

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

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

Also interesting to include PCG for comparison.

How does this compare performance wise with RomuQuad and RomuDuoJr? (romu-random.org/)

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

Curious to learn more about the circumstance :)

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?

[dead]