Here I present a class that can be substituted in place for the the .NET framework's
System.Random class to provide some advantages:
- Based on a simple and fast XOR-shift pseudo random number generator (RNG) specified in the paper: Marsaglia, George. (2003). Xorshift RNGs). This particular implementation of XOR-shift has a period of 2^128-1. See the above paper to see how this can be easily extended if you need a longer period. At the time of writing, I could find no information on the period of
System.Random for comparison.
- Faster than
System.Random. Up to 8x faster, depending on which methods are called and which CLR is used (see table below).
- Direct replacement for
System.Random. This class implements all of the methods that
System.Random does plus some additional methods for generating random
uints and booleans. The like named methods are functionally equivalent to those in
- Allows fast re-initialization with a seed, unlike
System.Random which accepts a seed at construction time only, which then executes a relatively expensive initialization routine. This provides a vast speed improvement if you need to reset the pseudo-random number sequence many times, e.g., if you want to re-generate the same sequence many times. An alternative might be to cache random numbers in an array, but that approach is limited by memory capacity and the fact that you may also want a large number of different sequences cached. Each sequence can be represented by a single seed value (
FastRandom in order to achieve greater speed in a prey capture simulation within another project, SharpNEAT. That simulation requires that the RNG be reset with a given seed 1000s of times per second.
Reinitialise() methods, therefore, provide a nice performance boost over
System.Random in that case. I then discovered that a number of further performance improvements could be made to the
Next*() methods. The first version of
FastRandom posted on CodeProject used a multiply-with-carry (MWC) algorithm devised by George Marsaglia. Forum posters pointed out that some seeds generated a sequence of the same number, and whilst investigating the solution, I came across another of Marsaglia's algorithms utilizing an XOR-shift technique that was even faster than MWC. The current version of
FastRandom therefore implements XOR-shift and should also provide good random sequences for all seed values (including 0).
The random number generator (RNG) used generates new numbers using just bitwise XOR and left and right shifts. The method
NextUInt provides the simplest example because it returns the generated 32 bit number (
uint) without any further manipulation:
public uint NextUInt()
uint t= (x^(x<<11));
return (w= (w^(w>>19))^(t^(t>>8)));
The state of the RNG is described by the four
w represents most recently generated number, and a history of the last four generated numbers is maintained with the inclusion of the
z variables. New numbers are generated by applying various shifts and XORs to
x, which represents the number generated four calls ago. Storing and using the history of the last four numbers in this manner results in an RNG with a longer period, here the period is 2^128-1. The period can be shortened or lengthened by adjusting the amount of history variables stored. For more information on this, see the paper referred to above.
All of the other
Next*() methods are variations of this technique, taking the 32 bits generated and manipulating them into
Reinitialise methods allow the caller to reset
FastRandom with a single integer seed value and thus generate the same set of random numbers over again. This can sometimes be useful, e.g., in simulations where you might want to recreate the same scenario exactly as before. Note that
System.Random provides no such method for re-initializing (re-seeding) the class once it is constructed; the only option is to construct a new instance and pass the seed in to the constructor, which then executes code to build an array of seed data. By allowing re-initialization and avoiding the need to build a seed data array,
FastRandom provides a significant performance improvement where reseeding is required.
Other Performance Improvements (in comparison to System.Random)
- Avoid use of floating point arithmetic where possible. This applies to
- Where floating point arithmetic is used, ensure that casts are performed from
double, and not from
double. In tests, casting from
uint took twice as long as casting from
int. This speed-up applies to
- Don't declare methods as
virtual. The virtual method table generates some overhead even in released, optimized code where the methods haven't actually been overridden.
System.Random's methods are declared as
virtual and therefore generate this overhead. There may be sound reasons for this within the .NET framework, but if you just want a fast RNG today, then we can omit the
virtual keyword in our declarations.
- In the
NextBytes method, we generate 32 bits at a time and fill the byte array in 4 byte chunks.
Performance Comparison Table
For prior readers of this article please note that this is an updated version of the table that takes into account improvements made to FastRandom.cs made since the article was first posted and also to the .NET runtime engine between .NET 1.1 and .NET 2.0.
System.Random run faster on the .NET 2.0 CLR than on .NET 1.1. However,
System.Random does benefit more than
FastRandom and so the performance gap between the two classes is narrower in .NET 2.0.
- One exception to the above point is
Next(int,int) with a long range between the two integer parameters, on the .Net 1.1 CLR FastRandom's version actually ran slower, however on .NET 2.0 this result is now reversed as can be seen in the table below.
The following performance figures were obtained using released, optimized code executing on an Intel Core 2 Duo E660 overclocked to 3.11Ghz. This is a dual core chip, however these performance figures are for a single core only:
System.Random (millions calls/sec)
FastRandom (millions calls/sec)
Next(int,int) <long range>*
NextBytes() 1024 byte array in tests
* - An alternative execution path occurs when the range between the lower and upper limits will not fit within an
int. This results in a different performance figure.
Note the last three methods which are extra methods not present on
NextUint() is provided because
uint is the underlying data type behind
FastRandom and so is very fast to generate.
NextInt() returns an
Int32<?CODE>) but unlike
Next() the range is between
int.MaxValue instead of between
int.MaxValue-1. This subtle difference allows an optimization to be made (elimination of an 'if' statement).
NextBool() is implemented by generating 32 bits (
uint) and buffering them for future calls, hence the high speed.
System.Random is actually very fast and achieves its speed mostly by only using simple and fast arithmetic operations such as shift and add. However, the whole class is based around a central
Sample() method that returns a
double between 0.0 and 1.0, and thus there is some unnecessary floating point arithmetic used to generate integer values.
FastRandom utilizes a completely different algorithm for generating random numbers that is inherently slightly faster, and in
FastRandom we provide a further boost by avoiding floating point arithmetic wherever possible and implementing some further refinements. Finally,
FastRandom also allows for fast re-seeding which allows repeat random number sequences to be re-generated very quickly.