Würfeln

[volkard]

Erhard Henkes schrieb:

Volkard: "zeig mal die implemetierung der rand()."
Kann ich leider nicht, ist rand() aus der Standardbibliothek <cstdlib>.

ich suche sowas am liebvsten, indem ich mit dem debugger vor die funktion laufe (beim msvc mit cursor über die zaile mit rand() gehen und f10 drücken) funktion hüpfe (beim msvc f11).

[Marc++us]

@Erhard:

Evtl. wird Volkard das Ding auch noch serialisieren wollen... also sowas:

class RandomPersistent
{ 
...
public: 
   RandomPersistent() 
   { 
      ifstream in(bla);
      if (in)
         in >> holdrand; 
      else
         // bzw. bei Dateifehler (does not exist) dann 
         holdrand = time(0);
   } 
   ~RandomPersistent()
   {
      ofstream out(bla);
      out << holdrand;
   }
...
};

Ist doch wirklich ein Vorteil, daß der RandomGenerator inzwischen ein Template-Parameter ist.

[Erhard Henkes]

Das Konzeptionelle ist weitgehend klar. Ich muss mich nun mit verschiedenen Funktionen random() beschäftigen. Habe ich bisher nie getan, immer nur rand() aus <cstdlib> als Funktion eingesetzt. Ziel wäre z.B. eine verbesserte Gleichverteilung.

[Marc++us]

Soweit ich weiß ist im http://www.c-plusplus.net/titelanzeige.php?ISBN=3893193766 auch eine drin.

[Erhard Henkes]

Danke für den Hinweis. Robert Sedgewick, Algorithmen in C++, Kap. 35, S.577, "Zufallszahlen" (lineare und additive Kongruenz).

Grundmodell der linearen Kongruenz (D.Lehmer, 1951):

a[0] = seed;
for( int i=1; i <= N; ++i )
  a[i] = ( a[i-1] * k1 + 1 ) % k2;

Ergebnis: Ganze Zahl zwischen 0 und k2-1

[Erhard Henkes]

Momentan sieht mein Programm wie folgt aus (Volkards "geklaute" Random-Klasse integriert):

#include <iostream> 
#include <iomanip>  
#include <conio.h>  
#include <cstdlib> 
#include <ctime>  

class Random_aus_Stdlib_geklaut 
{ 
private: 
   unsigned int seed_; 
   int random() 
   { 
      return(((seed_ = seed_ * 214013L + 2531011L) >> 16) & 0x7fff); 
   } 
public: 
   Random_aus_Stdlib_geklaut(){ seed_ = static_cast<unsigned>(time(0)); } 
   Random_aus_Stdlib_geklaut( unsigned int seed ) { seed_ = seed; } 

   int getNum() 
   { 
       return random();
   } 
};

class RandomStdlib // verwendet rand()
{ 
private: 
   const unsigned int seed_;
public: 
   RandomStdlib():seed_( static_cast<unsigned>(time(0)) ){}

   int getNum() const
   { 
     static bool seed_flag=0;
     if(!seed_flag)
     { 
       srand(seed_);  
       seed_flag = true; 
       // std::cout << "Seed fuer rand(): " << seed_ << std::endl << std::endl;
     } 
     return rand();
   } 
};

class RandomTestEqual // Test auf Gleichverteilung
{ 
private: 
   int num_; 
public: 
   RandomTestEqual() : num_(RAND_MAX - 1){}; 
   int getNum()  
   { 
      num_++; 
      if (num_ >= RAND_MAX) num_ = 0; 
      return num_; 
   } 
};

template<typename T_Generator> class Wuerfel  
{  
private:
  const unsigned int maxzahl_; 
  const unsigned int maxrandom_; 
  T_Generator zahlengenerator_; // Template-Typ

public:  
  Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl),maxrandom_(RAND_MAX-(RAND_MAX%maxzahl)) {}  

  unsigned int wuerfelt() 
  { 
    unsigned int r; 
    do{ r = zahlengenerator_.getNum(); }  
      while ( r >= maxrandom_ ); 
    return ( r % maxzahl_ +1 );  
  }      
};  

