Zufälle gibt's?! - Funktionen rund um rand, Random und den Zufall

Deine Random-Klasse hat ein schwerwiegendes Problem: Mehrere Instanzen der selben Klasse machen sich gegenseitig kaputt. Man ist bei Pseudozufallszahlen oft darauf angewiesen, dass die Zahlenfolge reproduzierbar ist. Nur ein Beispiel aus der Praxis:

Age of Empires 2 erstellt Zufallskarten. Diese Zufallskarten werden bei einem Netzwerkspiel nicht an alle Spieler vom Host übertragen, sondern es wird nur der (vom Host bestimmte) Seed übertragen, so dass alle Clients diese Karte generieren können. Auch der Karteneditor hat mit Zufall gearbeitet und man konnte den Seed angeben, um die immer wieder gleiche Karte zu generieren ("schau dir mal die Karte 823734 an").

Wenn du jetzt mehrere Instanzen deiner Klasse hast, lebt nicht jede Instanz für sich alleine sondern alle beziehen sich auf das globale srand() und den selben zuletzt generierten Wert. Welchen Wert ich also mit einer Instanz x als nächstes erzeuge hängt davon, was irgendwelche anderen Instanzen in der Zwischenzeit machen, which is bad. Jede Instanz braucht ihre eigenen Werte, damit sie von einander unabhängig sind. Von einander unabhängige Zufallsgeneratoren zu haben ist auch der einzige echte Sinn und Grund, überhaupt eine Klasse dafür zu schreiben.

Aber ein schöner und interessanter Artikel trotzdem, der vor allem für Newbies auf diesem Gebiet viele nützliche Informationen enthält und auch schön aufgemacht mit den Grafiken.

HumeSikkins

aMan schrieb:

Das rand nur Zahlen bis 32768 liefert, hab ich nicht gewusst

Gilt auch nur für einige Compiler/Platformen (VC z.B.). Bei neueren gccs z.B.
ist RAND_MAX identisch zu INT_MAX. Da habe ich schon lustige Bugs gesehen, wie z.B. den:

// random floating point number in the range [0, 1.0)
inline double drand() {
  return rand()/static_cast<double>(RAND_MAX+1);
}

aMan

HumeSikkins schrieb:

aMan schrieb:

Das rand nur Zahlen bis 32768 liefert, hab ich nicht gewusst

Gilt auch nur für einige Compiler/Platformen (VC z.B.). Bei neueren gccs z.B.
ist RAND_MAX identisch zu INT_MAX. ..

Aja, stimmt..
habs grad getestet..

RollingStones

Klasse Artikel!

volkard

klasse artikel.

Anmerkung 1:
(wie Optimizer, nur ich hab ne weitere begründung)
ein wenig unnett, ist daß die klasse Random nur std::rand() benutzt. von einer klasse würde ich einen eigenen zustand erwarten. das brauche ich gelegentlich, denn code-sequenzen wie

do{
   x1=random(30,50);
   x2=random(30,50);
   x3=random(30,50);
}while(x1*x1+x2*x2!=x3*x3);
//sowas kommt vor, wenn auch nicht bei mathematisch so einfachen suchen wie nach pythagoräischen tripeln. 
tuwasMit(x1,x2,x3);
a=rnd(100);//uih, kann sehr, sehr verfälscht sein! unter umständen kommt in der 
//gesamten random-sequenz nur ein solches tripel vor. 
//dann ist (oh, weh!) a immer gleich.

dem entgegnet man, indem man für solche such-mätzchen eine lokale instanz eines zufallszahlengenerators erzeugt.

Anmerkung 2:

Das Dumme ist nur, dass srand() leider keinen return-Wert hat, die an sich nahe liegende Konstruktion dummy = srand(time(NULL)) verbietet sich daher.

das wäre mir noch kein grund für eine klasse.

bool initRand(){
	srand(static_cast<int>(time(0)));
	return true;
}
int rnd(int min,int max){
	static bool b=initRand();
	return std::rand()%(max-min+1)+min;
}

naja, das versteckte if im lokalen static wäre für mich nutzlose rechenzeitverschwendung und ich würde doch das allseits beliebte randomize(); am anfang der main() aufrufen.

volkard

Erweitern Sie nun noch die Klasse Random um eine Zufallszahlerzeugung für rnd32, also Zufallszahlen im Bereich von 0 bis 4.294.967.296. Das sollte wohl die meisten Wünsche abdecken.

0 bis 4.294.967.295.

volkard

wenn man das prog

int main(){
	for(int i=0;i<5;++i){
		cout<<rnd(0,10000)<<' ';
	}
}

schnell hintereinander startet, passiert

