Würfeln

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?

volkard

volkard schrieb:

Erhard Henkes schrieb:

@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?

oh, konnteste nicht finden. heißt twister und nicht twin. den satz "Four times faster than rand()" kannste auch vergessen. nicht auf normalen prozessoren. aber vorzüge hat er ja trotzdem noch. ne saulange periode.

kein c++-code.
aber krasses c!
http://www.math.keio.ac.jp/home2/matumoto/public_html/mt19937int.c
kriegst bestimmt viel mecker, wenn du nicht die #defines wegmachst und so.

Erhard Henkes

@Volkard:
Danke für den Link.

@all:
Ich habe das Konzept 2 von Marc++us bezüglich der Template-Würfel-Klasse mal probeweise umgesetzt. Umschaltung zur Laufzeit geht jetzt nicht mehr (Nachteil). Diese Lösung gefällt mir nun dennoch besser, da die Aufgaben "(Zufalls)Zahlen generieren und ausgeben" und "Verteilung glätten / Umsetzen auf maximale Augenzahl / Augenzahl ausgeben" auf zwei Klassen verteilt wurden. Damit ist der Würfel nicht mehr fest an rand() gekettet. Das ist der Hauptvorteil. Die Klasse zur Erzeugung von Zufallszahlen mit rand() besteht jetzt nur aus einer Funktion. Ich habe bewusst seed_flag nicht zum Attribut (war das ein Vorschlag von Volkard?) gemacht, da Marc++us und Shade vorgeschlagen haben, dieses Flag lokal in der Funktion, die es braucht, zu setzen.

So jetzt könnt ihr den Entwurf wieder zerfetzen :

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

class RandomStdlib // verwendet rand()
{ 
public: 
   int getNum() const
   { 
     static bool seed_flag=0;
     if(!seed_flag)
     { 
       srand( static_cast<unsigned>(time(0)) );  
       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);  

  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 = w1a.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

Erhard Henkes schrieb:

Ich habe bewusst seed_flag nicht zum Attribut (war das ein Vorschlag von Volkard?) gemacht, da Marc++us und Shade vorgeschlagen haben, dieses Flag lokal in der Funktion, die es braucht, zu setzen.

habe nir gewollt, ein seed_flag als attribut zu nehmen.
will aber weiterhin, daß der seed attribut ist!
und ich bin sicher, marc++us und shade unterstützen das auch.

Erhard Henkes

Die Funktion srand(...) hat folgende Signatur: void srand( unsigned int seed );

seed ist hier "static_cast<unsigned>(time(0))"

Diesen Wert vom Typ unsigned int würdest Du also als Attribut der Klasse festlegen? Habe ich das so richtig verstanden:

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();
   } 
};

Wenn ja, warum bitte? Was bringt mir das?
Wenn nein, bitte genauere Erklärung.

volkard

zeig mal die implemetierung der rand().

Erhard Henkes

In der einen Klasse ist getNum() konstant, in der anderen nicht. Das macht doch nichts aus, soweit ich weiß, oder doch?

Erhard Henkes

Volkard: "zeig mal die implemetierung der rand()."

Kann ich leider nicht, ist rand() aus der Standardbibliothek <cstdlib>.

Marc++us

Im Verzeichnis (z.B.) D:\Programme\Microsoft Visual Studio .NET\Vc7\crt\src findest Du eine Datei mit dem Namen "rand.c":

/***
*rand.c - random number generator
*
*       Copyright (c) 1985-2001, Microsoft Corporation. All rights reserved.
*
*Purpose:
*       defines rand(), srand() - random number generator
*
*******************************************************************************/

#include <cruntime.h>
#include <mtdll.h>
#include <stddef.h>
#include <stdlib.h>

#ifndef _MT
static long holdrand = 1L;
#endif  /* _MT */

/***
*void srand(seed) - seed the random number generator
*
*Purpose:
*       Seeds the random number generator with the int given.  Adapted from the
*       BASIC random number generator.
*
*Entry:
*       unsigned seed - seed to seed rand # generator with
*
*Exit:
*       None.
*
*Exceptions:
*
*******************************************************************************/

void __cdecl srand (
        unsigned int seed
        )
{
#ifdef _MT

        _getptd()->_holdrand = (unsigned long)seed;

#else  /* _MT */
        holdrand = (long)seed;
#endif  /* _MT */
}

/***
*int rand() - returns a random number
*
*Purpose:
*       returns a pseudo-random number 0 through 32767.
*
*Entry:
*       None.
*
*Exit:
*       Returns a pseudo-random number 0 through 32767.
*
*Exceptions:
*
*******************************************************************************/

int __cdecl rand (
        void
        )
{
#ifdef _MT

        _ptiddata ptd = _getptd();

        return( ((ptd->_holdrand = ptd->_holdrand * 214013L
            + 2531011L) >> 16) & 0x7fff );

#else  /* _MT */
        return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
#endif  /* _MT */
}