1  using System;


2  using HeuristicLab.Core;


3  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


4 


5  namespace HeuristicLab.Random {


6  /// <summary>


7  /// A fast random number generator for .NET


8  /// Colin Green, January 2005


9  ///


10  /// September 4th 2005


11  /// Added NextBytesUnsafe()  commented out by default.


12  /// Fixed bug in Reinitialise()  y,z and w variables were not being reset.


13  ///


14  /// Key points:


15  /// 1) Based on a simple and fast xorshift pseudo random number generator (RNG) specified in:


16  /// Marsaglia, George. (2003). Xorshift RNGs.


17  /// http://www.jstatsoft.org/v08/i14/xorshift.pdf


18  ///


19  /// This particular implementation of xorshift has a period of 2^1281. See the above paper to see


20  /// how this can be easily extened if you need a longer period. At the time of writing I could find no


21  /// information on the period of System.Random for comparison.


22  ///


23  /// 2) Faster than System.Random. Up to 8x faster, depending on which methods are called.


24  ///


25  /// 3) Direct replacement for System.Random. This class implements all of the methods that System.Random


26  /// does plus some additional methods. The like named methods are functionally equivalent.


27  ///


28  /// 4) Allows fast reinitialisation with a seed, unlike System.Random which accepts a seed at construction


29  /// time which then executes a relatively expensive initialisation routine. This provides a vast speed improvement


30  /// if you need to reset the pseudorandom number sequence many times, e.g. if you want to regenerate the same


31  /// sequence many times. An alternative might be to cache random numbers in an array, but that approach is limited


32  /// by memory capacity and the fact that you may also want a large number of different sequences cached. Each sequence


33  /// can each be represented by a single seed value (int) when using FastRandom.


34  ///


35  /// Notes.


36  /// A further performance improvement can be obtained by declaring local variables as static, thus avoiding


37  /// reallocation of variables on each call. However care should be taken if multiple instances of


38  /// FastRandom are in use or if being used in a multithreaded environment.


39  ///


40  /// August 2010:


41  /// adapted for HeuristicLab by gkronber (cloning, persistence, IRandom interface)


42  ///


43  /// </summary>


44  [StorableClass]


45  public class FastRandom : Item, IRandom {


46  // The +1 ensures NextDouble doesn't generate 1.0


47  private const double REAL_UNIT_INT = 1.0 / ((double)int.MaxValue + 1.0);


48  private const double REAL_UNIT_UINT = 1.0 / ((double)uint.MaxValue + 1.0);


49  private const uint Y = 842502087, Z = 3579807591, W = 273326509;


50 


51  [Storable]


52  private uint x, y, z, w;


53 


54  #region Constructors


55 


56  /// <summary>


57  /// Initialises a new instance using time dependent seed.


58  /// </summary>


59  public FastRandom() {


60  // Initialise using the system tick count.


61  Reinitialise((int)Environment.TickCount);


62  }


63 


64  /// <summary>


65  /// Initialises a new instance using an int value as seed.


66  /// This constructor signature is provided to maintain compatibility with


67  /// System.Random


68  /// </summary>


69  public FastRandom(int seed) {


70  Reinitialise(seed);


71  }


72 


73  #endregion


74 


75  #region Public Methods [Reinitialisation]


76 


77  /// <summary>


78  /// Reinitialises using an int value as a seed.


79  /// </summary>


80  /// <param name="seed"></param>


81  public void Reinitialise(int seed) {


82  // The only stipulation stated for the xorshift RNG is that at least one of


83  // the seeds x,y,z,w is nonzero. We fulfill that requirement by only allowing


84  // resetting of the x seed


85  x = (uint)seed;


86  y = Y;


87  z = Z;


88  w = W;


89  }


90 


91  #endregion


92 


93  #region Public Methods [System.Random functionally equivalent methods]


94 


95  /// <summary>


96  /// Generates a random int over the range 0 to int.MaxValue1.


97  /// MaxValue is not generated in order to remain functionally equivalent to System.Random.Next().


98  /// This does slightly eat into some of the performance gain over System.Random, but not much.


99  /// For better performance see:


100  ///


101  /// Call NextInt() for an int over the range 0 to int.MaxValue.


102  ///


103  /// Call NextUInt() and cast the result to an int to generate an int over the full Int32 value range


104  /// including negative values.


105  /// </summary>


106  /// <returns></returns>


107  public int Next() {


108  uint t = (x ^ (x << 11));


109  x = y; y = z; z = w;


110  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));


111 


112  // Handle the special case where the value int.MaxValue is generated. This is outside of


113  // the range of permitted values, so we therefore call Next() to try again.


114  uint rtn = w & 0x7FFFFFFF;


115  if (rtn == 0x7FFFFFFF)


116  return Next();


117  return (int)rtn;


118  }


