Implement Romu RNG

[utterstep]

Background

There is a new family of PRNGs, claiming to be equal to PCG in terms of quality (randomness), but faster in execution.
Info, including C source code and paper about it: http://www.romu-random.org/

Feature request

Maybe it's reasonable to consider implementing Romu PRNG, as an alternative to PCG, used currently in SmallRng?

If that is the case — I can try doing it myself, however I'll need some guidance on at least "where exactly this alternative should be inside rand crate"-topic :)

[dhardy]

As a first step, I recommend creating a rand_romu crate in rngs — or even in your private repo.

Beyond that, choosing an algorithm for SmallRng is not a simple topic, as you can see in #910. Perhaps @vigna may like to comment on Romu. But don't expect a hasty decision (except possibly no).

[utterstep]

As a first step, I recommend creating a rand_romu crate in rngs — or even in your private repo.

Got it! Will try to land PR in the coming week.

[vigna]

I'm not a particularly big fan of this kind of generator (sometimes unappropriately called "chaotic"). The main problem is that you have no way to prove that the period is long.

In this class, SFC I think it is better. By adding a counter to the state change, it forces cycles to be at least 2^64 (and likely more) long, which is not perfect but certainly better than no guarantee. The difference in speed with SFC is in the order of 1-2% in my tests.

The Romu paper contains the usual proof about the probability of short cycles in a random permutation. It is the same proof of Bob Jenkins for his generator, and I've seen it several times. It is just a proof about a (known) fact of random permutations. There is no connection with the generator—and indeed the proof is always the same, no matter which the generator is.

The "connection" is the assumption that one can treat a specific permutation as it if was random, which has no mathematical basis. It is like assuming your generator is random, and prove that it is random.

The assumption could be maybe reasonable if you consider Romu's parameters picked at random, but also in this case, say, Romutrio has one 64-bit parameter and two 6-bit parameters: thus, of all possible random permutations Romutrio can materialize at most 2^76. But on 192 bits of state the permutations are (2^192)!, so basically the probability of hitting a permutation generated by Romu if you pick one at random is zero. So modeling the behavior of these permutations as if they were random, again, has no mathematical sense.

[SuperFluffy]

I saw the thread on HN and thought I give it a go: https://github.com/superfluffy/romu.rs

Turns out, implementing it did not teach my much, and my understanding of pRNGs is still very limited.

Implementing RngCore for it it is not a big task, but I wonder if including it into rust-random will be at all interesting, after @vigna's comment?

[dhardy]

I agree with @vigna's points about cycle length: SFC's approach is preferable. This doesn't make Romu a bad generator per-se, but as @vigna says the argument about being unlikely to hit a short cycle is not as robust as it may appear.

I am not opposed to adding your implementation to the RNGs repo (though it would need some test vectors), but the algorithm used by SmallRng should be reasonably well established (this is very new) and with some third-party review.