7484 559 5278 4718 3563

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
7487 1306 375 6015 1112

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
7490 2053 8238 7311 1425

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
7490 2053 8238 7311 1425

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
7493 36 3336 1371 1739

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
7493 36 3336 1371 1739

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
7497 783 1198 2668 2052

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
7500 1531 6296 3964 9602

die erste zahl läuft einfach nur mit der zeit schnurstracks aufwärts.

das läßt sich gut ausbügeln mit

srand(static_cast<int>(time(0)));rand();

statt nur

srand(static_cast<int>(time(0)));

und siehe da

621 75 7978 2167 7774

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
1369 5173 9274 2480 1699

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
2116 3035 569 2794 2861

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
2116 3035 569 2794 2861

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
99 8133 4630 343 6788

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
846 5995 5927 656 714

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
1593 1092 7223 970 4640

D:\...l Studio 2005\Projects\tmp\debug>tmp.exe
9577 8956 1283 1283 8567

volkard

mir scheint,
int ignoreBoundary = (RAND_MAX / count) * count;
gent schneller als
int ignoreBoundary = count - (RAND_MAX % count);

die division muß ich eh bezahlen, aber die multiplikation danach brauche ich nicht.

volkard

int rnd_nobias(int lowerbounds, int upperbounds)
würde stark davon profitieren, wenn lowerbounds und upperbounds template-parameter wären, falls das nicht über das ziel hinausschießt.

volkard

statt des arrays geht auch

int verteilung(int x){
      return (x+2)*2/3;
}

funktionen statt arrays für die verteilung werden dann wichtig, wenn man die normalverteilung oder sowas braucht.

volkard

...der Funktionsaufruf kann mit einer gewissen (kleinen) Wahrscheinlichkeit sehr lange dauern. Für Echtzeitanwendungen kann dies problematisch sein.

ja, das ist sehr traurig.
mir ist auch kein weg eingefallen, so eine funktion echtzeitfähig zu machen.
naja, für den von die zitierten zufallszahlengenerator könnte man einfach alle werte für count ausmessen. sollte nur wenige wochen dauern.
ich weiß bisher so viel:
wenn count<3 muß man schlimmstenfalls 1-mal raten
wenn count<29 muß man schlimmstenfalls 3-mal raten
wenn count<145 muß man schlimmstenfalls 4-mal raten
wenn count<683 muß man schlimmstenfalls 5-mal raten
wenn count<1093 muß man schlimmstenfalls 6-mal raten
wenn count<1693 muß man schlimmstenfalls 7-mal raten
wenn count<1928 muß man schlimmstenfalls 8-mal raten
wenn count<2979 muß man schlimmstenfalls 9-mal raten
wenn count<3641 muß man schlimmstenfalls 10-mal raten
wenn count<4097 muß man schlimmstenfalls 11-mal raten

volkard

[cpp]if ((count - 1) & count == 0)[/cpp]

if (((count - 1) & count) == 0)

volkard

in

static unsigned int rnd32() 
   { 
      static Random dummy; 
      int rnd1 = rand(); 
      int rnd2 = rand(); 
      int rnd3 = rand(); 
      unsigned int bigrnd = ((rnd1 & 0x03) << 30) + (rnd2 << 15) + rnd3; 
   }

fehlt das return.

Ohne jetzt den ganzen Artikel gelesen zu haben, wird beim Zuschneiden mit Modulus nicht die Gleichverteilung verletzt? Bei einer Zufallszahl zw 0 und 32767 und der Modulus 6 Rechnung kommt die 1 einmal häufiger vor. Bei größeren Zahlen als 6 wird die Verteilung noch mehr verletzt.

Da muß man zw Geschwindigkeit und Gleichverteilung (zB. mit double 6/32767 multiplizieren) gewichten.

CStoll

xxxx schrieb:

Ohne jetzt den ganzen Artikel gelesen zu haben

Vielleicht solltest du das mal nachholen Der ganze Artikel dreht sich genau um das Thema, wie man die Gleichverteilung der Zufallswerte retten kann.

Oh.

Toa

Weiß nicht ob das hier her passt aber :

Eine Zufalls Zahl von 1 bis 8 zb bekommt man ja durch :

rand() % 8 + 1;

Wie kann ich Sagen das manche Zahlen Wahrscheinicher sind als andere?
Damit meine ich das zb die 3 öfters kommt als die 5 oder 8.

MFG Toa

MFK

Indem du z.B. ein Ergebnis-Array mit den gewünschten Verteilungen erstellst und die ermittelte Zufallszahl als Index auf dieses Array benutzt.

Wenn du nichtganzzahlige Verteilungen willst, musst du rechnen.

leider gibts den link
http://www.ma.utexas.edu/documentation/nr/bookcpdf/
nicht mehr