• Slumptalsgenerator (WELL)

    Den inbyggda slumptalsgeneratorn (rand) är inte nödvändigtvis den bästa. Det finns gott om algoritmer för att generera slumpvärden, men en som anses vara riktigt bra är en kallad WELL, vilken är nyare och lite bättre än t.ex. den relativt välkända Mersenne Twister. Jag har här stoppat in den i en praktiskt helper klass kallad Random, som även har en del hjälpfunktioner för att generera slumptal som både heltal och decimaltal, eller inom ett visst intervall.

    Koden kan laddas hem här, och är public domain:
    http://www.colossusentertainment.com...ref/random.zip

    Och här är den inklistrad i postningen, för dom som bara vill ta en snabbtitt :-)
    Kod:
    /**
     * \class	Random
     * 
     * \ingroup	core
     * \brief	Random number generator
     * \author	Mattias Gustavsson	
     * 
     * Random number generation, using the WELL algorithm by F. Panneton, P. L'Ecuyer and M. Matsumoto.
     * The creators of the algorithm describes it like this:
     *
     *      Fast uniform random number generators with extremely long periods have been defined and implemented based on 
     *      linear recurrences modulo 2. The twisted GFSR and the Mersenne twister are famous recent examples. Besides the 
     *      period length, the statistical quality of these generators is usually assessed via their equidistribution 
     *      properties. The huge-period generators proposed so far are not quite optimal in that respect. In this paper, 
     *      we propose new generators, with better equidistribution and "bit-mixing" properties for equivalent period length 
     *      and speed. Approximately half of the coefficients of the characteristic polynomial of these generators are 
     *      nonzero. The state of our new generators evolves in a more chaotic way than for the Mersenne twister. We 
     *      illustrate how this can reduce the impact of persistent dependencies among successive output values, which can 
     *      be observed in certain parts of the period of gigantic generators such as the Mersenne twister.
     *
     * More information in the original paper: http://www.iro.umontreal.ca/~panneton/WELLRNG.html
     *
     * This code is originally based on WELL512 C/C++ code written by Chris Lomont (published in Game Programming Gems 7) 
     * and placed in the public domain. There's also an article about it on Lomont's site:
     *
     *      http://lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf
     */
    
    #ifndef Random_H
    #define Random_H
    
    class Random
    	{
    	public:
    		/**
    		 * Constructor. Initialises generator with a default seed
    		 */
    		Random();
    
    		/**
    		 * Seeds the generator with a custom seed value. 
    		 */
    		void Seed(
    			unsigned int seed	///< Custom seed value
    			);
    
    		/**
    		 * Retrieves the internal state of the generator. This consists of 16
    		 * unsigned ints, and one index value. This state can be stored and
    		 * later re-applied to a generator to continue along the same sequence.
    		 */
                    void GetState(
    			unsigned int state[16], ///< Array to receive the internal state from the generator
    			int& index ///< Variable to receive the index value from the generator
    			);
    
    		/**
    		 * Re-applies a state that was previously retrieved by calling GetState.
    		 * Useful to continue the generator from a previously saved point.
    		 */
                    void SetState(
    			const unsigned int state[16], ///< Array of state values to be applied to the generator
    			int index // Index value to be applied to the generator
    			);
    
    		/** 
    		 * Generates a random number on [0,0xffffffff]-interval
    		 */
    		unsigned int RandomInteger();
    
    		/**
    		 * Generates a random number on [0,0.99999999999...] interval
    		 */
    		float RandomFloat();
    
    		/**
    		 * Generates a random number on [min,max] interval
    		 */
    		int RandomRanged(int min, int max);
    
    	private:
                    unsigned int state_[16];	///< The internal state of the generator
                    unsigned int index_; ///< Current index value
    
    };
    
    #endif /* Random_H */
    Kod:
    //*** Random.cpp ***
    
    #include "Random.h"
    
    //*** Constructor ***
    
    Random::Random():
            index_(0)
    	{
            Seed(0x5ee39c34);  // Default seed
            }
    
    
    //*** Seed ***
    
    void Random::Seed(unsigned int s)
    	{	
    	// Some bit manipulation magic to propagate seed value to the internal state
            state_[0]=s^0xf68a9fc1;
            for (int i=1; i<16; i++) 
    		{
                    state_[i] = (0x6c078965U * (state_[i-1] ^ (state_[i-1] >> 30)) + i); 
    		}
    	index_ = 0;
    	}
    
    
    //*** SetState ***
    
    void Random::SetState(const unsigned int state[16], int index)
            {
            for (int i=0; i<16; i++)
                {
                state_[i]=state[i];
                }
    
            index_=index&15;
            }
    
    
    //*** GetState ***
    
    void Random::GetState(unsigned int state[16], int& index)
            {
            for (int i=0; i<16; i++)
                {
                state[i]=state_[i];
                }
    
            index=index_;
            }
    
    
    //*** RandomInteger ***
    
    unsigned int Random::RandomInteger()
    	{
    	// This is basically just the WELL algorithm as-is
            unsigned int a = state_[index_];
            unsigned int c = state_[(index_+13)&15];
            unsigned int b = a^c^(a<<16)^(c<<15);
            c = state_[(index_+9)&15];
            c ^= (c>>11);
            a = state_[index_] = b^c;
            unsigned int d = a^((a<<5)&0xda442d24U);
            index_ = (index_ + 15)&15;
            a = state_[index_];
            state_[index_] = a^b^d^(a<<2)^(b<<18)^(c<<28);
            return state_[index_];
    	}
    
    
    //*** RandomRanged ***
    
    int Random::RandomRanged(int min, int max)
    	{
    	// Calculate the range. The +1 is because the RandomFloat method returns
    	// values up to, but not including, 1. So, a max/min difference of 0, will 
    	// result in a range value of 1, which will (correctly) return all zeros.
    	// If we didn't do this, probability that max would come up would be wrong.
    	int range=(max-min)+1;
    
    	// If min was greater than max, just return min
    	if (range<=0)
    		{
    		return min;
    		}
    	
    	// Get a random float and scale it with the range. By generating a float and
    	// scaling it by range, we guarantee an equal distribution of values, which
    	// we are not sure to get if using modulo operator for the range.
    	int value=(int)(RandomFloat()*range);
            return min+value; 
    	}
    
    
    //*** RandomFloat ***
    
    float Random::RandomFloat()
    	{
            // Get a random integer, and divide by 2^32
            return (RandomInteger()/4294967296.0f);     
    	}
    This article was originally published in forum thread: Slumptalsgenerator (WELL) started by Mattias Gustavsson View original post
    Comments 5 Comments
    1. EClaessons avatar
      EClaesson -
      Vad är fördelarna med WELL jämfört med t.ex. Mersenne Twister?
    1. madahs avatar
      madah -
      Mersenne Twister använder ett mycket större internt state (624 st 32-bitars ord), medans WELL har ett mindre med endast 16 st 32-bitars ord.

      Detta är en fördel om man behöver spara ner exakt hela state, t ex för att kunna återskapa en genererad worldmap. Sen vill man kanske ha flera olika instanser av slumptalsgeneratorer, t ex en för worldmap och en för fiender/items. Då kan 2.5 KB per instans bli lite saftigt, jämfört med 64 byte för WELL.

      Sen påstås det också att WELL är 40% snabbare än Mersenne Twister, vilket alltid är en fördel.

      I övrigt så är det ett litet fel i koden, 0xda442d20U ska vara 0xda442d24U, vilket det också är i koden från den länkade html-sidan och pdf-dokumentet.
    1. Mattias Gustavssons avatar
      Mattias Gustavsson -
      oops - tack för det, har ingen aning om hur jag lyckades få in det felet :P

      WELL har dessutom bättre slumptalsdistribution, bättre bit-mixning (användbart vid t.ex. hashning) och hakar inte upp sig lika lätt (en del slumptalsgeneratorer kan hamna i ett internt noll-state som de har svårt att ta sig ur).
    1. doozs avatar
      dooz -
      Hittade precis en artikel om en ny snabb och "bra" slumptalsgenerator, Xorshift, som kanske kan vara intressant: http://xorshift.di.unimi.it/

      Dom postar även tabeller med period sant ns/genererad bit och jämför med MT och WELL.
    1. madahs avatar
      madah -
      Citat Ursprungligen postat av dooz Visa inlägg
      Hittade precis en artikel om en ny snabb och "bra" slumptalsgenerator, Xorshift, som kanske kan vara intressant: http://xorshift.di.unimi.it/

      Dom postar även tabeller med period sant ns/genererad bit och jämför med MT och WELL.
      Jag körde lite egna benchmarks (värden är i MiB/s):

      Kod:
      (Intel(R) Core(TM) i7 CPU         920  @ 2.67GHz)
      
                            | GCC 4.8.2 (Ubuntu)| MSVC 2008 (Win7)  | MSVC 2012 (Win7)  |
                            | 32 bit  | 64 bit  | 32 bit  | 64 bit  | 32 bit  | 64 bit  |
      ======================|=========|=========|=========|=========|=========|=========|
      gamerand              | 4213.99 | 4718.89 | 1178.37 | 4129.03 | 4338.98 | 4145.75 |
      Well512               |  800.63 |  747.45 |  427.20 |  424.54 |  496.12 |  503.19 |
      Mt19937ar             |  560.79 |  590.54 |  712.60 |  645.24 |  722.65 |  679.50 |
      Mt19937ar-cok         |  622.11 |  728.31 |  680.85 |  597.78 |  648.51 |  611.34 |
      XorShift1024star      |  813.99 | 2968.12 |  591.22 | 1750.43 |  666.67 | 1932.08 |
      XorShift128plus       | 1161.00 | 3893.54 | 1219.05 | 1943.07 | 1460.77 | 3447.81 |
      ======================|=========|=========|=========|=========|=========|=========|
      Intressant att även på äldre maskiner så är den dubbelt så snabb jämfört med MT eller Well:
      Kod:
      EeeBox = Asus EeeBox PC B202, Intel(R) Atom(TM) CPU N270   @ 1.60GHz, GCC 4.8.2 (Ubuntu) 32-bit
      RaspPi = Raspberry Pi, ARMv6-compatible processor rev 7 (v6l), GCC 4.6.3, 32-bit
      
                              EeeBox    RaspPi
      ======================|=========|=========|
      gamerand              | 1352.71 |  328.63 |
      Well512               |  174.15 |   78.84 |
      Mt19937ar             |  149.12 |   43.88 |
      Mt19937ar-cok         |  171.07 |   45.10 |
      XorShift1024star      |  243.58 |   92.49 |
      XorShift128plus       |  308.53 |  156.48 |
      ======================|=========|=========|
      Passade även på att köra dieharder (./prog | dieharder -a -g 200):
      Kod:
                            | PASSED  | WEAK    | FAILED  |
      ======================|=========|=========|=========|
      gamerand              |     103 |       2 |       9 |
      Well512               |     112 |       2 |       0 |
      XorShift1024star      |     112 |       2 |       0 |
      XorShift128plus       |     107 |       7 |       0 |
      ======================|=========|=========|=========|

      GameRand är en annan favorit som med fördel kan användas där "bra" slumptal inte är så viktigt, t ex particle systems:

      Kod:
      /** Based on the random number generator by Ian C. Bullard:
       *  http://www.redditmirror.cc/cache/websites/mjolnirstudios.com_7yjlc/mjolnirstudios.com/IanBullard/files/79ffbca75a75720f066d491e9ea935a0-10.html
       *
       *  GameRand is a random number generator based off an "Image of the Day" posted by Stephan Schaem
       *  http://www.flipcode.com/archives/07-15-2002.shtml
       *
       *  http://stackoverflow.com/questions/1046714/what-is-a-good-random-number-generator-for-a-game
       *
       */
      class GameRand
      {
      public:
          uint32_t Next()
          {
              high_   = (high_ << 16) | (high_ >> 16);
              high_   += low_;
              low_    += high_;
              return high_;
          }
      
          void Init(const uint32_t seed)
          {
              high_   = seed;
              low_    = high_ ^ 0x49616E42;
          }
      
          GameRand() { Init(1); }
          ~GameRand() {}
      private:
          uint32_t high_, low_;
      };