[Mono-dev] Issues with System.Random
Adrian Willenbücher
AWillenbuecher at gmx.de
Mon Mar 15 18:32:40 EDT 2010
Hello,
I noticed that the implementation of System.Random has a couple of flaws:
1.) The algorithm for the random data fails miserably in some of the Diehard tests (http://i.cs.hku.hk/~diehard/), even
if it is slightly changed in order to generate full 32-bit random values.
2.) It might return a negative value:
"if (retVal < 0) retVal += MBIG;"
results in -1 for retVal == int.MinValue, which is forbidden.
3.) The use of floating-point arithmetic introduces numerical errors since int.MaxValue is not a power of two (so
1.0/int.MaxValue is not representable without errors).
I reimplemented the class using the xorshift algorithm by George Marsaglia, which he posted on comp.lang.c
(http://groups.google.com/group/comp.lang.c/browse_thread/thread/a9915080a4424068/), and tested it with the Diehard
battery of tests (it passed); it avoids any FP arithmetic where it is not needed.
The interface of the class is still pretty screwed up, but sadly we can't change that.
I also completely rewrote the unit tests; they are stricter and more precise now. The expected values were produced by
running the C-code given by George Marsaglia.
The patches for the two files can be found below.
Regards,
Adrian
Index: mcs/class/corlib/System/Random.cs
===================================================================
--- mcs/class/corlib/System/Random.cs (revision 153607)
+++ mcs/class/corlib/System/Random.cs (working copy)
@@ -4,12 +4,11 @@
// Authors:
// Bob Smith (bob at thestuff.net)
// Ben Maurer (bmaurer at users.sourceforge.net)
+// Adrian Willenbücher (AWillenbuecher at gmx.de)
//
// (C) 2001 Bob Smith. http://www.thestuff.net
// (C) 2003 Ben Maurer
//
-
-//
// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
@@ -39,104 +38,98 @@
[ComVisible (true)]
public class Random
{
- const int MBIG = int.MaxValue;
- const int MSEED = 161803398;
+ private uint [] state = new uint [5];
- int inext, inextp;
- int [] SeedArray = new int [56];
-
- public Random ()
- : this (Environment.TickCount)
+ public Random () : this(Environment.TickCount)
{
}
public Random (int Seed)
{
- int ii;
- int mj, mk;
-
- // Numerical Recipes in C online @ http://www.library.cornell.edu/nr/bookcpdf/c7-1.pdf
- mj = MSEED - Math.Abs (Seed);
- SeedArray [55] = mj;
- mk = 1;
- for (int i = 1; i < 55; i++) { // [1, 55] is special (Knuth)
- ii = (21 * i) % 55;
- SeedArray [ii] = mk;
- mk = mj - mk;
- if (mk < 0)
- mk += MBIG;
- mj = SeedArray [ii];
- }
- for (int k = 1; k < 5; k++) {
- for (int i = 1; i < 56; i++) {
- SeedArray [i] -= SeedArray [1 + (i + 30) % 55];
- if (SeedArray [i] < 0)
- SeedArray [i] += MBIG;
- }
- }
- inext = 0;
- inextp = 31;
+ state [0] = 123456789 ^ (uint)Seed;
+ state [1] = 362436069;
+ state [2] = 521288629;
+ state [3] = 88675123;
+ state [4] = 886756453;
}
- protected virtual double Sample ()
+ /* Uses the xorshift algorithm by George Marsaglia on:
+ * http://groups.google.com/group/comp.lang.c/browse_thread/thread/a9915080a4424068/
+ */
+ private uint NextUInt32 ()
{
- int retVal;
+ var temp = state [0] ^ (state [0] >> 7);
+ temp = temp ^ (temp << 13);
- if (++inext >= 56) inext = 1;
- if (++inextp >= 56) inextp = 1;
+ for (var i = 0; i < 4; ++i)
+ state [i] = state [i + 1];
+
+ state [4] = (state [4] ^ (state [4] << 6)) ^ temp;
+
+ return (2 * state [1] + 1) * state [4];
+ }
- retVal = SeedArray [inext] - SeedArray [inextp];
+ private uint NextUInt32 (uint maxValue)
+ {
+ if (maxValue == 0)
+ return 0;
- if (retVal < 0)
- retVal += MBIG;
+ // Mask for all bits beneath and including most significant bit
+ var mask = maxValue;
+ mask = mask | (mask >> 1);
+ mask = mask | (mask >> 2);
+ mask = mask | (mask >> 4);
+ mask = mask | (mask >> 8);
+ mask = mask | (mask >> 16);
+
+ uint x;
+ do {
+ x = NextUInt32 () & mask;
+ } while (x >= maxValue);
+
+ return x;
+ }
- SeedArray [inext] = retVal;
+ protected virtual double Sample ()
+ {
+ return NextUInt32 () * (1.0 / 4294967296.0);
+ }
- return retVal * (1.0 / MBIG);
+ public virtual double NextDouble ()
+ {
+ return Sample ();
}
public virtual int Next ()
{
- return (int)(Sample () * int.MaxValue);
+ const uint cutoff = 2147483648u;
+ var x = NextUInt32 ();
+ return x >= cutoff ? (int)(x - cutoff) : (int)x;
}
public virtual int Next (int maxValue)
{
if (maxValue < 0)
- throw new ArgumentOutOfRangeException(Locale.GetText (
- "Max value is less than min value."));
+ throw new ArgumentOutOfRangeException ("maxValue is less than minValue.");
- return (int)(Sample () * maxValue);
+ return (int)NextUInt32 ((uint)maxValue);
}
public virtual int Next (int minValue, int maxValue)
{
if (minValue > maxValue)
- throw new ArgumentOutOfRangeException (Locale.GetText (
- "Min value is greater than max value."));
+ throw new ArgumentOutOfRangeException ("minValue is greater than maxValue.");
- // special case: a difference of one (or less) will always return the minimum
- // e.g. -1,-1 or -1,0 will always return -1
- uint diff = (uint) (maxValue - minValue);
- if (diff <= 1)
- return minValue;
-
- return (int)((uint)(Sample () * diff) + minValue);
+ return (int)NextUInt32 ((uint)(maxValue - minValue)) + minValue;
}
public virtual void NextBytes (byte [] buffer)
{
if (buffer == null)
- throw new ArgumentNullException ("buffer");
+ throw new ArgumentNullException ("buffer is null.");
- for (int i = 0; i < buffer.Length; i++) {
- buffer [i] = (byte)(Sample () * (byte.MaxValue + 1));
- }
+ for (var i = 0; i < buffer.Length; ++i)
+ buffer [i] = (byte)NextUInt32 ();
}
-
- public virtual double NextDouble ()
- {
- return this.Sample ();
- }
}
}
Index: mcs/class/corlib/Test/System/RandomTest.cs
===================================================================
--- mcs/class/corlib/Test/System/RandomTest.cs (revision 153607)
+++ mcs/class/corlib/Test/System/RandomTest.cs (working copy)
@@ -2,8 +2,7 @@
// System.Random Test Cases
//
// Authors:
-// Bob Smith <bob at thestuff.net>
-// Sebastien Pouliot <sebastien at ximian.com>
+// Adrian Willenbücher <AWillenbuecher at gmx.de>
//
// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
//
@@ -28,104 +27,159 @@
//
using NUnit.Framework;
+using NUnit.Framework.SyntaxHelpers;
using System;
namespace MonoTests.System {
[TestFixture]
public class RandomTest {
+#region Next ()
+ [Test]
+ public void SeededSequence1 ()
+ {
+ int [] expected = { 256171686, 924759460, 1326063082, 1748505655, 770391478, 893875434, 1927233845,
+ 1915141213, 1304416967, 1040106214, 1413028753, 517287625, 164449503, 484347407, 134543290, 1497001777,
+ 1437568641, 1805630818, 442001507, 276608167 };
-#if false
- //
- // This test will fail, given enough runs.
- //
- // It is an ad-hoc test for distribution, and does not work
- // 100% of the time.
- //
+ var rng = new Random (-1234);
+
+ foreach (var x in expected)
+ Assert.That (x, Is.EqualTo (rng.Next ()), "#A01");
+ }
+
[Test]
- public void NextDouble ()
+ public void SeededSequence2 ()
{
- Random r = new Random ();
- int i;
- double c=0;
- for (i=0; i<20; i++)
- c += r.NextDouble ();
- c/=i;
- Assert.IsTrue (c.ToString () + " is out of range.", c < .7 && c > .3);
+ int [] expected = { 545630734, 1871987772, 32100770, 2055383023, 588683182, 770534463, 129782961, 1446710564,
+ 1212431109, 342542925, 1688944563, 631123534, 1233995261, 1977968768, 1785858814, 375605933, 1274134403,
+ 2089187981, 919781722, 1124065708 };
+
+ var rng = new Random (0);
+
+ foreach (var x in expected)
+ Assert.That (x, Is.EqualTo (rng.Next ()), "#A02");
}
-#endif
+ [Test]
+ public void SeededSequence3 ()
+ {
+ int [] expected = { 428190222, 177488956, 1323946402, 2139269103, 1846974382, 2037083199, 817648817,
+ 341642532, 1854421765, 726977101, 2110569395, 1682606670, 414270973, 582707328, 2058012414, 664397541,
+ 735971203, 1192835725, 373417658, 1356677716 };
+ var rng = new Random (int.MaxValue);
+
+ foreach (var e in expected)
+ Assert.That (rng.Next (), Is.EqualTo (e), "#A03");
+ }
+#endregion
+
+#region Next (int)
[Test]
- public void CompareStreamWithSameSeed ()
+ public void NextMax1 ()
{
- Random r = new Random (42);
- Random r2 = new Random (42);
- double c=0, c2=0;
- for (int i=0; i<20; i++) {
- c += r.NextDouble ();
- c2 += r2.NextDouble ();
- }
- Assert.AreEqual (c, c2, "Compare");
+ var rng = new Random (0);
+ Assert.That (rng.Next (0), Is.EqualTo (0), "#B01");
}
[Test]
- public void Next ()
+ public void NextMax2 ()
{
- Random r = new Random ();
- for (int i=0; i<20; i++) {
- long c = r.Next ();
- Assert.IsTrue (c < Int32.MaxValue && c >= 0, "Next(" + i + ")");
+ var rng = new Random (0);
+ int [] maxValues = { 1, 2, 3, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
+ foreach (var maxValue in maxValues) {
+ for (var i = 0; i < 100; ++i) {
+ var x = rng.Next (maxValue);
+ Assert.That (x, Is.GreaterThanOrEqualTo (0), "#B02a");
+ Assert.That (x, Is.LessThan (maxValue), "#B02b");
+ }
}
}
[Test]
- public void NextMax()
+ [ExpectedException ("System.ArgumentOutOfRangeException", UserMessage="#B03")]
+ public void NextMax3 ()
{
- Random r = new Random();
- for (int i=0; i<20; i++) {
- long c = r.Next (10);
- Assert.IsTrue (c < 10 && c >= 0, "NextMax(" + i + ")");
- }
+ var rng = new Random (0);
+ rng.Next (-1);
}
+#endregion
+#region Next (int, int)
[Test]
- public void NextMinMax()
+ public void NextMinMax1 ()
{
- Random r = new Random ();
- Assert.AreEqual (42, r.Next (42, 42), "#1 Failed where min == max");
- Assert.AreEqual (Int32.MaxValue, r.Next (Int32.MaxValue, Int32.MaxValue), "#2 Failed where min == max");
- Assert.AreEqual (Int32.MinValue, r.Next (Int32.MinValue, Int32.MinValue), "#3 Failed where min == max");
- Assert.AreEqual (0, r.Next (0, 0), "#4 Failed where min == max");
- for (int i = 1; i <= Int32.MaxValue / 2; i *= 2) {
- long c = r.Next (i, i * 2);
- Assert.IsTrue (c < i * 2, "At i=" + i + " c < i*2 failed");
- Assert.IsTrue (c >= i, "At i=" + i + " c >= i failed");
+ var rng = new Random (0);
+ Assert.That (rng.Next (-50, -50), Is.EqualTo (-50), "#C01");
+ }
+
+ [Test]
+ public void NextMinMax2 ()
+ {
+ var rng = new Random (0);
+ int [] minValues = { -4, -3, -2, 0, 4, 5, 6, 7, 8, 0, int.MinValue, int.MinValue };
+ int [] maxValues = { -3, 0, 10, 1, 5, 7, 7, 15, 16, int.MaxValue, 0, int.MaxValue };
+ for (var i = 0; i < minValues.Length; ++i) {
+ var minValue = minValues [i];
+ var maxValue = maxValues [i];
+ for (var j = 0; j < 100; ++j) {
+ var x = rng.Next (minValue, maxValue);
+ Assert.That (x, Is.GreaterThanOrEqualTo (minValue), "#C02a");
+ Assert.That (x, Is.LessThan (maxValue), "#C02b");
+ }
}
- for (int i = -1; i >= Int32.MinValue / 2; i *= 2) {
- long c = r.Next (i * 2, i);
- Assert.IsTrue (c < i, "At i=" + i + " c < i*2 failed");
- Assert.IsTrue (c >= i * 2, "At i=" + i + " c >= i failed");
- }
}
-/* Mono implementation is now compatible with Knuth (not MS) implementation (choice of constants)
[Test]
- public void CompareWithMS ()
+ [ExpectedException("System.ArgumentOutOfRangeException", UserMessage = "#C03")]
+ public void NextMinMax3 ()
{
- string[] r = new string [4];
- byte[] buffer = new byte [8];
- int x = 4;
- while (x-- > 0) {
- int seed = (x << x);
- Random random = new Random (seed);
- random.NextBytes (buffer);
- r [x] = BitConverter.ToString (buffer);
- }
- Assert.AreEqual ("43-DB-8B-AE-0A-88-A8-7B", r [3], "Seed(24)");
- Assert.AreEqual ("E7-2A-5C-44-D1-8C-7D-74", r [2], "Seed(8)");
- Assert.AreEqual ("C5-67-2A-FC-1B-4E-CD-72", r [1], "Seed(2)");
- Assert.AreEqual ("B9-D1-C4-8E-34-8F-E7-71", r [0], "Seed(0)");
- }*/
+ var rng = new Random (0);
+ rng.Next (11, 10);
+ }
+#endregion
+
+#region NextBytes (byte [])
+ [Test]
+ public void NextBytes1 ()
+ {
+ var rng = new Random (-1);
+
+ byte [] expected = { 14, 60, 162, 239, 174, 63, 177, 36, 5, 77, 179, 78, 253, 128, 254, 157, 131, 141, 26 };
+ byte [] values = new byte [expected.Length];
+
+ rng.NextBytes (values);
+ Assert.That (values, Is.EqualTo (expected), "#D01");
+ }
+
+ [Test]
+ [ExpectedException("System.ArgumentNullException", UserMessage = "#D02")]
+ public void NextBytes2 ()
+ {
+ var rng = new Random (-1);
+ rng.NextBytes (null);
+ }
+#endregion
+
+#region NextDouble ()
+ [Test]
+ public void NextDouble1 ()
+ {
+ double [] expected = { 0.62703955499455332756042480468750, 0.43585611786693334579467773437500,
+ 0.00747404294088482856750488281250, 0.97855615220032632350921630859375,
+ 0.13706348417326807975769042968750, 0.17940403497777879238128662109375,
+ 0.03021745034493505954742431640625, 0.33683855179697275161743164062500,
+ 0.78229111549444496631622314453125, 0.57975448970682919025421142578125,
+ 0.39323804969899356365203857421875, 0.64694489864632487297058105468750,
+ 0.28731191088445484638214111328125, 0.96053174138069152832031250000000,
+ 0.41580265713855624198913574218750, 0.58745257114060223102569580078125,
+ 0.29665753315202891826629638671875, 0.98642698233015835285186767578125,
+ 0.71415337035432457923889160156250, 0.76171694230288267135620117187500 };
+ var rng = new Random (0);
+ foreach (var e in expected)
+ Assert.That(rng.NextDouble(), Is.EqualTo(e).Within(1e-28));
+ }
+#endregion
}
}
More information about the Mono-devel-list
mailing list