MTRand Class Reference

Generate unsigner 32 bits random number using the Merdsenne Twister Algorithm. More...

#include <MersenneTwister.h>

Inheritance diagram for MTRand:

Public Types
enum	{ N = 624 }
enum	{ SAVE = N + 1 }
typedef unsigned long	uint32
	unsigned integer type, at least 32 bits

Public Member Functions
	MTRand (const uint32 &oneSeed)
	Initialize with a simple uint32.
	MTRand (uint32 *const bigSeed, uint32 const seedLength=N)
	Initialize with a an array.
	MTRand ()
	auto-initialize with /dev/urandom or time() and clock()
double	rand ()
	real number in [0,1]
double	rand (const double &n)
	real number in [0,n]
double	randExc ()
	real number in [0,1)
double	randExc (const double &n)
	real number in [0,n)
double	randDblExc ()
	real number in (0,1)
double	randDblExc (const double &n)
	real number in (0,n)
uint32	randInt ()
	integer in [0,2^32-1]
double	operator() ()
	same as rand().
uint32	randInt (const uint32 &n)
	integer in [0,n] for n < 2^32
double	rand53 ()
	Access to 53-bit random numbers (capacity of IEEE double precision).
double	randNorm (const double &mean, const double &variance)
	Access to nonuniform random number distributions.
void	seed (const uint32 oneSeed)
	Re-seeding functions with same behavior as initializers.
void	seed (uint32 *const bigSeed, const uint32 seedLength)
	Re-seeding functions with same behavior as initializers.
void	seed ()
	Re-seeding functions with same behavior as initializers.
void	save (uint32 *saveArray) const
	Saving and loading generator state.
void	load (uint32 *const loadArray)
	Saving and loading generator state.

Protected Types
enum	{ M = 397 }

Protected Member Functions
void	initialize (const uint32 seed)
	Initialize generator state with seed See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
void	reload ()
	Generate N new values in state Made disposeer and faster by Matthew Bellew (matth.nosp@m.ew.b.nosp@m.ellew.nosp@m.@hom.nosp@m.e.com)
uint32	hiBit (const uint32 &u) const
	High bit.
uint32	loBit (const uint32 &u) const
	low bit.
uint32	loBits (const uint32 &u) const
	low bits.
uint32	mixBits (const uint32 &u, const uint32 &v) const
	mixed bits.
uint32	twist (const uint32 &m, const uint32 &s0, const uint32 &s1) const
	twisted values.

Static Protected Member Functions
static uint32	hash (time_t t, clock_t c)
	Get a uint32 from t and c Better than uint32(x) in case x is floating point in [0,1] Based on code by Lawrence Kirby (fred@.nosp@m.gene.nosp@m.sis.d.nosp@m.emon.nosp@m..co.u.nosp@m.k)

Protected Attributes
uint32	state [N]
	internal state
uint32 *	pNext
	Next value to get from state.
int	left
	number of values left before reload needed

Detailed Description

Generate unsigner 32 bits random number using the Merdsenne Twister Algorithm.

The Mersenne Twister is an algorithm for generating random numbers. It was designed with consideration of the flaws in various other generators. The period, 2^19937-1, and the order of equidistribution, 623 dimensions, are far greater. The generator is also fast; it avoids multiplication and division, and it benefits from caches and pipelines. For more information see the inventors' web page at http://www.math.keio.ac.jp/~matumoto/emt.html

Reference M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.

Do NOT use for CRYPTOGRAPHY without securely hashing several returned values together, otherwise the generator state can be learned after reading 624 consecutive values. Access to 32-bit random numbers

Not thread safe (unless auto-initialization is avoided and each thread has its own MTRand object)

Definition at line 87 of file MersenneTwister.h.

Member Typedef Documentation

uint32

typedef unsigned long MTRand::uint32

unsigned integer type, at least 32 bits

Definition at line 92 of file MersenneTwister.h.

Member Enumeration Documentation

anonymous enum

anonymous enum

Enumerator
N

Definition at line 94 of file MersenneTwister.h.

{ N = 624 };       

anonymous enum

anonymous enum

Enumerator
SAVE

Definition at line 95 of file MersenneTwister.h.

{ SAVE = N + 1 };  

anonymous enum

anonymous enum

protected

Enumerator
M

Definition at line 98 of file MersenneTwister.h.

