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

[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.

[xxxx]

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.

[xxxx]

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.

[weg]

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

[Contor]

kennt jemand die lineare kongruenz? kann mir jemand was dazu sagen ?
komme da nicht weiter !!!

[Michael E.]

Hast du eine konkrete Frage?

Der allgemeine Aufbau eines linearen Kongruenzgenerators wird in einem anderen Artikel erläutert.

[Zitro]

Marc++us schrieb:

#include <iostream>
using namespace std;

int main()
{
   for (unsigned u = 0; u <= RAND_MAX; u++)
   {
      cout << u << "\t" << u % 3 << endl;
   }
   return 0;
}

Am Anfang geht's noch sauber los:

0   0
1   1
2   2
3   0
...

aber am Ende ist ein kleines Problem vorhanden:

32762   2
32763   0
32764   1
32765   2
32766   0
32767   1

Es geht nicht auf! Der größtmögliche Wert 32767 – der Zufallszahlengenerator schneidet wegen &0xffff alles darüber ab – wird durch das Modulo 3 auf 1 gesetzt. Sie können sich das wie das Ablegen von Kugeln vorstellen, man legt immer reihum in die drei Töpfe; zählt man am Ende die Kugeln in den drei Töpfen 0, 1 und 2, so liegt diese Anzahl von Kugeln pro Topf vor:

Topf 0:   10923   33,33435%
Topf 1:   10923   33,33435%
Topf 2:   10922   33,33130%

Problem gelöst...
Bei den Modulo-Rechnungen mit nicht 2er Potenzen einfach in der for den Maximalwert - in dem Fall RAND_MAX - mit dem selben Modulo berechnen und addieren:

#include <iostream>

using namespace std;

int main()
{
   for (unsigned u = 0; u <= RAND_MAX + (RAND_MAX % 3); u++) // <-
   {
      cout << u << "\t" << u % 3 << endl;
   }
   cin>>ende;
   return 0;
}

Oder RAND_MAX mit dem selben Modulo berechnen, +1 und dann subtrahieren:

#include <iostream>

using namespace std;

int main()
{
   for (unsigned u = 0; u <= RAND_MAX - ((RAND_MAX % 3)+1); u++) // <-
   {
      cout << u << "\t" << u % 3 << endl;
   }
   return 0;
}

Damit sind alle "Töpfe" gleich voll und man schließt eine ungleiche "Prozentuale Zieh-Chance" aus.

Jedoch wird die häufigkeit der wiederholung damit beeinflusst.

Ergibt das überhaupt Sinn?

MfG
C++ Newbe, Zitro

[SG1]

Zitro schrieb:

Ergibt das überhaupt Sinn?

Nein. RAND_MAX kannst Du nicht ändern.

[Swordfish]

@Marc-us sagte in Zufälle gibt's?! - Funktionen rund um rand, Random und den Zufall:

   srand(static_cast<int>(time(NULL)));  // <-- Neu

Der cast sollte imho nach unsigned lauten.

[hustbaer]

@Zitro
Nö das ergibt keinen Sinn.

Was man dagegen machen kann...
Wenn man die Zahlen von 0...RAND_MAX auf N Töpfe aufteilen will, dann kann man

auto const x = (RAND_MAX - N + 1) / N; // Annahme: RAND_MAX >= N - 1

rechnen, dann alle Zufallszahlen r < x verwerfen, und bei den übrigbleibenden r % N als Topfnummer verwenden.

Abgesehen davon... dieser Thread ist von 2007 und durch die neuen RNG Klassen von C++11 auch eindeutig veraltet. Also wozu ausgraben?

[Swordfish]

@hustbaer für Zeh ist es nicht veraltet.

[hustbaer]

@Swordfish Zeh?