Reader Level:
Articles

Random isn't Really Random -- C# Random Number Generation

By Matthew Cochran on July 18, 2006
This article covers overriding the System.Random object in order to produce better random numbers. The project file contains a library of eight commonly used random number generating algorithms, the best of which is the Mersenne Twister algorithm.
  • 0
  • 0
  • 108950
Download Files:
 

Part I. Overriding System.Random

First we need a base class for overriding System.Random.  We will call it RandomBase and it will be used to cover all the methods implemented by System.Random.  We'll only be leaving the Next() method unimplemented but as abstract so the parent classes can implement the method differently for each algorithm.  Everything else will be the same.

There are a few utility functions for type conversion included and we'll expose the base class random number generator for the cases when we'll need it.

public abstract class RandomBase: Random

{

    #region Constructors

 

    public RandomBase() { }

 

    public RandomBase(int seed) : base(seed) { }

 

    #endregion

 

    #region Methods

 

    protected int GetBaseNextInt32()

    {

        return base.Next();

    }

 

    protected uint GetBaseNextUInt32()

    {

        return ConvertToUInt32(base.Next());

    }

 

    protected double GetBaseNextDouble()

    {

        return base.NextDouble();

    }

 

    #endregion

 

    #region Overrides

 

    public abstract override int Next();

 

    public override int Next(int maxValue)

    {

        return Next(0, maxValue);

    }

 

    public override int Next(int minValue, int maxValue)

    {

        return Convert.ToInt32((maxValue - minValue) * Sample() + minValue);

    }

 

    public override double NextDouble()

    {

        return Sample();

    }

 

    public override void NextBytes(byte[] buffer)

    {

        int i, j, tmp;

 

        // fill the part of the buffer that can be covered by full Int32s

        for (i = 0; i < buffer.Length - 4; i += 4)

        {

            tmp = Next();

 

            buffer[i] = Convert.ToByte(tmp & 0x000000FF);

            buffer[i + 1] = Convert.ToByte((tmp & 0x0000FF00) >> 8);

            buffer[i + 2] = Convert.ToByte((tmp & 0x00FF0000) >> 16);

            buffer[i + 3] = Convert.ToByte((tmp & 0xFF000000) >> 24);

        }

 

        tmp = Next();

 

        // fill the rest of the buffer

        for (j = 0; j < buffer.Length % 4; j++)

        {

            buffer[i + j] = Convert.ToByte(((tmp & (0x000000FF << (8 * j))) >> (8 * j)));

        }

    }

 

    protected override double Sample()

    {

 

        // generates a random number on [0,1)

        return Convert.ToDouble(Next()) / 2147483648.0; // divided by 2^31 (Int32 absolute value)

    }

 

    #endregion 

   

    #region Utility Methods

 

    protected static UInt32 ConvertToUInt32(Int32 value)

    {

        return BitConverter.ToUInt32(BitConverter.GetBytes(value), 0);

 

    }

 

    protected static Int32 ConvertToInt32(UInt32 value)

    {

        return BitConverter.ToInt32(BitConverter.GetBytes(value), 0);

 

    }

 

    protected static Int32 ConvertToInt32(UInt64 value)

    {

        return BitConverter.ToInt32(BitConverter.GetBytes(value & 0x000000007fffffff) , 0);

 

    }

 

    #endregion

}

 

Part II: Implementing an algorithm.

 

The algorithms are pretty standard and I found implementations for the algorithms used in this article from these two sources: 

To implement we just have to put together the constructors and implement the Next() method as in the Quick class below.  I had to modify each algorithm slightly to take advantage of the inheritance in place and work out some small bugs that popped up.

 

public class Quick : RandomBase

{

    #region Constructors

 

    public Quick() : this(Convert.ToInt32(DateTime.Now.Ticks & 0x000000007FFFFFFF)) { }

 

    public Quick(int seed)

        : base(seed)

    {

        i = Convert.ToUInt64(GetBaseNextInt32());

    }

 

    #endregion

 

    #region Member Variables

 

    private static readonly uint a = 1099087573;

 

    private ulong i;

 

    #endregion

 

    #region Methods

 

    public override int Next()

    {

        #region Execution

 

        i = a * i; // overflow occurs here!

        return ConvertToInt32(i);

 

        #endregion

 

    }

 

    #endregion

}

 

Part III. Executing the Algorithms

 

The beauty of this approach is that we can treat each algorithm implementations as if it were a System.Random object.

 

Step 1: Declare the Variable:

 

private Random m_quick;

 

Step 2: Initialize:

 

m_quick = new RandomNumberGeneration.Quick();

 

Step 3: Execute (just as if it were a System.Random object)

 

m_quick.NextDouble();

 

Hopefully you'll find the project library useful.

 

Until next time,

Happy Coding

COMMENT USING

Trending up