www.digitalmars.com         C & C++   DMDScript  

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


          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 puremagic.com
          Reporter: r.97all gmail.com

As you know, std.random recommends MT19937 as the default random number
generator Random:
and, the current implementation of std.random.uniform for integral types use
modulo operation:

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

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

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.

Dec 04 2014