User's Guide

Up: Random Numbers Next: Quasi-Random Sequences Previous: Random Numbers Contents

Random Number Generators

So-called random number generators (RNG's) produce sequences of numbers that, for the purposes of the user, appear to be random. The Etreme Optimizatoin Statistics Library for .NET contains a number of different random number generators, which vary in speed and quality.

The ExtendedRandom Class

The .NET framework already contains a random number generator. It is based on an algorithm from Donald Knuth's The Art of Computer Programming. For several reasons, this generator is not ideal. It scores badly on some tests of randomness and has a serious bias in the least significant bit. Nevertheless, the System.Random class defines a number of methods that are the accepted standard in the .NET framework.

The ExtendedRandom class extends System.Random by supplying a number of new methods for generating sequences of random numbers, and for generating random numbers from any statistical distribution. ExtendedRandom is the base class for all random number generators in the Etreme Optimizatoin Statistics Library for .NET.

The ExtendedRandom class provides additional overloads for the Next method, which returns a random variate from a discrete distribution, and the NextDouble method, which returns a random variate from a continuous distribution.

The ExtendedRandom class defines a Fill method which fills existing arrays and Vector objects with a sequence of random numbers. Overloads of the Fill method correspond to overloads of the Next and NextDouble methods, with an extra argument that specifies the object that is to recieve the random numbers.

All random number generators can be serialized. This means that their current state can be saved. When their state is restored at a later time, the random sequence can be continued from the point where it was saved.

The RANLUX Generator

The RANLUX suite of random number generators was developed by M. Luescher in 1994. It generates 24 bit pseudo-random numbers. To reduce correlation between successive values, a number of generated random numbers is skipped occasionaly. The period of is roughly 10¹⁷¹.

The RANLUX suite is a prime example of the trade-off between quality and speed. Depending on the luxury level, the random numbers are from pretty good to perfect. The highest luxury level (3) produces 24 bit numbers which are proven to be totally random. This randomness comes at a cost: the best generator is about 3 times slower than the least good.

The RANLUX generators are implemented by the Ranlux class. The luxury level is defined by the RanluxLuxuryLevel enumeration. It can take on the following values:

Value	Description
Default	The fastest algorithm with some correlation between random values.
Better	A medium-speed algorithm with reduced correlation between random values.
Best	A slower algorithm without any correlation between random values.

The RanLux class has four constructors. The first constructor has no arguments. It uses the default (fastest) luxury level, and uses a time-based seed. The second constructor has one parameter: a RanluxLuxuryLevel that specifies the luxury level. The third constructor takes one integer parameter that is the initial seed value. The fourth constructor takes an integer seed and a RanluxLuxuryLevel value. The following code snippet illustrates these constructors:

C#	Copy Code
RanLux ranLux1 = new RanLux(); RanLux ranLux2 = new RanLux(99); RanLux ranLux3 = new RanLux(RanLuxLuxuryLevel.Better); RanLux ranLux4 = new RanLux(99, RanLuxLuxuryLevel.Best);

Visual Basic	Copy Code
Dim ranLux1 As RanLux = New RanLux Dim ranLux2 As RanLux = New RanLux(99) Dim ranLux3 As RanLux = New RanLux(RanLuxLuxuryLevel.Better) Dim ranLux4 As RanLux = New RanLux(99, RanLuxLuxuryLevel.Best)

The Generalized Feedback Shift Register Generator

A Generalized Feedback Shift Register (GFSR) pseudo-random number generator combines 4 values from a long sequence of registers to produce each new 32 bit random number. Our implementation uses the values proposed by the generator's developer Robert Ziff. It has a very long period of about 10²⁹¹⁷.

Initialization time for this type of generator is relatively long. Generation of actual random numbers is very fast.

The generalized feedback shift register pseudo-random number generator is implemented by the GfsrGenerator class. It has three constructors. The first constructor has no parameters. The second constructor takes one integer seed value. The third constructor takes an array of integers containing the seed values. The maximum length of this array is 16383.

C#	Copy Code
GfsrGenerator gfsr1 = new GfsrGenerator(); GfsrGenerator gfsr2 = new GfsrGenerator(99); GfsrGenerator gfsr3 = new GfsrGenerator(new int[] {99, 17, int.MaxValue});

Visual Basic	Copy Code
Dim gfsr1 As GfsrGenerator = New GfsrGenerator Dim gfsr2 As GfsrGenerator = New GfsrGenerator(99) Dim gfsr3 As GfsrGenerator = _ New GfsrGenerator(New Integer() {99, 17, Integer.MaxValue})

The Mersenne Twister

The Mersenne Twister is a random number generator with an extremely long period - 2¹⁹⁹³⁷, or roughly 1 followed by 6,000 zeroes. It is relatively fast, and has good randomness properties. It is a variation on a generalized feedback shift register generator. It is of excellent quality and is comparable to other generators in speed.

The Mersenne Twister is implemented by the MersenneTwister class. It has three constructors. The first constructor has no parameters. The second constructor takes one integer seed value. The third constructor takes an array of integers containing the seed values. The maximum length of this array is 623.

C#	Copy Code
MersenneTwister mersenne1 = new MersenneTwister(); MersenneTwister mersenne2 = new MersenneTwister(99); MersenneTwister mersenne3 = new MersenneTwister(new int[] {99, 17, int.MaxValue});

Visual Basic	Copy Code
Dim mersenne1 As MersenneTwister = New MersenneTwister Dim mersenne2 As MersenneTwister = New MersenneTwister(99) Dim mersenne3 As MersenneTwister = _ New MersenneTwister(New Integer() {99, 17, Integer.MaxValue})

Visual Basic

Copy Code

Dim mersenne1 As MersenneTwister = New MersenneTwister
Dim mersenne2 As MersenneTwister = New MersenneTwister(99)
Dim mersenne3 As MersenneTwister = _
    New MersenneTwister(New Integer() {99, 17, Integer.MaxValue})

Choosing a Random Number Generator

No random number generator is perfect for every application. In fact, with the increase in computing power in recent decades have come an increasing number of failures of random number generators that were thought to be well-behaved. The application itself has become the testing ground for the quality of pseudo-random numbers.

We recommend testing your application with at least two different random number generators. If the results are significantly different, then at least one of the generators is not suitable. If the results are similar, you may wish to choose the faster of the two.

To help you make this decision, the table below lists the number of integer and double random numbers per second produced by each of the available pseudo-random number generators. The test machine was a 3GHz Pentium IV, and the unit is millions of random numbers per second.

Generator	Integers/s	Doubles/s
System.Random	26.9	44.5
MersenneTwister	36.7	13.0
RanLux (default)	7.6	8.0
RanLux (better)	5.0	5.2
RanLux (best)	2.8	2.9
GsfrGenerator	49.5	16.3

References

Donald E. Knuth, The Art of Computer Programming: Seminumerical Algorithms (Vol 2, 3rd Ed, 1997), Addison-Wesley.

M. Lscher, "A portable high-quality random number generator for lattice field theory calculations", Computer Physics Communications, 79 (1994) 100-110.

Makoto Matsumoto and Takuji Nishimura, "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator". ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1 (Jan. 1998), Pages 3-30

Robert M. Ziff, "Four-tap shift-register-sequence random-number generators", Computers in Physics, 12(4), Jul/Aug 1998, pp 385-392.