STK++  0.4
Public Types | Public Member Functions | Protected Types | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Friends
MTRand Class Reference

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

#include <MersenneTwister.h>

Inheritance diagram for MTRand:
Inheritance graph
[legend]

List of all members.

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 (matthew.bellew@home.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@genesis.demon.co.uk)

Protected Attributes

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

Friends

std::ostream & operator<< (std::ostream &os, const MTRand &mtrand)
std::istream & operator>> (std::istream &is, MTRand &mtrand)

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

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
Enumerator:
N 

Definition at line 94 of file MersenneTwister.h.

{ N = 624 };
anonymous enum
Enumerator:
SAVE 

Definition at line 95 of file MersenneTwister.h.

{ SAVE = N + 1 };
anonymous enum [protected]
Enumerator:
M 

Definition at line 98 of file MersenneTwister.h.

{ M = 397 };

Constructor & Destructor Documentation

MTRand::MTRand ( const uint32 &  oneSeed) [inline]

Initialize with a simple uint32.

Definition at line 107 of file MersenneTwister.h.

References seed().

    { seed(oneSeed); }
MTRand::MTRand ( uint32 *const  bigSeed,
uint32 const  seedLength = N 
) [inline]

Initialize with a an array.

Definition at line 111 of file MersenneTwister.h.

References seed().

    { seed(bigSeed,seedLength); }
MTRand::MTRand ( ) [inline]

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

Definition at line 115 of file MersenneTwister.h.

References seed().

    { seed(); }

Member Function Documentation

double MTRand::rand ( ) [inline]

real number in [0,1]

Definition at line 119 of file MersenneTwister.h.

References randInt().

Referenced by operator()().

    { return double(randInt()) * (1.0/4294967295.0); }
double MTRand::rand ( const double &  n) [inline]

real number in [0,n]

Definition at line 123 of file MersenneTwister.h.

References rand().

Referenced by rand().

    { return rand() * n; }
double MTRand::randExc ( ) [inline]

real number in [0,1)

Definition at line 127 of file MersenneTwister.h.

References randInt().

Referenced by randNorm().

    { return double(randInt()) * (1.0/4294967296.0); }
double MTRand::randExc ( const double &  n) [inline]

real number in [0,n)

Definition at line 131 of file MersenneTwister.h.

References randExc().

Referenced by randExc().

    { return randExc() * n; }
double MTRand::randDblExc ( ) [inline]

real number in (0,1)

Definition at line 135 of file MersenneTwister.h.

References randInt().

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

    { return ( double(randInt()) + 0.5 ) * (1.0/4294967296.0); }
double MTRand::randDblExc ( const double &  n) [inline]

real number in (0,n)

Definition at line 139 of file MersenneTwister.h.

References randDblExc().

Referenced by randDblExc().

    { return randDblExc() * n; }
uint32 MTRand::randInt ( ) [inline]

integer in [0,2^32-1]

Definition at line 143 of file MersenneTwister.h.

References left, pNext, and reload().

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

    {
      // Pull a 32-bit integer from the generator state
      // Every other access function simply transforms the numbers
      // extracted here
      if( left == 0 ) reload();
      --left;

      register uint32 s1;
      s1  = *pNext++;
      s1 ^= (s1 >> 11);
      s1 ^= (s1 <<  7) & 0x9d2c5680UL;
      s1 ^= (s1 << 15) & 0xefc60000UL;
      return ( s1 ^ (s1 >> 18) );
    }
double MTRand::operator() ( ) [inline]

same as rand().

Reimplemented in STK::RandBase.

Definition at line 159 of file MersenneTwister.h.

References rand().

{ return rand(); }
uint32 MTRand::randInt ( const uint32 &  n) [inline]

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

Definition at line 162 of file MersenneTwister.h.

References randInt().

    {
      // 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;
    }
double MTRand::rand53 ( ) [inline]

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

real number in [0,1)

Definition at line 185 of file MersenneTwister.h.

References randInt().

    {
      uint32 a = randInt() >> 5, b = randInt() >> 6;
      // by Isaku Wada
      return ( a * 67108864.0 + b ) * (1.0/9007199254740992.0);
    }
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 195 of file MersenneTwister.h.

References randDblExc(), randExc(), and STK::Stat::variance().

    {
      double r = sqrt( -2.0 * log( 1.0-randDblExc()) ) * variance;
      double phi = STK::Const::_2PI_ * randExc();
      return mean + r * cos(phi);
    }
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 204 of file MersenneTwister.h.

References initialize(), and reload().

    {
      initialize(oneSeed);
      reload();
    }
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 218 of file MersenneTwister.h.

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

    {
      initialize(19650218UL);
      register int i = 1;
      register uint32 j = 0;
      register 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();
    }
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 251 of file MersenneTwister.h.

