[Issue 13822] New: std.random.uniform(0, 16) takes lower bits

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=13822

          Issue ID: 13822
           Summary: std.random.uniform(0, 16) takes lower bits
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: Phobos
          Assignee: nobody at puremagic.com
          Reporter: r.97all at gmail.com

As you know, std.random recommends MT19937 as the default random number
generator Random:
https://github.com/D-Programming-Language/phobos/blob/v2.066.1/std/random.d#L708
and, the current implementation of std.random.uniform for integral types use
modulo operation:
https://github.com/D-Programming-Language/phobos/blob/v2.066.1/std/random.d#L1263

Actually, as long as using MT19937, the implementation of uniform is not the
best, in the view of high-dimensional equidistribution.
In this post, "X is k-dimensionally equidistributed" roughly means that "it is
safe to assume x[] is uniformly random after the following:
x = [];
foreach (i; 0..k)
    x ~= X;
".

An example is when X is uniform!("[)", uint, uint, MT19937)(0, 16, rng).
This is equivalent to taking lower 4 bits of an uint generated by MT19937.
Though I cannot give the evidence, according to a research partner of mine,
this is 2492-dimensionally equidistributed but not 2493-dimensionally
equidistributed.

If we took upper 4 bits of an uint generated by MT19937, it is shown to be
4984-dimensionally equidistributed, as shown in the paper [1].

Generally but roughly speaking, when a pseudo-random number generator is
designed to be generate a uniform pseudo-random integer in [0..2^32),
if it is good for dividing by 2^32 to have a real number in [0..1), then it is
good for reversing bits and then taking modulo to have an integer in [0..n).

[1] Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random
Number Generator
http://dl.acm.org/citation.cfm?id=272995


Since this issue is not critical (In the above example, 2492-dimensional
equidistribution is enough in most situations), I'm not sure fixing it by
reversing bits worth the loss of speed, so that I mark this as an enhancement.
There are some F2-linear pseudo-random number generators with better
equidistribution property, with a little drawback in speed.

--