Click here to Skip to main content
Click here to Skip to main content
Go to top

A fast equivalent for System.Random

, 10 Oct 2006
Rate this:
Please Sign up or sign in to vote.
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:

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.247 2.14x
Next(int,int)

34.506

87.680 2.54x
Next(int,int) <long range>*

16.182

30.261 1.87x
NextDouble()

87.680

185.528 2.12x
NextBytes() 1024 byte array in tests

0.105

0.927 8.83x
NextUInt()

n/a

261.437 n/a
NextInt()

n/a

256.081 n/a
NextBool()

n/a

312.500 n/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

Share

About the Author

colgreen
Web Developer
United Kingdom United Kingdom
No Biography provided

Comments and Discussions

 
QuestionNon random results PinmemberMember 1074189211-Apr-14 1:50 
QuestionUse 64-bit shifts... and test against ThreadLocalRandom PinmemberSebastiano Vigna3-Apr-14 23:15 
BugI think there is a bug in Reinitialise() Pinmemberbrowseria5-Nov-12 9:31 
GeneralRe: I think there is a bug in Reinitialise() Pinmembercolgreen5-Nov-12 11:16 
QuestionOptimization for safe code PinmemberThomas Happ21-Sep-11 17:02 
QuestionRandom Float Pinmembermcunha9827-Mar-09 4:00 
GeneralSpeed test Pinmemberadamdyvig26-Oct-08 9:50 
GeneralRe: Speed test Pinmembercolgreen28-Dec-08 12:47 
GeneralThanks! PinmemberCorinna John30-Mar-08 8:16 
GeneralMinor "error" and improvement PinmemberStefan Troschütz15-Aug-06 0:07 
GeneralRe: Minor &quot;error&quot; and improvement Pinmembercolgreen22-Sep-06 14:18 
GeneralRe: Minor &quot;error&quot; and improvement PinmemberStefan Troschütz22-Sep-06 22:09 
Generaloptimization PinmemberSystem.Object19-Jul-06 3:54 
GeneralCode Reuse Pinmemberjnorman18-Apr-06 6:22 
GeneralRe: Code Reuse Pinmembercolgreen18-Apr-06 8:49 
QuestionRe: Code Reuse PinmemberRohit Dubey from Hyderabad24-Apr-12 5:36 
GeneralReinitialise not deterministic Pinmembergosub3-Sep-05 6:25 
GeneralRe: Reinitialise not deterministic Pinmembercolgreen4-Sep-05 11:14 
GeneralUnsafe implementation of NextBytes Pinmemberreinux8-Jun-05 15:44 
GeneralRe: Unsafe implementation of NextBytes Pinmembercolgreen9-Jun-05 13:09 
GeneralRe: Unsafe implementation of NextBytes Pinmemberreinux9-Jun-05 19:35 
GeneralRe: Unsafe implementation of NextBytes PinmemberD11112-Jun-06 8:06 
GeneralRe: Unsafe implementation of NextBytes Pinmemberreinux12-Jun-06 9:00 
GeneralPLEASE NOTE - Updated Algorithm! Pinmembercolgreen6-Jan-05 22:26 
GeneralRe: PLEASE NOTE - Updated Algorithm! PinmemberJeffrey Sax7-Jan-05 3:17 
GeneralRe: PLEASE NOTE - Updated Algorithm! Pinmembercolgreen7-Jan-05 8:26 
GeneralWhy not use a standard algorithm PinmemberUrs Enzler5-Jan-05 4:33 
GeneralRe: Why not use a standard algorithm Pinmembercolgreen5-Jan-05 10:15 
GeneralRe: Why not use a standard algorithm PinmemberJens Scheidtmann7-Jan-05 0:25 
GeneralRe: Why not use a standard algorithm Pinmembercolgreen7-Jan-05 0:39 
GeneralRe: Why not use a standard algorithm PinmemberJeffrey Sax7-Jan-05 3:09 
GeneralRe: Why not use a standard algorithm PinmemberUrs Enzler7-Jan-05 3:25 
GeneralEven faster PinmemberJeffrey Sax31-Dec-04 10:34 
GeneralRe: Even faster Pinmembercolgreen1-Jan-05 0:24 
GeneralFast - but not very random PinmemberJabes31-Dec-04 3:58 
GeneralRe: Fast - but not very random PinmemberJeffrey Sax31-Dec-04 10:26 
GeneralRe: Fast - but not very random Pinmembercolgreen1-Jan-05 0:31 
GeneralRe: Fast - but not very random PinmemberJabes7-Jan-05 0:58 
GeneralRe: Fast - but not very random Pinmemberaxelriet9-Sep-05 16:57 
GeneralRe: Fast - but not very random Pinmembercargo.dk18-Nov-06 7:34 
GeneralRe: Fast - but not very random PinmemberVandretta15-Jun-07 20:26 

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

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

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 10 Oct 2006
Article Copyright 2004 by colgreen
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid