[Issue 10550] 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



--- Comment #9 from Joseph Rushton Wakeling <joseph.wakeling at webdrake.net> 2013-07-08 07:51:04 PDT ---
(In reply to comment #8)
> I remember correctly, I generated test cases from paper based C implementation.
> I implemented C version first and generated test cases for D unittest.
> After that, I implemented XorshiftEngine for D-ish code.

Ahhh, OK.  Then I think we can reasonably assume that these test sequences,
like the code in std.random, reflect typos in Marsaglia's paper.

For Xorshift32 we can see that Marsaglia's C implementation at the very top of
p.32 contains at least one typo -- the second bitshift y=(y>>17) should be
y^=(y>>17).  I am strongly suspicious that there is a second typo for the value
of c, which should be 15 rather than 5.

It's definitely not the only such typo in the paper -- Panneton and L'Ecuyer
(2005) note that the (a, b, c) triple (9, 5, 1) should be (9, 5, 14).

In any case, we lose nothing by using the triple (13, 17, 15) since it's
acknowledged in the paper as a valid choice.

For Xorshift160 I think that the code given has a typo for the bitshift with
respect to a, as in all other such code examples the bitshift is in the
opposite direction to that for b and c.  In general, the bitshifts seem to
follow a rule of two in one direction, one in the other.

In summary, I think we can proceed as follows:

   * confirm with experts in the field the typos in the paper

   * generate new checking sequences with corrected versions of the C code

   * correct the D code and unittests accordingly

I am actually inclined to jump ahead with getting the patches to Phobos done,
because I'm pretty confident my analysis here is correct :-)

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