This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| MersenneTwister Submitted by

MersenneTwister is a fast (below 40 cycles of x86 CPU) pseudorandom number generator with very strong cryptographics properties and VERY large period (2^19937 -1).

Download Associated File: cMersenneTwister.h (3,827 bytes)

    #ifndef cMersenneTwister_h_INCLUDED
    #define cMersenneTwister_h_INCLUDED

    // This is the ``Mersenne Twister'' random number generator MT19937,
    // which generates pseudorandom integers uniformly distributed in
    // 0..(2^32 - 1) starting from any odd seed in 0..(2^32 - 1) with
    // period 2^19937 -1 with 623-dimmensional equidistibution up to
    // 32-bits of accurancy.
    // This is Shaw Cookus Implementation of algorithm invented by
    // Takuji Nishimura embedded into C++ class by me, that is
    // Maciek Urbański.
    // Amortized cost of generating 32-bit integer is 33 CPU cycles on
    // my K6-2 450MHz (MSVC 6.0/SP4). It's fast. ;-)
    // For detailed properties - there is a paper: "Mersenne Twister:
    // A 623-dimmensionally equidstributed uniform pseudorandom number
    // generator" by Makoto Matsumoto and Takuji Nishimura.

    #define N               (624)
    #define M               (397)
    #define K               (0x9908B0DFU)
    #define hiBit(u)        ((u) & 0x80000000U)
    #define loBit(u)        ((u) & 0x00000001U)
    #define loBits(u)       ((u) & 0x7FFFFFFFU)
    #define mixBits(u, v)   (hiBit(u)|loBits(v))
    #define SEED0           (4357U)

    class cMersenneTwister
    {
    private:
      unsigned long   state[N+1];   // state vector
      unsigned long   *next;        // next random
      int      left;                // how many values left
    public:
      ////////////////////////////////////////////////////////////////////
      // initialize MT via linear conguential generator
      // x[n+1] = (69069 * x[n]) mod 2^32
      void Init( unsigned long seed       //32-bit seed
               )
      {
        register unsigned long x = (seed | 1U) & 0xFFFFFFFFU, *s = state;
        register int j;
        for( left=0, *s++=x, j=N; --j; *s++ = (x*=69069U) & 0xFFFFFFFFU);
      }
      ////////////////////////////////////////////////////////////////////
      // load state vector
      void Load( unsigned long *state     //pointer to state (624*4 bytes)
               )
      {
        register unsigned long j, *s = state;
        for( j=N; --j; *s++ = *state++ );
      }
      ////////////////////////////////////////////////////////////////////
      // save state vector
      void Save( unsigned long *state     //pointer to state (624*4 bytes)
               )
      {
        register unsigned long j, *s = state;
        for( j=N; --j; *state++ = *s++ );
      }
      ////////////////////////////////////////////////////////////////////
      // create MT object
      cMersenneTwister( void )
      {
        left = -1;
      }
      ////////////////////////////////////////////////////////////////////
      // create MT object & init it
      cMersenneTwister( unsigned long seed )
      {
        Init( seed );
      }
      ////////////////////////////////////////////////////////////////////
      // create MT object & load seed
      cMersenneTwister( unsigned long *state )
      {
        Load( state );
      }
      ////////////////////////////////////////////////////////////////////
      // calculates next values
      unsigned long Reload( void )
      {
        register unsigned long *p0=state, *p2=state+2, *pM=state+M, s0, s1;
        register int j;
        if(left < -1) Init( SEED0 );
        left=N-1, next=state+1;
        for( s0=state[0], s1=state[1], j=N-M+1; --j; s0=s1, s1=*p2++ )
          *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
        for(pM=state, j=M; --j; s0=s1, s1=*p2++)
          *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
        s1 = state[0], *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
        s1 ^= (s1 >> 11);
        s1 ^= (s1 <<  7) & 0x9D2C5680U;
        s1 ^= (s1 << 15) & 0xEFC60000U;
        return ( s1 ^ (s1 >> 18) );
      }
      ////////////////////////////////////////////////////////////////////
      // get next value
      inline unsigned long Random( void )
      {
        register unsigned long y;
        if(--left < 0) return Reload();
        y  = *next++;
        y ^= (y >> 11);
        y ^= (y <<  7) & 0x9D2C5680U;
        y ^= (y << 15) & 0xEFC60000U;
        return(y ^ (y >> 18));
      }
    };

    #endif

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.