digitalmars.D.bugs - [Issue 13822] New: std.random.uniform(0, 16) takes lower bits
- via Digitalmars-d-bugs (47/47) Dec 04 2014 https://issues.dlang.org/show_bug.cgi?id=13822
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 puremagic.com Reporter: r.97all 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. --
Dec 04 2014