{ M = 397 };  

Constructor & Destructor Documentation

MTRand() [1/3]

MTRand::MTRand ( const uint32 &  oneSeed )

inline

Initialize with a simple uint32.

Definition at line 107 of file MersenneTwister.h.

    { seed(oneSeed); }

References seed().

MTRand() [2/3]

MTRand::MTRand ( uint32 *const  bigSeed, uint32 const  seedLength = N  )

inline

Initialize with a an array.

Definition at line 111 of file MersenneTwister.h.

    { seed(bigSeed,seedLength); }

References seed().

MTRand() [3/3]

MTRand::MTRand ( )

inline

auto-initialize with /dev/urandom or time() and clock()

Definition at line 115 of file MersenneTwister.h.

    { seed(); }

References seed().

Member Function Documentation

hash()

static uint32 MTRand::hash ( time_t  t, clock_t  c  )

inlinestaticprotected

Get a uint32 from t and c Better than uint32(x) in case x is floating point in [0,1] Based on code by Lawrence Kirby (fred@.nosp@m.gene.nosp@m.sis.d.nosp@m.emon.nosp@m..co.u.nosp@m.k)

Definition at line 345 of file MersenneTwister.h.

    {
      static uint32 differ = 0;  // guarantee time-based seeds will change
 
      uint32 h1 = 0;
      unsigned char *p = (unsigned char *) &t;
      for( size_t i = 0; i < sizeof(t); ++i )
      {
        h1 *= UCHAR_MAX + 2U;
        h1 += p[i];
      }
      uint32 h2 = 0;
      p = (unsigned char *) &c;
      for( size_t j = 0; j < sizeof(c); ++j )
      {
        h2 *= UCHAR_MAX + 2U;
        h2 += p[j];
      }
      return ( h1 + differ++ ) ^ h2;
    }

Referenced by seed().

hiBit()

uint32 MTRand::hiBit ( const uint32 &  u ) const

inlineprotected

High bit.

Definition at line 322 of file MersenneTwister.h.

    { return u & 0x80000000UL; }

Referenced by mixBits().

initialize()

void MTRand::initialize ( const uint32  seed )

inlineprotected

Initialize generator state with seed See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.

In previous versions, most significant bits (MSBs) of the seed affect only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto.