int main()  
{  
  const unsigned long long Serie     = 3;  
  const unsigned long long Versuche  = 30000000;  
  const unsigned int limit           = 200;  
  const unsigned int moeglichkeiten  = 6;  

  Wuerfel<RandomTestEqual>  w0a(moeglichkeiten);  
  Wuerfel<RandomTestEqual>  w0b(2);  
  Wuerfel<RandomStdlib>     w1a(moeglichkeiten);  
  Wuerfel<RandomStdlib>     w1b(2);
  Wuerfel<Random_aus_Stdlib_geklaut>  w2a(moeglichkeiten);  
  Wuerfel<Random_aus_Stdlib_geklaut>  w2b(2);

  unsigned long long H[moeglichkeiten+1];  

  for(unsigned long long i=1; i<Serie+1; ++i)  
  {  
    for(unsigned int j=0; j<moeglichkeiten+1; ++j) H[j] = 0;  

    for(unsigned long long k=1; k<Versuche+1; ++k)  
    {  
      unsigned int wurf = w2a.wuerfelt(); // hier wird gewürfelt 

      if(Versuche<limit) std::cout << wurf << " ";  
      ++H[wurf];  
    }  

    for(unsigned int c=1; c<moeglichkeiten+1; ++c)  
    {  
      std::cout << std::endl << c << ": " << H[c] << " " << std::setprecision(7)   
                << 100 * static_cast<float>(H[c]) / Versuche << " %";  
      H[0] += H[c];  
    }  
    std::cout << std::endl << "Wuerfe insgesamt: " << H[0] << std::endl << std::endl;  
  }  
  getch();  
}

Nun müsste nur noch eine verbesserte random-Funktion her.

[Erhard Henkes]

Die von Volkard zitierte Methode sieht übrigens wie folgt aus (nach C++ transferiert):

//GNU 
#include <ctime>
#include <cstdio>
#include <conio.h>

/* Period parameters */  
const int N = 624;
const int M = 397;
const unsigned MATRIX_A   = 0x9908b0df; /* constant vector a */
const unsigned UPPER_MASK = 0x80000000; /* most significant w-r bits */
const unsigned LOWER_MASK = 0x7fffffff; /* least significant r bits */

/* Tempering parameters */   
const unsigned TEMPERING_MASK_B = 0x9d2c5680;
const unsigned TEMPERING_MASK_C = 0xefc60000;

unsigned TEMPERING_SHIFT_U(unsigned y)  {return (y >> 11);} 
unsigned TEMPERING_SHIFT_S(unsigned y)  {return (y <<  7);} 
unsigned TEMPERING_SHIFT_T(unsigned y)  {return (y << 15);} 
unsigned TEMPERING_SHIFT_L(unsigned y)  {return (y >> 18);} 

static unsigned mt[N]; /* the array for the state vector  */
static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */

unsigned seed;

/* initializing the array with a NONZERO seed */
void sgenrand(unsigned seed)	
{
    /* setting initial seeds to mt[N] using         */
    /* the generator Line 25 of Table 1 in          */
    /* [KNUTH 1981, The Art of Computer Programming */
    /*    Vol. 2 (2nd Ed.), pp102]                  */
    mt[0]= seed & 0xffffffff;
    for (mti=1; mti<N; mti++)
        mt[mti] = (69069 * mt[mti-1]) & 0xffffffff;
}

unsigned genrand()
{
    unsigned y;
    static unsigned mag01[2]={0x0, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */

    if (mti >= N) 
    { /* generate N words at one time */
        int kk;

        if (mti == N+1)   /* if sgenrand() has not been called, */
            sgenrand(4357); /* a default initial seed is used   */

        for (kk=0;kk<N-M;kk++) 
        {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1];
        }
        for (;kk<N-1;kk++) 
        {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1];

        mti = 0;
    }
    y = mt[mti++];
    y ^= TEMPERING_SHIFT_U(y);
    y ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
    y ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
    y ^= TEMPERING_SHIFT_L(y);
    return y; 
}