119 


120  /// <summary>


121  /// Generates a random int over the range 0 to upperBound1, and not including upperBound.


122  /// </summary>


123  /// <param name="upperBound"></param>


124  /// <returns></returns>


125  public int Next(int upperBound) {


126  if (upperBound < 0)


127  throw new ArgumentOutOfRangeException("upperBound", upperBound, "upperBound must be >=0");


128 


129  uint t = (x ^ (x << 11));


130  x = y; y = z; z = w;


131 


132  // The explicit int cast before the first multiplication gives better performance.


133  // See comments in NextDouble.


134  return (int)((REAL_UNIT_INT * (int)(0x7FFFFFFF & (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))))) * upperBound);


135  }


136 


137  /// <summary>


138  /// Generates a random int over the range lowerBound to upperBound1, and not including upperBound.


139  /// upperBound must be >= lowerBound. lowerBound may be negative.


140  /// </summary>


141  /// <param name="lowerBound"></param>


142  /// <param name="upperBound"></param>


143  /// <returns></returns>


144  public int Next(int lowerBound, int upperBound) {


145  if (lowerBound > upperBound)


146  throw new ArgumentOutOfRangeException("upperBound", upperBound, "upperBound must be >=lowerBound");


147 


148  uint t = (x ^ (x << 11));


149  x = y; y = z; z = w;


150 


151  // The explicit int cast before the first multiplication gives better performance.


152  // See comments in NextDouble.


153  int range = upperBound  lowerBound;


154  if (range < 0) { // If range is <0 then an overflow has occured and must resort to using long integer arithmetic instead (slower).


155  // We also must use all 32 bits of precision, instead of the normal 31, which again is slower.


156  return lowerBound + (int)((REAL_UNIT_UINT * (double)(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)))) * (double)((long)upperBound  (long)lowerBound));


157  }


158 


159  // 31 bits of precision will suffice if range<=int.MaxValue. This allows us to cast to an int and gain


160  // a little more performance.


161  return lowerBound + (int)((REAL_UNIT_INT * (double)(int)(0x7FFFFFFF & (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))))) * (double)range);


162  }


163 


164  /// <summary>


165  /// Generates a random double. Values returned are from 0.0 up to but not including 1.0.


166  /// </summary>


167  /// <returns></returns>


168  public double NextDouble() {


169  uint t = (x ^ (x << 11));


170  x = y; y = z; z = w;


171 


172  // Here we can gain a 2x speed improvement by generating a value that can be cast to


173  // an int instead of the more easily available uint. If we then explicitly cast to an


174  // int the compiler will then cast the int to a double to perform the multiplication,


175  // this final cast is a lot faster than casting from a uint to a double. The extra cast


176  // to an int is very fast (the allocated bits remain the same) and so the overall effect


177  // of the extra cast is a significant performance improvement.


178  //


179  // Also note that the loss of one bit of precision is equivalent to what occurs within


180  // System.Random.


181  return (REAL_UNIT_INT * (int)(0x7FFFFFFF & (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)))));


182  }


183 


184 


185  /// <summary>


186  /// Fills the provided byte array with random bytes.


187  /// This method is functionally equivalent to System.Random.NextBytes().


188  /// </summary>


189  /// <param name="buffer"></param>


190  public void NextBytes(byte[] buffer) {


191  // Fill up the bulk of the buffer in chunks of 4 bytes at a time.


192  uint x = this.x, y = this.y, z = this.z, w = this.w;


193  int i = 0;


194  uint t;


195  for (int bound = buffer.Length  3; i < bound; ) {


196  // Generate 4 bytes.


197  // Increased performance is achieved by generating 4 random bytes per loop.


198  // Also note that no mask needs to be applied to zero out the higher order bytes before


199  // casting because the cast ignores thos bytes. Thanks to Stefan Trosch�tz for pointing this out.


200  t = (x ^ (x << 11));


201  x = y; y = z; z = w;


202  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));


203 


204  buffer[i++] = (byte)w;


205  buffer[i++] = (byte)(w >> 8);


206  buffer[i++] = (byte)(w >> 16);


207  buffer[i++] = (byte)(w >> 24);


208  }


209 


210  // Fill up any remaining bytes in the buffer.


211  if (i < buffer.Length) {


212  // Generate 4 bytes.


213  t = (x ^ (x << 11));


214  x = y; y = z; z = w;


215  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));


216 


217  buffer[i++] = (byte)w;


218  if (i < buffer.Length) {


219  buffer[i++] = (byte)(w >> 8);


220  if (i < buffer.Length) {


221  buffer[i++] = (byte)(w >> 16);


222  if (i < buffer.Length) {


223  buffer[i] = (byte)(w >> 24);


224  }


225  }


226  }