Definition at line 292 of file MersenneTwister.h.

    {
      uint32 *s = state;
      uint32 *r = state;
      int i = 1;
      *s++ = seed & 0xffffffffUL;
      for( ; i < N; ++i )
      {
        *s++ = ( 1812433253UL * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffUL;
        r++;
      }
    }

References N, seed(), and state.

Referenced by seed(), and seed().

load()

void MTRand::load ( uint32 *const  loadArray )

inline

Saving and loading generator state.

from such array

Definition at line 275 of file MersenneTwister.h.

    {
      uint32 *s = state;
      uint32 *la = loadArray;
      int i = N;
      for( ; i--; *s++ = *la++ ) {}
      left = *la;
      pNext = &state[N-left];
    }

References left, N, pNext, and state.

loBit()

uint32 MTRand::loBit ( const uint32 &  u ) const

inlineprotected

low bit.

Definition at line 326 of file MersenneTwister.h.

    { return u & 0x00000001UL; }

Referenced by twist().

loBits()

uint32 MTRand::loBits ( const uint32 &  u ) const

inlineprotected

low bits.

Definition at line 330 of file MersenneTwister.h.

    { return u & 0x7fffffffUL; }

Referenced by mixBits().

mixBits()

uint32 MTRand::mixBits ( const uint32 &  u, const uint32 &  v  ) const

inlineprotected

mixed bits.

Definition at line 334 of file MersenneTwister.h.

    { return hiBit(u) | loBits(v); }

References hiBit(), and loBits().

Referenced by twist().

operator()()

double MTRand::operator() ( )

inline

same as rand().

Definition at line 148 of file MersenneTwister.h.

{ return rand(); }

References rand().

Referenced by STK::RandBase::operator()().

rand() [1/2]

double MTRand::rand ( )

inline

real number in [0,1]

Definition at line 119 of file MersenneTwister.h.

{ return double(randInt()) * (1.0/4294967295.0); }

References randInt().

Referenced by operator()(), STK::RandBase::rand(), and STK::RandBase::rand().

rand() [2/2]

double MTRand::rand ( const double &  n )

inline

real number in [0,n]

Definition at line 121 of file MersenneTwister.h.

{ return rand() * n; }

References rand().

Referenced by rand().

rand53()

double MTRand::rand53 ( )

inline

Access to 53-bit random numbers (capacity of IEEE double precision).

real number in [0,1)

Definition at line 174 of file MersenneTwister.h.

    {
      uint32 a = randInt() >> 5, b = randInt() >> 6;
      // by Isaku Wada
      return ( a * 67108864.0 + b ) * (1.0/9007199254740992.0);
    }

References randInt().

randDblExc() [1/2]

double MTRand::randDblExc ( )

inline

real number in (0,1)

Definition at line 127 of file MersenneTwister.h.

{ return ( double(randInt()) + 0.5 ) * (1.0/4294967296.0); }

References randInt().

Referenced by STK::RandBase::randDblExc(), STK::RandBase::randDblExc(), and randNorm().

randDblExc() [2/2]

double MTRand::randDblExc ( const double &  n )

inline

real number in (0,n)

Definition at line 129 of file MersenneTwister.h.

{ return randDblExc() * n; }

References randDblExc().

Referenced by randDblExc().

randExc() [1/2]

double MTRand::randExc ( )

inline

real number in [0,1)

Definition at line 123 of file MersenneTwister.h.

{ return double(randInt()) * (1.0/4294967296.0); }

References randInt().

Referenced by STK::RandBase::randExc(), STK::RandBase::randExc(), and randNorm().

randExc() [2/2]

double MTRand::randExc ( const double &  n )

inline

real number in [0,n)

Definition at line 125 of file MersenneTwister.h.

{ return randExc() * n; }

References randExc().

Referenced by randExc().

randInt() [1/2]

uint32 MTRand::randInt ( )

inline

integer in [0,2^32-1]

Definition at line 132 of file MersenneTwister.h.

    {
      // Pull a 32-bit integer from the generator state
      // Every other access function simply transforms the numbers
      // extracted here
      if( left == 0 ) reload();
      --left;
 
      uint32 s1;
      s1  = *pNext++;
      s1 ^= (s1 >> 11);
      s1 ^= (s1 <<  7) & 0x9d2c5680UL;
      s1 ^= (s1 << 15) & 0xefc60000UL;
      return ( s1 ^ (s1 >> 18) );
    }

References left, pNext, and reload().

Referenced by rand(), rand53(), randDblExc(), STK::RandBase::randDiscreteUnif(), randExc(), STK::RandBase::randGauss(), and randInt().

randInt() [2/2]

uint32 MTRand::randInt ( const uint32 &  n )

inline

integer in [0,n] for n < 2^32

Definition at line 151 of file MersenneTwister.h.

    {
      // Find which bits are used in n
      // Optimized by Magnus Jonsson (magnus@smartelectronix.com)
      uint32 used = n;
      used |= used >> 1;
      used |= used >> 2;
      used |= used >> 4;
      used |= used >> 8;
      used |= used >> 16;
 
      // Draw numbers until one is found in [0,n]
      uint32 i;
      do
          i = randInt() & used;  // toss unused bits to shorten search
      while( i > n );
      return i;
    }

References randInt().

randNorm()

double MTRand::randNorm ( const double &  mean, const double &  variance  )

inline

Access to nonuniform random number distributions.

Return a real number from a normal (Gaussian) distribution with given mean and variance by Box-Muller method.

Definition at line 184 of file MersenneTwister.h.

    {
      double r = sqrt( -2.0 * log( 1.0-randDblExc()) ) * variance;
      double phi = STK::Const::_2PI_ * randExc();
      return mean + r * cos(phi);
    }

References randDblExc(), and randExc().

reload()

void MTRand::reload ( )

inlineprotected

Generate N new values in state Made disposeer and faster by Matthew Bellew (matth.nosp@m.ew.b.nosp@m.ellew.nosp@m.@hom.nosp@m.e.com)

Definition at line 309 of file MersenneTwister.h.

    {
      uint32 *p = state;
      int i;
      for( i = N - M; i--; ++p )
        *p = twist( p[M], p[0], p[1] );
      for( i = M; --i; ++p )
        *p = twist( p[M-N], p[0], p[1] );
      *p = twist( p[M-N], p[0], state[0] );
 
      left = N, pNext = state;
    }

References left, M, N, pNext, state, and twist().

Referenced by randInt(), seed(), and seed().

save()

void MTRand::save ( uint32 *  saveArray ) const

inline

Saving and loading generator state.

to array of size SAVE

Definition at line 263 of file MersenneTwister.h.

    {
      uint32 *sa = saveArray;
      const uint32 *s = state;
      int i = N;
      for( ; i--; *sa++ = *s++ ) {}
      *sa = left;
    }

References left, N, and state.

seed() [1/3]

void MTRand::seed ( )

inline

Re-seeding functions with same behavior as initializers.

Seed the generator with an array from /dev/urandom if available Otherwise use a hash of time() and clock() values

Definition at line 240 of file MersenneTwister.h.

    {
      // First try getting an array from /dev/urandom
      FILE* urandom = fopen( "/dev/urandom", "rb" );
      if( urandom )
      {
          uint32 bigSeed[N];
          uint32 *s = bigSeed;
          int i = N;
          bool success = true;
          while( success && i-- )
              success = fread( s++, sizeof(uint32), 1, urandom );
          fclose(urandom);
          if( success ) { seed( bigSeed, N );  return; }
      }
 
      // Was not successful, so use time() and clock() instead
      seed( hash( time(NULL), clock() ) );
    }

References hash(), N, and seed().

Referenced by initialize(), MTRand(), MTRand(), MTRand(), STK::RandBase::RandBase(), and seed().

seed() [2/3]

void MTRand::seed ( const uint32  oneSeed )

inline

Re-seeding functions with same behavior as initializers.

Seed the generator with a simple uint32

Definition at line 193 of file MersenneTwister.h.

    {
      initialize(oneSeed);
      reload();
    }

References initialize(), and reload().

seed() [3/3]

void MTRand::seed ( uint32 *const  bigSeed, const uint32  seedLength  )

inline

Re-seeding functions with same behavior as initializers.

Seed the generator with an array of uint32's There are 2^19937-1 possible initial states. This function allows all of those to be accessed by providing at least 19937 bits (with a default seed length of N = 624 uint32's). Any bits above the lower 32 in each element are discarded. Just call seed() if you want to get array from /dev/urandom

