Würfeln

Walli

Erhard Henkes schrieb:

Wie hoch sind die Abweichungen eigentlich bei mechanischen Würfeln, auch ca. 0,1% ?

Theoretisch 0%.
<müll>
Nun muss man aber bei einem Würfel bedenken, dass die Löcher Gewicht umverteilen und Einfluss auf die Aerodynamik haben. Desweiteren ist das Material sicher nicht ganz rein wodurch eine Ungerechtigkeit in der Gewichtsverteilung unvermeidbar ist. Zusätzlich nutzt sich der Würfel nach jedem Wurf ab (ob das gleichmäßig geschieht kann zum Streitpunkt werden) .
</müll>

Marc++us

Zerreissen? Bitteschön... wie bestellt:

wieso ist die Methode "wuerfelt" nicht const?
wieso ist das statische Seed-Flag global in der Klasse und nicht lokal im Ctor? Außer dem Ctor braucht das doch sonst keiner.

volkard

Erhard Henkes schrieb:

Die Differenzen bei der Gleichverteilung liegen jetzt im Promillebereich. Damit sollte man leben können. Wie hoch sind die Abweichungen eigentlich bei mechanischen Würfeln, auch ca. 0,1% ?

verdammt! mach mal "const unsigned int moeglichkeiten = RAND_MAX*0.6;"
deine abweichungen wären ok, wenn sie alle zahlen mal treffen würden, aber abweichungen, die wiederholbar immer die 0 und die 1 bevorzugen, sind schlicht fehler.

operator void

Und die const-Elementvariablen machen das Zuweisen von Würfeln unmöglich.

Erhard Henkes

@Marc++us: Danke für die Ergänzungen, hier die aktuelle Variante:

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

