015
23.08.2005, 14:01 Uhr
virtual
Sexiest Bit alive
(Operator)
|
@Crack
Ich möchte mein Post von vorhin dahingehend präzisieren, daß der Algorithmus dann benutzbar ist, wenn unter und obergrenze nah beieinanderliegen.
Ich möchte nochmal kurz auf das Problem speziell bei kleinen Zahlen zusprechen kommen, also zB eine Würfelsimulation:
Nimmt man vereinfachend an, daß RAND_MAX=9 sei, also der Zufallsgenerator Zahlen zwischen 0 und 9 produziert, so ist sofort einleuchtend, daß diese Modulovariante zu Problemen führt:
| C++: |
int wuerfel() {
return rand()%6 + 1;
}
|
Der grund: Folgende Tablle zeigt in der ersten Spale den Rückgabewert von rand und in der zweiten Splate den von wuerfel:
| Code: |
0 1
1 2
2 3
3 4
4 5
5 6
6 1
7 2
8 3
9 4
|
Man erkennt leicht, daß also die zahlen 1-4 mit 20% Wahrscheinlichkeit, die Zahlen 5-6 nur mit 10% wahrscheinlichkeit gewürfelt werden.
Dieses Problem kann stärker und weniger stark ausgeprägt sein: Ist n die Anzahl der Würfelflächen, dann
1. gibt es überhaupt kein Problem, wenn (RAND_MAX+1) ein Vielfaches von n ist
2. wird das Problem größer, je größer der Quotient von n/RAND_MAX ist
3. wird das Problem kleiner, je kleiner der Quotient von n/RAND_MAX ist
Letztlich wird man mit der Modulo variante bei einem realistischen RAND_MAX=2,1 Milliarde und m=6 meistens keine messbaren Probleme bekommen. Dh für triviale Anwendungen, wo eben n/RAND_MAX "klein" ist, hat man auch keine Probleme.
Die von Crack angegegebene Variante ist sinnvoll für kleine n. Je größer n wird, desto heftiger ist jedoch ihr versagen.
Man kann IMHO folgende Lösung nehmen: man Schreibt n als eine Summe von zweierpotenzen auf. Etwa: 6 = 4+2
Dann geht man hin und brechnet den Wuerfel so:
| C++: |
int wuerfel() {
return rand()%4 + rand()%2 +1;
}
|
Das geht aber nur für n < RAND_MAX. Ist n>RAND_MAX muß man andere Strategien fahren.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
machs halt so:
benutze die CPP Tags selber!