int main()
{ 
    int j;
    sgenrand(4357); 
    for (j=1; j<139; j++) 
    {
        printf("%12u ", genrand());
        if(j%6==0) printf("\n");
    }
    printf("\n");
    getch();
}

... sieht ziemlich voluminös aus.

[Erhard Henkes]

Ich habe diesen (von C nach C++ übertragenen, damit ich keine "mecker" kriege. ) Zahlengenerator
( http://www.math.keio.ac.jp/home2/matumoto/public_html/mt19937int.c )
nun in eine eigene Klasse verpackt und zum Würfel hinzugefügt:

#include <iostream>
#include <iomanip>
#include <conio.h>
#include <cstdlib>
#include <ctime>

/******************************************************************/
class Random_spezial // siehe: http://www.math.keio.ac.jp/home2/matumoto/public_html/mt19937int.c
{
private:
  unsigned seed_;
  const int N;
  const int M;
  const unsigned MATRIX_A;
  const unsigned UPPER_MASK;
  const unsigned LOWER_MASK;
  const unsigned TEMPERING_MASK_B;
  const unsigned TEMPERING_MASK_C;
  unsigned TEMPERING_SHIFT_U(unsigned y) {return (y >> 11);}
  unsigned TEMPERING_SHIFT_S(unsigned y) {return (y <<  7);}
  unsigned TEMPERING_SHIFT_T(unsigned y) {return (y << 15);}
  unsigned TEMPERING_SHIFT_L(unsigned y) {return (y >> 18);}
  static unsigned mt[624];
  static int mti;

public:
  Random_spezial():N(624), M(397), MATRIX_A(0x9908b0df),
                   UPPER_MASK(0x80000000), LOWER_MASK(0x7fffffff),
                   TEMPERING_MASK_B(0x9d2c5680), TEMPERING_MASK_C(0xefc60000),
                   seed_( static_cast<unsigned>(time(0)) )
  {
    static bool seed_flag=0;
    if(!seed_flag)
    {
      sgenrand(seed_);
      seed_flag = true;
    }
  }

  void sgenrand(unsigned seed_)
  {
    mt[0]= seed_ & 0xffffffff;
    for (mti=1; mti<N; mti++) mt[mti] = (69069 * mt[mti-1]) & 0xffffffff;
  }

  unsigned getNum() { return genrand()%(RAND_MAX+1); }

  unsigned genrand()
  {
    unsigned y;
    static unsigned mag01[2]={0x0, MATRIX_A};

    if (mti >= N)
    {
        int kk;
        //if (mti == N+1) sgenrand(seed_);
        for (kk=0;kk<N-M;kk++)
        {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1];
        }
        for (;kk<N-1;kk++)
        {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1];

        mti = 0;
    }
    y = mt[mti++];
    y ^= TEMPERING_SHIFT_U(y);
    y ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
    y ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
    y ^= TEMPERING_SHIFT_L(y);
    return y;
  }
};

unsigned Random_spezial::mt[624];
int Random_spezial::mti = 625;

/******************************************************************/

class Random_aus_Stdlib_geklaut
{
private:
   unsigned int seed_;
   int random()
   {
      return(((seed_ = seed_ * 214013L + 2531011L) >> 16) & 0x7fff);
   }
public:
   Random_aus_Stdlib_geklaut(){ seed_ = static_cast<unsigned>(time(0)); }
   Random_aus_Stdlib_geklaut( unsigned int seed ) { seed_ = seed; }

   int getNum()
   {
       return random();
   }
};

/******************************************************************/

class RandomStdlib // verwendet rand()
{
private:
   const unsigned int seed_;
public:
   RandomStdlib():seed_( static_cast<unsigned>(time(0)) ){}