class Wuerfel  
{  
private:
  const unsigned int maxzahl_; 
  const unsigned int maxrandom_; 

public:  
  Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl),maxrandom_(RAND_MAX-(RAND_MAX%maxzahl))
  { 
    static bool seed_flag = 0; 
    if(!seed_flag)
    { 
      srand( (unsigned)time( NULL ) );  seed_flag = true; 
      // std::cout << "seed-flag gesetzt." << std::endl;
    } 
  }  

  unsigned int wuerfelt() const
  {   
    unsigned int r; 
    do{ r = rand(); }  
      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 w(moeglichkeiten), w_binaer(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 = w.wuerfelt();  
      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();  
}

Marc++us

Hättest Du übrigens den Zufallszahlengenerator ausgelagert in eine Klasse, so könntest Du Deinen Würfel mit folgender wunderschöner Testklasse erproben:

class AllNumbersAreEqual
{
private:
   int m_seed;
public:
   AllNumbersAreEqual() : m_seed(RAND_MAX - 1);
   int getNum()
   {
      m_seed++;
      if (m_seed >= RAND_MAX)
         m_seed = 0;
      return m_seed;
   }
};

Dieser Generator erzeugt Dir eine aufsteigende Zahlenfolge von 0...RAND_MAX-1.

Wenn Du diesen Generator in Deine class Wuerfel einbindest und dann einige (N * 6 * RAND_MAX) Male würfelst, MUSS bei der Häufigkeit überall exakt die gleiche Zahl rauskommen.

Wie gesagt, das solltest Du auch mal für einen 60er Würfel testen.

Erhard Henkes

@Marc++us:
Danke für Deine konstruktiven Beiträge, das hilft mir sehr. Ich wollte darstellen, dass der Würfel als einheitliches Objekt selbst die Zahlen generiert. Deinen hier geposteten Testgenerator bauen wir aber sofort mittels eigener Methode "wuerfelt_mit_externem_Generator()" in den Würfel ein, damit kann man nun wählen, ob man mit rand() oder zu Testzwecken mit dem "Gleichverteiler" arbeiten will. Klasse Idee! Weiter so.

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

class AllNumbersAreEqual 
{ 
private: 
   int m_seed; 
public: 
   AllNumbersAreEqual() : m_seed(RAND_MAX - 1){}; 
   int getNum() 
   { 
      m_seed++; 
      if (m_seed >= RAND_MAX) 
         m_seed = 0; 
      return m_seed; 
   } 
};

class Wuerfel  
{  
private:
  const unsigned int maxzahl_; 
  const unsigned int maxrandom_; 
  AllNumbersAreEqual zahlengenerator_;

public:  
  Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl),maxrandom_(RAND_MAX-(RAND_MAX%maxzahl))
  { 
    static bool seed_flag = 0; 
    if(!seed_flag)
    { 
      srand( static_cast<unsigned>(time(0)) );  seed_flag = true; 
      // std::cout << "seed-flag gesetzt." << std::endl;
    } 
  }  

  unsigned int wuerfelt() const
  {   
    unsigned int r; 
    do{ r = rand(); }  
      while ( r >= maxrandom_ ); 
    return ( r % maxzahl_ +1 );  
  }

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

int main()  
{  
  const unsigned long long Serie     = 1;  
  const unsigned long long Versuche  = 60000000;  
  const unsigned int limit           = 200;  
  const unsigned int moeglichkeiten  = 60;  

  Wuerfel w(moeglichkeiten), w_binaer(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 = w.wuerfelt_mit_externem_Generator(); 
      // unsigned int wurf = w.wuerfelt();
      // unsigned int wurf = w_binaer.wuerfelt();       

      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:
Ich habe das mit 0.6*RAND_MAX und auch mit anderen Einstellungen getestet und keine Bevorzugung von 0 und 1 (weder die ersten beiden Zahlen des Würfels noch die niedrigste und höchste Zahl der erzeugten Zahlenreihe) gesehen. Daher meine Frage: Wie zuverlässig ist rand() wirklich. Eine exakte Gleichverteilung habe ich damit bisher nicht geschafft, eine Häufung bei gewissen Zahlen aber auch nicht, dafür haben wir doch maxrandom_ eingebaut. Vielleicht könntest Du mir noch einen konkreten Tipp geben.

Marc++us

Argl.

Dein Klassenentwurf mit der Fallunterscheidung der Generatoren ist furchtbar.

Du darfst Dir einen Entwurf aussuchen:

Klassisch mit Interface

Du erzeugst eine abstrakte Interfaceklasse "IRandomGenerator" (da will Volkard schon seit 6 Stunden hin) mit einer rein virtuellen "getNumber"-Methode.

Davon leitest Du zwei Klassen AllNumbersAreEqual und RandFromStdlib ab (die letztere implementierst Du mit Hilfe von srand und rand).

Unter Umständen ist es hilfreich, die Konstant RAND_MAX innerhalb der Klasse IRandomGenerator noch einmal zu "spiegeln", also dort unterzubringen. Du solltest Dich nicht mehr direkt auf RAND_MAX aus stdlib abstützen.

Die Klasse Wuerfel bekommt einen Zeiger auf eine Instanz IRandomGenerator verpasst, dem Du jeweils eine mit new erzeugte Instanz übergeben kannst:

void Wuerfel::changeGenerator(IRandomGenerator* pRG)
{
   assert(pRG);
   delete m_RandomGenerator = pRG;
}

Du kannst nun mit w1.changeGenerator(new AllNumbersAreEqual) einen anderen Generator setzen.

Achtung, die obige Implementation hat den Nachteil, daß man eine gestacktes Objekt übergeben kann. Eine alternative Implementation, die das vermeidet, überlesen wir dem geneigten Leser als Übungsaufgabe.

Der Ctor initialisiert m_RandomGenerator mit einem Objekt der Stdlib-Klasse.

Random-Policy mit Hilfe von Templates

Du erstellst zwei Klassen AllNumbersAreEqual ohne gemeinsame Oberklasse, getNumber ist nicht virtual. Ansonsten gleiche Signatur der public-Methoden.

Wuerfel wird eine Template-Klasse und bekommt einen Template-Parameter <typename Generator> verpasst. Die Ziehung ruft nun Generator.getNumber auf.

Pro/Cons:
1+ zur Laufzeit umschaltbarer Generator
1- etwas inkonsequent, daß man den Testfall explizit umschalten muß, eigentlich könnte man ja gleich eine Testklasse von Würfel nehmen und die Exe als Testfall-Exe compilieren
2+ nicht verwendete Generatoren bleiben außen vor, etwas schlanker
2- nicht zur Laufzeit umschaltbar

Erhard Henkes

Dein Klassenentwurf mit der Fallunterscheidung der Generatoren ist furchtbar.

Warum genau? Ich bin noch nicht völlig überzeugt, dass man hier wirklich solche Geschütze auffahren sollte. Es geht hier nur um einen winzigen Würfel. Ein so harmloses einheitliches Objekt (einfach nur ein Zahlenerzeuger) sollte man doch nicht dermaßen aufspalten und aufblähen!
Bei meinem Würfel sieht man im Hauptprogramm "wer" würfelt. Das erkennt man sofort am Namen der Methode (ansonsten hätte ich ein internes Flag verwendet, dann steht da aber nur wuerfelt() und keiner weiß welcher Generator genau.). Die Umschaltung zur Laufzeit ist problemlos durch Wechseln der Methode möglich. Außerdem soll zum Schluss nur eine Methode verbleiben. Das war nur ein Test, für den man eine Klasse, eine Member-Variable und eine -Funktion eingebaut hat, die man ruckzuck wieder verschwinden lassen kann. Auf Zeiger als Member und new/delete werde ich solange verzichten, wie es geht. Das würde nur unnötigen Overhead schaffen wegen der notwendigen Vermeidung flacher Kopien.

Es kann ja sein, dass rand() nichts taugt, was ich bisher nicht überzeugend feststellen konnte (mit 0,1% Abweichung kann man meiner Meinung nach in der Praxis problemlos umgehen.)

Marc++us

Eine andere Methode, die das gleiche macht, nur anders? Was ist, wenn Dir hier ein Fehler unterläuft und Du die beiden Methoden aus Versehen unterschiedlich machst?

Und wenn Du 4 "wuerfeln()"-Aufrufe hast, mußt Du die dann alle durch den anderen Methodennamen ersetzen?

Die Test-Methoden für statistische Tests auch wieder verschwinden lassen? Du mußt also in Zukunft nie mehr Tests machen?

Frage: verwendest Du Konstanten im Quelltext? Warum? Wieso verwendest Du folglich bei Methoden nicht den gleichen Lösungsansatz mit globalem Austausch? Wenn Dir die Argumentation mit Konstanten einleuchtet, muß Sie Dir auch bei Methoden einleuchten.

Ich sehe ein, daß Du keinen Interface-Overhead spendieren willst. Ok, dann nimm Lösung 2) mit den Templates. Kapsele rand/srand in einer Klasse - das kannst Du sowieso immer wieder brauchen. Mache aus Wuerfel ein Template-Klasse und Du kannst dann global den Generator durch den Testgenerator austauschen, _ohne_ Gefahr, daß der Testfall nur 99% identisch ist zum scharfen Fall.

volkard

Erhard Henkes schrieb:

@Volkard:
Ich habe das mit 0.6*RAND_MAX und auch mit anderen Einstellungen getestet und keine Bevorzugung von 0 und 1 (weder die ersten beiden Zahlen des Würfels noch die niedrigste und höchste Zahl der erzeugten Zahlenreihe) gesehen.

ach, du willst meinen beiträgen gar nicht folgen. meinetwegen. kannst alles wichtige erstmal in genau diesem thread nachlesen.

Marc++us

Ich kann ehrlich gesagt auch nicht folgen. Die jetzige Ziehungsvariante blendet die Fragmente am oberen Rand doch aus? Ich habe zwar jetzt die Formel nicht geprüft ob sie für andere Werte auch die richtige Grenze für das Ende der Maskierung errechnet, aber sonst ändert sich doch nichts an der Vorgehensweise.

volkard

ups, ausblenden hat er ja angenommen. nur den zufallszahlengenerator als klasse (so mit status als attrubut) noch nicht.
die absolute abweichung hat mit der wurzel der versuche zu wachsen. damit hat wohl die relative genauigkeit den selben faktor.
afair kommste mit 6e6 versuchen vermutlich auf 1e6+-1e3 pro zahl.
willste messergebnisgenauigkeit verzehnfachen, mußte leider 100mal mehr versuche machen.

Marc++us

volkard schrieb:

willste messergebnisgenauigkeit verzehnfachen, mußte leider 100mal mehr versuche machen.

Die Nacht ist noch jung.

volkard

Erhard Henkes schrieb:

Die Differenzen bei der Gleichverteilung liegen jetzt im Promillebereich. Damit sollte man leben können. Wie hoch sind die Abweichungen eigentlich bei mechanischen Würfeln, auch ca. 0,1% ?

sorry. das da hat mich schwer verwirrt. ich war mich sicher, daß du sachen wie die ungleichung von tschebyscheff und das gesetz der großen zahl kennst.
also so mathe-sachen, die sagen, daß die relativen wahrscheinlichkeiten mit steigender anzahl der versuche sich langsam angleichen. und daher hab ich deine messung von 0.1% fehler für den lektronischen würfel dahingehend interpretiert, daß dein würfel ne echte schieflage hat.

Erhard Henkes

@Marc++us: Deine Argumente stechen, ich werde Vorschlag 2 daher als Alternative in Betracht ziehen. Zunächst möchte ich aber Volkard's Einwände kapieren.

@Volkard: Doch ich möchte verstehen, was Du mir mitzuteilen versuchst, vielleicht habe ich das Entscheidende noch nicht erfasst. Bezüglich der Bevorzugung der Zahlen 0 und 1 bei einem 6er-Würfel (in meinem Sourcecode übrigens 1 und 2, aber das ist nebensächlich) habe ich doch den Vorschlag von Marc++us übernommen und das größte Vielfache der höchsten Augenzahl unterhalb RAND_MAX minus 1 als Obergrenze für die erzeugten Zahlen vorgegeben. Dabei bin ich davon ausgegangen, dass die Gleichverteilung damit gewährleistet ist. Marc++us hat meiner Umsetzung, wenn ich das richtig verstanden habe, zugestimmt. Könnte aber noch ein Fehler drinnen stecken. Mir ist bisher aber noch keine systematische Verzerrung aufgefallen ( bei Einsatz von Dev-C++ 4.9.8.2, vielleicht gibt es da Unterschiede bezüglich rand() bei anderen Compilern ).

/EDIT: scheint ein Missverständnis gewesen zu sein, dennoch die Frage:
ist die nachstehende Variante günstiger? Ich denke nein.

Man kann auch auf

dRand = rand(); 
dRand /= RAND_MAX; 
dRand = dRand * 6 + 1; 
nWuerfel = (int) dRand;

umstellen, wenn das homogenere Ergenisse liefert. Ich werde es ausprobieren, da Dir das besser gefallen hat.

Erhard Henkes

und daher hab ich deine messung von 0.1% fehler für den lektronischen würfel dahingehend interpretiert, daß dein würfel ne echte schieflage hat.

Mir gefällt diese Abweichung nicht, ich würde sie gerne verringern. Liegt das an rand() oder an meinem Sourcecode? Wenn ich den Binärwürfel einsetze, ist die Abweichung deutlich geringer, aber das liegt daran, dass mehr Random-Zahlen zu einer Zahl zugeordnet werden.

Marc++us

Erhard Henkes schrieb:

Man kann auch auf
dRand = rand(); 
dRand /= RAND_MAX;        // (1)
dRand = dRand * 6 + 1;    // (2a)
nWuerfel = (int) dRand;   // (2b)
umstellen, wenn das homogenere Ergenisse liefert. Ich werde es ausprobieren, da Dir das besser gefallen hat.

Kann der Wechsel der Zahlendarstellung etwas daran ändern, daß es 32768 verschiedene Werte gibt? Es gibt ab der Stelle (1) eben 32768 unterschiedliche double-Werte statt int-Werte. Haben wir was geändert?

Ändert die Skalierung in den Schritten (2a) und (2b) etwas daran, daß 32768 KEIN ganzzahliges Vielfaches von 6 ist?

Also was bringt der obige Rechentrick für die Häufigkeit?

Btw, Du kannst Deine Implementation mit dem Testgenerator doch prüfen. Wenn Du mit dem vorgestellten Testgenerator richtige Gleichverteilung erhälst, liegt es ausschließlich an rand().[aber wie gesagt: Du mußt dann genau n * 6 * 32768 mal ziehen]

Erhard Henkes

Mit dem Testgenerator läuft das spitzenmäßig.
30.000.000 Versuche ergeben jeweils 5.000.000 einer Zahl bei 6 Möglichkeiten.
Zur Kontrolle:

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

Gegenprobe:
1: 5.000.763
2-6: 4.999.847 bzw. 4.999.848

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

Deine Vorgehensweise funktioniert also prächtig. q.e.d.
Dann wird dieser Teil mit dem Modulo und dem Abschneiden der oberen Werte jetzt abgehakt.

Übrigens:
"Du mußt dann genau n * 6 * 32768 mal ziehen"
30.000.000 Versuche ergibt da keine natürliche Zahl. Dennoch geht es perfekt.

Ansonsten zum Konzept: "Do The Simplest Thing That Could Possibly Work" (XP-Spruch) http://xp.c2.com/DoTheSimplestThingThatCouldPossiblyWork.html

@Volkard: gut, nachdem dies geklärt ist, wie funktioniert der "mersenne prime twin generator" zum Erzeugen von Zufallszahlen, oder genauer: wo finde ich den C++-Code zum Einbinden in meinen Würfel?

volkard

Erhard Henkes schrieb:

ist die nachstehende Variante günstiger? Ich denke nein.
Man kann auch auf
dRand = rand(); 
dRand /= RAND_MAX; 
dRand = dRand * 6 + 1; 
nWuerfel = (int) dRand;
umstellen, wenn das homogenere Ergenisse liefert. Ich werde es ausprobieren, da Dir das besser gefallen hat.

nee, die gefällt mir gar nicht gut. dem rechnen mit fließkommazahlen traue ich nicht.
sollte nicht bei jedem compiler ne funktion MulDiv dabei sein, die zwei 32-bitter plutimiziert und das ergebnis durch nen weiteren dividiert?