search

rust-random / book

The Rust Rand Book
Other
49 stars 19 forks source link

Fix predictability statements #17

Closed vks closed 4 years ago

vks commented 4 years ago

Also recommend xoshiro256++ over xoshiro256**.

vks commented 4 years ago

Fixes https://github.com/rust-random/rand/issues/905.

dhardy commented 4 years ago

As far as I understand, the only reason to recommend Xoshiro256++ over is for the vectorisation, which this implementation doesn't provide (and would have to be a distinct generator). So I don't think changing the recommendation here makes sense, especially since the variant is supposedly stronger. @vigna?

vigna commented 4 years ago

There is no absolute "better" because, for example, xoshiro256++ has much higher linear complexity. In the original paper I was not able to prove enough equidistribution for the ++ scrambler—my idea was to obtain the maximum minus one, like for the + scrambler, but the proof eluded me. In the last version, I was able to come up with a new idea and at that point the ++ scrambler was included, and I started to promote the ++ scrambler vs. the ** scrambler for a number of reasons.

From a testing viewpoint, I cannot measure any difference. The ++ scrambler should be faster (no multiplications) but on different architectures results are different (e.g., hardware people love ++). Theoretically, xoshiro256++ is 3-dimensionally equidistributed, whereas xoshiro256** is 4-dimensionally equidistributed (the maximum possible), but as you notice in your book this actually means that you can prove that xoshiro256** will fail a collision test for 256-bit blocks after about 2^128 outputs. This is entirely academic, of course, as there's no way till the end of times to enumerate so many values, but makes you think whether maximum equidistribution is actually a good idea.

So, since you have already implemented it my answer would be yes, suggest as first choice xoshiro256++ (and I hope not to be proved wrong, this is always a risky business...).

vks commented 4 years ago

As far as I understand, the only reason to recommend Xoshiro256++ over ** is for the vectorisation, which this implementation doesn't provide (and would have to be a distinct generator).

We have optional SIMD support in Rand, for which it might matter. (Not sure about this, I never used it.)