Click here to Skip to main content
16,019,976 members
Articles / Programming Languages / C#
Article

A fast equivalent for System.Random

Rate me:
Please Sign up or sign in to vote.
4.88/5 (28 votes)
10 Oct 20067 min read 250.4K   3.5K   61   42
A simple and fast random number generator that can be substituted in place of System.Random, with extra methods and fast re-initialization.

Introduction

Here I present a class that can be substituted in place for the the .NET framework's System.Random class to provide some advantages:

  1. 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.
  2. Faster than System.Random. Up to 8x faster, depending on which methods are called and which CLR is used (see table below).
  3. 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 System.Random.
  4. 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 (int).

Background

I created 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. FastRandom's 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 Math

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:

C#
public uint NextUInt() 
{
   uint t= (x^(x<<11)); 
   x=y;
   y=z; 
   z=w;
   return (w= (w^(w>>19))^(t^(t>>8)));
}

The state of the RNG is described by the four uint variables x, y, z and w. w represents most recently generated number, and a history of the last four generated numbers is maintained with the inclusion of the x, y and 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 double, int, bytes, etc.

Reinitialise() methods

The 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 Next() and NextBytes(byte[]).
  • Where floating point arithmetic is used, ensure that casts are performed from int to double, and not from uint to double. In tests, casting from uint took twice as long as casting from int. This speed-up applies to NextDouble(), Next(int) and Next(int,int).
  • 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.

Other notes:

  • Both FastRandom and 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)

Speed increase

Next()

103.252

220.750

2.14x
Next(int)

51.826

142.2472.14x
Next(int,int)

34.506

87.6802.54x
Next(int,int) <long range>*

16.182

30.2611.87x
NextDouble()

87.680

185.5282.12x
NextBytes() 1024 byte array in tests

0.105

0.9278.83x
NextUInt()

n/a

261.437n/a
NextInt()

n/a

256.081n/a
NextBool()

n/a

312.500n/a

* - 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 System.Random. NextUint() is provided because uint is the underlying data type behind FastRandom and so is very fast to generate. NextInt() returns an int (Int32<?CODE>) but unlike Next() the range is between 0 and int.MaxValue instead of between 0 and 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.

Conclusion

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
United Kingdom United Kingdom
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionNon random results Pin
Member 1074189211-Apr-14 1:50
Member 1074189211-Apr-14 1:50 
QuestionUse 64-bit shifts... and test against ThreadLocalRandom Pin
Sebastiano Vigna3-Apr-14 23:15
Sebastiano Vigna3-Apr-14 23:15 
AnswerRe: Use 64-bit shifts... and test against ThreadLocalRandom Pin
Petoj8728-Jun-15 20:40
Petoj8728-Jun-15 20:40 
BugI think there is a bug in Reinitialise() Pin
browseria5-Nov-12 9:31
browseria5-Nov-12 9:31 
GeneralRe: I think there is a bug in Reinitialise() Pin
colgreen5-Nov-12 11:16
colgreen5-Nov-12 11:16 
QuestionOptimization for safe code Pin
Thomas Happ21-Sep-11 17:02
Thomas Happ21-Sep-11 17:02 
QuestionRandom Float Pin
mcunha9827-Mar-09 4:00
mcunha9827-Mar-09 4:00 
GeneralSpeed test Pin
adamdyvig26-Oct-08 9:50
adamdyvig26-Oct-08 9:50 
GeneralRe: Speed test Pin
colgreen28-Dec-08 12:47
colgreen28-Dec-08 12:47 
GeneralThanks! Pin
Corinna John30-Mar-08 8:16
Corinna John30-Mar-08 8:16 
GeneralMinor "error" and improvement Pin
Stefan Troschuetz15-Aug-06 0:07
Stefan Troschuetz15-Aug-06 0:07 
GeneralRe: Minor &quot;error&quot; and improvement Pin
colgreen22-Sep-06 14:18
colgreen22-Sep-06 14:18 
GeneralRe: Minor &quot;error&quot; and improvement Pin
Stefan Troschuetz22-Sep-06 22:09
Stefan Troschuetz22-Sep-06 22:09 
Generaloptimization Pin
System.Object19-Jul-06 3:54
System.Object19-Jul-06 3:54 
GeneralCode Reuse Pin
jnorman18-Apr-06 6:22
jnorman18-Apr-06 6:22 
GeneralRe: Code Reuse Pin
colgreen18-Apr-06 8:49
colgreen18-Apr-06 8:49 
QuestionRe: Code Reuse Pin
Rohit Dubey from Hyderabad24-Apr-12 5:36
Rohit Dubey from Hyderabad24-Apr-12 5:36 
GeneralReinitialise not deterministic Pin
gosub3-Sep-05 6:25
gosub3-Sep-05 6:25 
GeneralRe: Reinitialise not deterministic Pin
colgreen4-Sep-05 11:14
colgreen4-Sep-05 11:14 
GeneralUnsafe implementation of NextBytes Pin
Rei Miyasaka8-Jun-05 15:44
Rei Miyasaka8-Jun-05 15:44 
GeneralRe: Unsafe implementation of NextBytes Pin
colgreen9-Jun-05 13:09
colgreen9-Jun-05 13:09 
GeneralRe: Unsafe implementation of NextBytes Pin
Rei Miyasaka9-Jun-05 19:35
Rei Miyasaka9-Jun-05 19:35 
GeneralRe: Unsafe implementation of NextBytes Pin
D11112-Jun-06 8:06
D11112-Jun-06 8:06 
GeneralRe: Unsafe implementation of NextBytes Pin
Rei Miyasaka12-Jun-06 9:00
Rei Miyasaka12-Jun-06 9:00 
GeneralPLEASE NOTE - Updated Algorithm! Pin
colgreen6-Jan-05 22:26
colgreen6-Jan-05 22:26 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.