[erlang-questions] RNG algorithm choice for uniform natural numbers

[Raimo Niskanen]

On Thu, Aug 02, 2018 at 02:19:17PM +0200, Krzysztof Jurewicz wrote:
> I’m looking for an algorithm to perform a transparent, reproducible generation of an uniform sequence of natural numbers. There are three RNG algorithms documented in the rand module:
> 
> • Xoroshiro116+. According to the linked page at http://xoshiro.di.unimi.it/ , it is suitable only for floating point numbers, so it doesn’t fit. Moreover, the page actually describes an algorithm with 64-bit precision, while rand implements a variant with 56-bit precision. It looks like the latter is implemented only in Erlang, so there is little practical interoperability between languages.
> • Xorshift1024*. It fails the BigCrush test according to https://lemire.me/blog/2017/09/15/the-xorshift1024-random-number-generator-fails-bigcrush/ .

It is a known fact that the lowest bits of Xors... generators with * and +
scramblers are of lower quality than the rest.  If he had used the high 32
bits I predict that it would have passed.

The author of Xoroshiro, etc, thinks that this is a small problem.

> • Xorshift116+. The comment about 58-bit precision being rare applies (according to https://github.com/jj1bdx/emprng/ , “the original exsplus was Xorshift128+”). Xorshift128+ fails the BigCrush test, so I presume that xorshift116+ fails it too.

I would also guess so.

> 
> So… is there any particular reason for the rand module to not implement xoshiro256**, which is more widespread than 58-bit precision algorithms and, according to its creators, “has excellent (sub-ns) speed, a state space (256 bits) that is large enough for any parallel application, and it passes all tests we are aware of”?

Any 64-bit word algorithm runs about 2..3 (or more) times slower
than a 58-bit output word one, on 64-bit Erlang.  That's why.

Implementation of a new algorithm should be fairly easy (mostly
cut-and-paste).  Unfortunately the bignum operations that 64-bit
calculations provoke hits performance a lot.

We do not have any generator that uses the new ** scrambler that makes
all tests pass BigCrush (with the lowest bits), yet, but...

I have a pull request for Xoroshiro928** that is a reworked Xoroshiro1024**
with 58-bit word size, exactly because of speed reasons.  For the next
step I was thinking about rewriting Xoroshiro256** to 58-bit, but the
resulting algorighm would not be much faster than Xoroshiro928**,
it would only have smaller state space, hopefully.  So I am not certain
that it would be worth implementing.

    https://github.com/erlang/otp/pull/1857

I have never thought about implementing the new 64-bit word size generators
since nobody has asked for inter-platform compatibility before, and you still
have to be careful with bit compatibility.  It is only when you request
the generator word size range that you get the raw numbers.  And for
floating point if you are lucky that both platforms use the same bits
(low/high/middle).

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB