[Issue 10550] New: Xorshift32 and Xorshift160 do not generate uniformly-distributed random numbers

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=10550

           Summary: Xorshift32 and Xorshift160 do not generate
                    uniformly-distributed random numbers
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: joseph.wakeling at webdrake.net


--- Comment #0 from Joseph Rushton Wakeling <joseph.wakeling at webdrake.net> 2013-07-05 07:11:03 PDT ---
The output of Xorshift32 and Xorshift160 departs strongly from uniformity.

The issue for Xorshift32 can be seen clearly even in this very simple piece of
code:

    auto rng = Xorshift32(unpredictableSeed);

    foreach(r; rng.take(20))
    {
        writeln(r, "\t", rng.min, "\t", rng.max);
    }

... where we can see that the generated values are always much closer to
rng.min than rng.max.

A more sophisticated example (but still very simple) is provided in the test of
uniformity in https://github.com/WebDrake/std.random.test -- specifically, in:
https://github.com/WebDrake/std.random.test/blob/master/uniform.d
https://github.com/WebDrake/std.random.test/blob/master/test/stats.d

... which generates millions of random numbers using uniform(0.0, 0.1, rng),
divides them up into bins of width 0.05, and outputs the histogram and
cumulative distribution values.

For Xorshift32, this gives:

Generating 10000000 random numbers in [0, 1) with XorshiftEngine!(uint, 32, 13,
17, 5)
    5    1    1
    10    0    1
    15    0    1
    20    0    1
    25    0    1
    30    0    1
    35    0    1
    40    0    1
    45    0    1
    50    0    1
    55    0    1
    60    0    1
    65    0    1
    70    0    1
    75    0    1
    80    0    1
    85    0    1
    90    0    1
    95    0    1
    100    0    1

... while for Xorshift160 it gives:

Generating 10000000 random numbers in [0, 1) with XorshiftEngine!(uint, 160, 2,
1, 4)
    5    0.0535713    0.0535713
    10    0.0208334    0.0744047
    15    0.0446429    0.119048
    20    0.047619    0.166667
    25    0.0714286    0.238095
    30    0.0238096    0.261905
    35    0.0208333    0.282738
    40    0.0416667    0.324405
    45    0.0595238    0.383929
    50    0.0446429    0.428572
    55    0.0476191    0.476191
    60    0.0595239    0.535714
    65    0.0714285    0.607143
    70    0.0535714    0.660714
    75    0.0535713    0.714286
    80    0.0744045    0.78869
    85    0.0744049    0.863095
    90    0.0357143    0.898809
    95    0.0238095    0.922619
    100    0.0773811    1

Other RNGs, including other Xorshift types, appear to generate correct
proportions.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------