   int getNum() const
   {
     static bool seed_flag=0;
     if(!seed_flag)
     {
       srand(seed_);
       seed_flag = true;
     }
     return rand();
   }
};

/******************************************************************/

class RandomTestEqual // Test auf Gleichverteilung
{
private:
   int num_;
public:
   RandomTestEqual() : num_(RAND_MAX - 1){};
   int getNum()
   {
      num_++;
      if (num_ >= RAND_MAX) num_ = 0;
      return num_;
   }
};

/******************************************************************/

template<typename T_Generator> class Wuerfel
{
private:
  const unsigned int maxzahl_;
  const unsigned int maxrandom_;
  T_Generator zahlengenerator_; // Template-Typ

public:
  Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl),maxrandom_(RAND_MAX-(RAND_MAX%maxzahl)) {}

  unsigned int wuerfelt()
  {
    unsigned int r;
    do{ r = zahlengenerator_.getNum(); }
      while ( r >= maxrandom_ );
    return ( r % maxzahl_ +1 );
  }
};

/******************************************************************/

int main()
{
  const unsigned long long Serie     = 3;
  const unsigned long long Versuche  = 30000000;
  const unsigned int limit           = 200;
  const unsigned int moeglichkeiten  = 6;

  Wuerfel<RandomTestEqual>  w0a(moeglichkeiten);
  Wuerfel<RandomTestEqual>  w0b(2);
  Wuerfel<RandomStdlib>     w1a(moeglichkeiten);
  Wuerfel<RandomStdlib>     w1b(2);
  Wuerfel<Random_aus_Stdlib_geklaut>  w2a(moeglichkeiten);
  Wuerfel<Random_aus_Stdlib_geklaut>  w2b(2);
  Wuerfel<Random_spezial>   w3a(moeglichkeiten);
  Wuerfel<Random_spezial>   w3b(2);

  unsigned long long H[moeglichkeiten+1];

  for(unsigned long long i=1; i<Serie+1; ++i)
  {
    for(unsigned int j=0; j<moeglichkeiten+1; ++j) H[j] = 0;

    for(unsigned long long k=1; k<Versuche+1; ++k)
    {
      unsigned int wurf = w3a.wuerfelt(); // hier wird gewürfelt

      if(Versuche<limit) std::cout << wurf << " ";
      ++H[wurf];
    }

    for(unsigned int c=1; c<moeglichkeiten+1; ++c)
    {
      std::cout << std::endl << c << ": " << H[c] << " " 
                << std::setprecision(7)
                << 100 * static_cast<float>(H[c]) / Versuche << " %";
      H[0] += H[c];
    }
    std::cout << std::endl << "Wuerfe insgesamt: " << H[0] 
              << std::endl << std::endl;
  }
  getch();
}

@Volkard: geht die Zeile

unsigned getNum() { return genrand()%(RAND_MAX+1); }

in der ersten Klasse in Ordnung? Da es sich sowohl bei RAND_MAX als auch bei der von genrand() produzierten höchsten Zahl um Zweierpotenzen-1 handelt, könnte das gehen, oder mache ich da einen Denkfehler? Ansonsten müsste ich allen Klassen noch ein Attribut random_number_max spendieren, das man dann im Würfel verarbeiten müsste.

Bezüglich der Gleichverteilung hat rand() bzw. die geklaute rand() gegenüber dieser wahrlich komplizierten Variante die Nase deutlich vorne:
________________

Würfelversuche mit Binärwürfel (30.000.000 Würfe):

w1b und w2b:
49.999%
50.001%

w3b:
49.995%
50.005%
________________

Das kann noch an einem Fehler meinerseits liegen, oder ist rand() wirklich die beste Funktion für einen Würfel?

[PAD]

Habe hier eine Seite gefunden die sich mit Zufallszahlengeneratoren auseindersetzt

http://www.agner.org/random/

Ist interessant und informativ

[Erhard Henkes]

Danke für den Link! Sehr interessant.