Zufallsgenerator
-
Original erstellt von Shakareh:
**Laut der FAQ ist die dortige methode aber besser in sachen Zufall, wobei ich mir nich sicher bin ob das beim Kartenmischen nen unterschied macht
**du meinst doch nicht etwa
you should always do it by using high-order
bits, as in
j=1+(int) (10.0*rand()/(RAND_MAX+1.0));
and never by anything resembling
j=1+(rand() % 10);
(which uses lower-order bits)."fall doch, schimpfe ich hiermit den deppen aus, der diese scheiße auch noch in die faq gestellt hat. das ist stand von vor 10 jahren.
-
wer macht nu dem mist aus der faq raus?
die gleichverteilung: mal annehmen, rand() gibt was gleichverteiltes zurück zwischen 0 und 32767. also 32768 verschiedene zahlen.
dann werden bei rand()%10 wohl 3277 zur 0 werden.
dann werden bei rand()%10 wohl 3277 zur 1 werden.
dann werden bei rand()%10 wohl 3277 zur 2 werden.
dann werden bei rand()%10 wohl 3277 zur 3 werden.
dann werden bei rand()%10 wohl 3277 zur 4 werden.
dann werden bei rand()%10 wohl 3277 zur 5 werden.
dann werden bei rand()%10 wohl 3277 zur 6 werden.
dann werden bei rand()%10 wohl 3277 zur 7 werden.
dann werden bei rand()%10 wohl 3276 zur 8 werden.
dann werden bei rand()%10 wohl 3276 zur 9 werden.
beobachtung: die großen zhalen kommen seltener raus.
wie selten? mit weniger als 0.05% abweichung vom soll.
also würde sich ein raumschiff, das ich steuere mit
x+=rand()%3+1; theoretisch langsam nach links bewegen.
praktisch ist mir so ein effekt aber noch nie aufgefallen.also laßt mal gut sein und bei rand()%10 hab kein furchtbar schlechtes gewissen.
probleme gibts bei größeren moduln.
mal annehmen, rand() gibt was gleichverteiltes zurück zwischen 0 und 32767. also 32768 verschiedene zahlen.
dann werden bei rand()%10000 wohl 4 zur 0 werden.
dann werden bei rand()%10000 wohl 4 zur 1 werden.
dann werden bei rand()%10000 wohl 4 zur 2 werden.
...
dann werden bei rand()%10000 wohl 4 zur 2767 werden.
dann werden bei rand()%10000 wohl 3 zur 2768 werden.
...
dann werden bei rand()%10000 wohl 3 zur 9999 werden.ne gewisse ungleichverteilung ist nicht zu vermeiden, wenn man 32768 zahlen auf 10000 zahlen abbilden will. manche werden 4 mal vorkommen und manche drei mal.
das problem liegt darin, daß die 4-er alle zusammeen sind, was ne schlimme schieflage bewirkt.deswegen macht man manchmal gerne
10000.0*rand()/(RAND_MAX+1.0)
das hat den effekt, daß die 4-er recht gleichmäßig übers ganze spektrum verteilt sind.historischer einschub:
die üblichen zufallgeneratoren erzeugen linear congruential sequences und die haben schlimme bitwackler, und zwar im bit n mit der periode 2^n. klar, daß man da nicht rand()%4 nehmen darf.
aber das war mal. heute rechnen die inter mit 32 bit und geben x>>16 raus, was für und den tollen effekt hat, daß die periode in unserem bit0 wohl um 2^16 ist (65536). ausreichend.
daher will ich hier nie mehr hören, daß man fehler kriegt durch die ausschließliche verwendung der unteren bits.
und wie jeder leicht prüfen kann, ist rand()%11 nicht die ausschließliche verwendung der unteren bits und hat ne saulange periode. hat nur das schieflagenproblem.wie könnte man sonst noch dafür sorgen, daß die schieflage von rand()%10000 weg geht? als an was kleinere üben. an rand()%10. mach ich rand()%10, dann hab ich leichte schieflage. und zwar sind die beiden seltenen zahlen die 8 und die 9. (rand()+1)%10 würde die 9 und die 0 zu den seltenen zahlen machen. schieflage ist irgendwie noch da, aber symmetrisch. das raumschiff hat keine flucht-tendenz mehr, die anderen gesetzen als der brownschen molekularbewegung gehorchen.
und was wäre bei 10.0*rand()/(RAND_MAX+1.0) passiert? da wären die beiden seltenen zahlen die 4 und die 9 gewesen. also nicht nur lahmer, sondern auch schiefer als mit ein wenig nachdenk. das schiff würde nach links laufen.daher mein tip: benutze man-pages nur, wenn du in der lage bist, sie zu verstehen.
den effekt von 10.0rand()/(RAND_MAX+1.0) könnte man auch schafen, indem man erstmal %5 nimmt (seltene zahl ist 4) und dann zufällig 5 dazuaddiert oder nicht.
also rand()%5+5*rand()%2; üder bei 10000 eben als rand()%625+625*rand()%16. ist natürlich wieder schieflagenverschiebbar mit (rand()+56)%625+625rand()%16 oder so.man beachte, daß bei rand()%zweierpotenz keine schieflage auftritt. die zweierpotenzen sind nämlich teiler der anahl der zahlen, die rand() zurückliefern kann.
man kann viele tricks anwenden, um zu gleichverteiltem zufall zu kommen. wie wärs damit?
int wuerfel()
{
int x;
do
{
x=rand()%8;
}while(x>=6);
};
man beachte, daß %8 gleichverteilte ergebnisse leifert, weil zweierpotenz und daß die schleife terminiert, weil rand() alle zahlen mal leifert.also folgendes vorgehen bei der auswahl von zufall:
a) erstmal überlegen, wie groß die schieflage bei % ist, und normalerweise ist man hier schon fertig.
b) überlegen, ob man die schieflage von 10.0*rand()/(RAND_MAX+1.0) mag und nehmen.
c) oder in notfällen gehirn einschalten und sich selber was bauen.
und in der praxis überspringe ich stets b).[ Dieser Beitrag wurde am 26.04.2003 um 13:23 Uhr von volkard editiert. ]
-
-
Dein letztes Beispiel hat einen Haken: Es kann wenns dumm kommt extrem lange dauern, ansonsten: so hab ich das eigentlich noch nie betrachtet :). Ein einfaches rand()%x hat für mich bisher immer gereicht - gut zu wissen, dass das in manchen Situationen wo es eine genaue Zufallszahl sein soll so nicht gehen kann.
Was übrigens bei der Kartenverteilung egal ist: Ob nun Spieler #1 öfters den Herz Buben in der Hand hält ist wohl den meisten egal :).
MfG SideWinder
-
Original erstellt von SideWinder:
Was übrigens bei der Kartenverteilung egal ist: Ob nun Spieler #1 öfters den Herz Buben in der Hand hält ist wohl den meisten egal :).verdammt, lies den satz mit den zweierpotenzen!
-
Original erstellt von SideWinder:
Dein letztes Beispiel hat einen Haken: Es kann wenns dumm kommt extrem lange dauernjo. wenns real time sein muß, kann man ja erstmal laufen lassen, bis rand durch ist und gucken, was die längste schleife war.
aber es dürfte wohl zu keinen aussetzern kommen. insbesondere keine, die 100000 takte lang dauert, als keine, die länger dauert als ne seiteneinlagerung von der platte.
man könnte sich auch mit nem rand()%8192 ne große zahl holen, alles über 7776 wegschmeißen (also nur 5%) und wegen 7776==pow(6,5) dann die 5 folgenden würfelwürfe rauslesen.
-
Ich habe den Thread ehrlich gesagt nur überflogen, aber gibt es irgendeinen Grund nicht random_shuffle() zu verwenden?
-
Original erstellt von nman:
gibt es irgendeinen Grund nicht random_shuffle() zu verwenden?nein.
-
Huii..lange am lesen gewesen Volkard, glaube habe deine aussage verstanden
Warum ich es angemerkt habe war halt der grund das ich in nem winzprogramm ebenfalls wuerfele und da mir das manchmal recht komisch vor kam hab ich nen kleinen test eingebaut der 1.000.000 mal wuerfelt - und siehe da ich hatte (zahlen von 1 - 6) abweichungen von bis zu 150.000 mal eine zahl mehr als die andern - gleichmaessig wurde es erst mit der von dir oben erwaehnten zeile aus der faq.
-
Original erstellt von Shakareh:
gleichmaessig wurde es erst mit der von dir oben erwaehnten zeile aus der faq.kannste mir das test-programm geben?
und wann war das ungefähr?
-
hm hab nur noch die "neuere" Variante mit der langen version aus der faq... die "alte" loesung hab ich ueberschrieben als ich die faq durchblaettert habe. Habs mir nochmal so wie ich glaube es gemacht zu haben nachgeschrieben...nu kommt quasi(kleinre abweichungen sind ja normal bei zufaellen *g*)das gleiche raus
*verwirrtis* 
habs nich mehr gefunden aber irgenwo gabs in nem post nen klappezu.gif oder so..wuerde jetzt hier her passen *g* - auf mich bezogen scheints...edit - grrr...warum zum geier hab ich nen englisches tastaturlayout sobald ich hier was tippe....
[ Dieser Beitrag wurde am 28.04.2003 um 12:57 Uhr von Shakareh editiert. ]