227  }


228  this.x = x; this.y = y; this.z = z; this.w = w;


229  }


230 


231 


232  // /// <summary>


233  // /// A version of NextBytes that uses a pointer to set 4 bytes of the byte buffer in one operation


234  // /// thus providing a nice speedup. The loop is also partially unrolled to allow outoforderexecution,


235  // /// this results in about a x2 speedup on an AMD Athlon. Thus performance may vary wildly on different CPUs


236  // /// depending on the number of execution units available.


237  // ///


238  // /// Another significant speedup is obtained by setting the 4 bytes by indexing pDWord (e.g. pDWord[i++]=w)


239  // /// instead of adjusting it dereferencing it (e.g. *pDWord++=w).


240  // ///


241  // /// Note that this routine requires the unsafe compilation flag to be specified and so is commented out by default.


242  // /// </summary>


243  // /// <param name="buffer"></param>


244  // public unsafe void NextBytesUnsafe(byte[] buffer)


245  // {


246  // if(buffer.Length % 8 != 0)


247  // throw new ArgumentException("Buffer length must be divisible by 8", "buffer");


248  //


249  // uint x=this.x, y=this.y, z=this.z, w=this.w;


250  //


251  // fixed(byte* pByte0 = buffer)


252  // {


253  // uint* pDWord = (uint*)pByte0;


254  // for(int i=0, len=buffer.Length>>2; i < len; i+=2)


255  // {


256  // uint t=(x^(x<<11));


257  // x=y; y=z; z=w;


258  // pDWord[i] = w = (w^(w>>19))^(t^(t>>8));


259  //


260  // t=(x^(x<<11));


261  // x=y; y=z; z=w;


262  // pDWord[i+1] = w = (w^(w>>19))^(t^(t>>8));


263  // }


264  // }


265  //


266  // this.x=x; this.y=y; this.z=z; this.w=w;


267  // }


268 


269  #endregion


270 


271  #region Public Methods [Methods not present on System.Random]


272 


273  /// <summary>


274  /// Generates a uint. Values returned are over the full range of a uint,


275  /// uint.MinValue to uint.MaxValue, inclusive.


276  ///


277  /// This is the fastest method for generating a single random number because the underlying


278  /// random number generator algorithm generates 32 random bits that can be cast directly to


279  /// a uint.


280  /// </summary>


281  /// <returns></returns>


282  public uint NextUInt() {


283  uint t = (x ^ (x << 11));


284  x = y; y = z; z = w;


285  return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));


286  }


287 


288  /// <summary>


289  /// Generates a random int over the range 0 to int.MaxValue, inclusive.


290  /// This method differs from Next() only in that the range is 0 to int.MaxValue


291  /// and not 0 to int.MaxValue1.


292  ///


293  /// The slight difference in range means this method is slightly faster than Next()


294  /// but is not functionally equivalent to System.Random.Next().


295  /// </summary>


296  /// <returns></returns>


297  public int NextInt() {


298  uint t = (x ^ (x << 11));


299  x = y; y = z; z = w;


300  return (int)(0x7FFFFFFF & (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))));


301  }


302 


303  /// <summary>


304  /// Generates a single random bit.


305  /// This method's performance is improved by generating 32 bits in one operation and storing them


306  /// ready for future calls.


307  /// </summary>


308  /// <returns></returns>


309  public bool NextBool() {


310  if (bitMask == 1) {


311  // Generate 32 more bits.


312  uint t = (x ^ (x << 11));


313  x = y; y = z; z = w;


314  bitBuffer = w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));


315 


316  // Reset the bitMask that tells us which bit to read next.


317  bitMask = 0x80000000;


318  return (bitBuffer & bitMask) == 0;


319  }


320  return (bitBuffer & (bitMask >>= 1)) == 0;


321  }


322  // Buffer 32 bits in bitBuffer, return 1 at a time, keep track of how many have been returned


323  // with bitBufferIdx.


324  [Storable]


325  private uint bitBuffer;


326  [Storable]


327  private uint bitMask = 1;


328 


329 


330  #endregion


331 


332  #region IRandom Members


333 


334  public void Reset() {


335  Reinitialise((int)Environment.TickCount);


336  }


337 


338  public void Reset(int seed) {


339  Reinitialise(seed);


340  }


341 


342  #endregion


343 


344  public override Common.IDeepCloneable Clone(Common.Cloner cloner) {


345  FastRandom clone = (FastRandom)base.Clone(cloner);


346  clone.x = x;


347  clone.y = y;


348  clone.z = z;


349  clone.w = w;


350  clone.bitBuffer = bitBuffer;


351  clone.bitMask = bitMask;


352  return clone;


353  }


354  }


355  }