References hash(), and N.

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

    {
      // First try getting an array from /dev/urandom
      FILE* urandom = fopen( "/dev/urandom", "rb" );
      if( urandom )
      {
          uint32 bigSeed[N];
          register uint32 *s = bigSeed;
          register int i = N;
          register 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() ) );
    }
void MTRand::save ( uint32 *  saveArray) const [inline]

Saving and loading generator state.

to array of size SAVE

Definition at line 274 of file MersenneTwister.h.

References left, N, and state.

    {
      register uint32 *sa = saveArray;
      register const uint32 *s = state;
      register int i = N;
      for( ; i--; *sa++ = *s++ ) {}
      *sa = left;
    }
void MTRand::load ( uint32 *const  loadArray) [inline]

Saving and loading generator state.

from such array

Definition at line 286 of file MersenneTwister.h.

References left, N, pNext, and state.

    {
      register uint32 *s = state;
      register uint32 *la = loadArray;
      register int i = N;
      for( ; i--; *s++ = *la++ ) {}
      left = *la;
      pNext = &state[N-left];
    }
void MTRand::initialize ( const uint32  seed) [inline, protected]

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 308 of file MersenneTwister.h.

References N, and state.

Referenced by seed().

    {
      register uint32 *s = state;
      register uint32 *r = state;
      register int i = 1;
      *s++ = seed & 0xffffffffUL;
      for( ; i < N; ++i )
      {
        *s++ = ( 1812433253UL * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffUL;
        r++;
      }
    }
void MTRand::reload ( ) [inline, protected]

Generate N new values in state Made disposeer and faster by Matthew Bellew (matthew.bellew@home.com)

Definition at line 325 of file MersenneTwister.h.

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

Referenced by randInt(), and seed().

    {
      register uint32 *p = state;
      register 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;
    }
uint32 MTRand::hiBit ( const uint32 &  u) const [inline, protected]

High bit.

Definition at line 338 of file MersenneTwister.h.

Referenced by mixBits().

    { return u & 0x80000000UL; }
uint32 MTRand::loBit ( const uint32 &  u) const [inline, protected]

low bit.

Definition at line 342 of file MersenneTwister.h.

Referenced by twist().

    { return u & 0x00000001UL; }
uint32 MTRand::loBits ( const uint32 &  u) const [inline, protected]

low bits.

Definition at line 346 of file MersenneTwister.h.

Referenced by mixBits().

    { return u & 0x7fffffffUL; }
uint32 MTRand::mixBits ( const uint32 &  u,
const uint32 &  v 
) const [inline, protected]

mixed bits.

Definition at line 350 of file MersenneTwister.h.

References hiBit(), and loBits().

Referenced by twist().

    { return hiBit(u) | loBits(v); }
uint32 MTRand::twist ( const uint32 &  m,
const uint32 &  s0,
const uint32 &  s1 
) const [inline, protected]

twisted values.

Definition at line 354 of file MersenneTwister.h.

References loBit(), and mixBits().

Referenced by reload().

    { return m ^ (mixBits(s0,s1)>>1) ^ (-loBit(s1) & 0x9908b0dfUL); }
static uint32 MTRand::hash ( time_t  t,
clock_t  c 
) [inline, static, protected]

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@genesis.demon.co.uk)

Definition at line 361 of file MersenneTwister.h.

Referenced by seed().

    {
      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;
    }

Friends And Related Function Documentation

std::ostream& operator<< ( std::ostream &  os,
const MTRand &  mtrand 
) [friend]

Definition at line 383 of file MersenneTwister.h.

{
    register const MTRand::uint32 *s = mtrand.state;
    register int i = mtrand.N;
    for( ; i--; os << *s++ << "\t" ) {}
    return os << mtrand.left;
}
std::istream& operator>> ( std::istream &  is,
MTRand &  mtrand 
) [friend]

Definition at line 392 of file MersenneTwister.h.

{
    register MTRand::uint32 *s = mtrand.state;
    register int i = mtrand.N;
    for( ; i--; is >> *s++ ) {}
    is >> mtrand.left;
    mtrand.pNext = &mtrand.state[mtrand.N-mtrand.left];
    return is;
}

Member Data Documentation

uint32 MTRand::state[N] [protected]

internal state

Definition at line 100 of file MersenneTwister.h.

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

uint32* MTRand::pNext [protected]

Next value to get from state.

Definition at line 101 of file MersenneTwister.h.

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

int MTRand::left [protected]

number of values left before reload needed

Definition at line 102 of file MersenneTwister.h.

Referenced by load(), operator<<(), operator>>(), randInt(), reload(), and save().

The documentation for this class was generated from the following file:
Generated on Wed May 22 2013 23:07:32 for STK++ by   doxygen 1.7.6.1