Definition at line 207 of file MersenneTwister.h.

    {
      initialize(19650218UL);
      int i = 1;
      uint32 j = 0;
      int k = ( N > seedLength ? N : seedLength );
      for( ; k; --k )
      {
        state[i] =
            state[i] ^ ( (state[i-1] ^ (state[i-1] >> 30)) * 1664525UL );
        state[i] += ( bigSeed[j] & 0xffffffffUL ) + j;
        state[i] &= 0xffffffffUL;
        ++i;  ++j;
        if( i >= N ) { state[0] = state[N-1];  i = 1; }
        if( j >= seedLength ) j = 0;
      }
      for( k = N - 1; k; --k )
      {
        state[i] =
          state[i] ^ ( (state[i-1] ^ (state[i-1] >> 30)) * 1566083941UL );
        state[i] -= i;
        state[i] &= 0xffffffffUL;
        ++i;
        if( i >= N ) { state[0] = state[N-1];  i = 1; }
      }
      state[0] = 0x80000000UL;// MSB is 1, assuring non-zero initial array
      reload();
    }

References initialize(), N, reload(), and state.

twist()

uint32 MTRand::twist ( const uint32 &  m, const uint32 &  s0, const uint32 &  s1  ) const

inlineprotected

twisted values.

Definition at line 338 of file MersenneTwister.h.

    { return m ^ (mixBits(s0,s1)>>1) ^ (-loBit(s1) & 0x9908b0dfUL); }

References loBit(), and mixBits().

Referenced by reload().

Member Data Documentation

left

int MTRand::left

protected

number of values left before reload needed

Definition at line 102 of file MersenneTwister.h.

Referenced by load(), randInt(), reload(), and save().

pNext

uint32* MTRand::pNext

protected

Next value to get from state.

Definition at line 101 of file MersenneTwister.h.

Referenced by load(), randInt(), and reload().

state

uint32 MTRand::state[N]

protected

internal state

Definition at line 100 of file MersenneTwister.h.

Referenced by initialize(), load(), reload(), save(), and seed().

---

The documentation for this class was generated from the following file:

• MersenneTwister.h