32-Bit Zufallszahl...

[Cocaine]

Wieso? Die Rands sind durchnummeriert, sollen also separate Aufrufe von rand() sein - damit sind (theoretisch) alle Zahlen gleich wahrscheinlich.

Problem ist dabei lediglich die übliche Verwendung von rand():
Als Bezug wird oft die Zeit benutzt (srand(time(0));), allerdings unterscheiden sich dann kurz aufeinanderfolgend generierte Zufallswerte in den niedrigen Bits oft nur geringfügig.
Willst du also "wirklich zufällig" verteilte Werte, benutz die Boost Library.

[Dr. von Rosenstein]

Kann aber keine andere Library verwenden, weil mein Übungsgruppenleiter das Teil an den Kisten an der Uni komplilieren können muß. Aber ich glaub ihr habt mich immernoch net verstanden. Die Zahlen sind schon irgendwie zufällig. Nur Werte mit WENIGEN Stellen werden gewaltig unterdrückt. Weil das zu mehrere Zufallszahlen gleich Null sein müssten. Aber eigentlich ist es auch egal. Muß ja net das non plus ultra werden mein Code, hauptsache er funzt. Die Zufallszahlen sind eh nur für Test zwecke da. Hat mich nur persönlich interessiert. Falls noch jemand ne andere Idee hat, ich les alles. Danke jedenfalls...

[Walli]

Cocaine schrieb:

Wieso? Die Rands sind durchnummeriert, sollen also separate Aufrufe von rand() sein - damit sind (theoretisch) alle Zahlen gleich wahrscheinlich.

Eben nicht. Wenn er 5 rand()-Ergebnisse addiert dann sinkt die Möglichkeit niedrige Zahlen zu erhalten erheblich. Eine 0 als Ergebnis wäre dann schon beinahe unmöglich.

Cocaine schrieb:

Problem ist dabei lediglich die übliche Verwendung von rand():
Als Bezug wird oft die Zeit benutzt (srand(time(0));), allerdings unterscheiden sich dann kurz aufeinanderfolgend generierte Zufallswerte in den niedrigen Bits oft nur geringfügig.

Ehm, dir ist klar, dass man den seed nur einmal im Programm initialisiert?

[DasPinsch]

hmm was ist dein problem??

angenommen du hast zB ne 8-bittige random zahl. wahrscheinlichkeit auf ne 0 ist 1/2^8. jetzt nimmst du eine 16-bittige random zahl. wahrsheinlichkeit auf ne 0 ist 1/2^16 . wenn du jetzt die 16-bittige zahl durch 2 8-bittige zahlen konstruierst, müssen, damit als gesamtzahl eine 0 entsteht, beide 8-bittige Zahlen 0 sein (wie du schon richtig erkannt hast). die wahrscheinlichkeit ist also (1/22 = 1/(2^8*2 = 1/2^16 ! (ist also die gleiche (natürlich kleine) wahrscheinlichkeit, eine 0 zu bekommen, als wenn man sofort eine 16-bittige random zahl genommen hätte)

[operator void]

MaSTaH schrieb:

Eben nicht. Wenn er 5 rand()-Ergebnisse addiert dann sinkt die Möglichkeit niedrige Zahlen zu erhalten erheblich. Eine 0 als Ergebnis wäre dann schon beinahe unmöglich.

Addieren ja, aber | sollte doch nichts an der Wahrscheinlichkeit ändern. Naja, siehe oben. Wenn man nebenbei zuguckt, wie Neulinge in IRC-Channels fertig gemacht werden, ist man natürlich zu langsam

[Christoph]

Ob | oder + macht keinen Unterschied, wenn die eine 8-Bit-Zahl um 8 Bits nach links geshiftet wurde.

[peterchen]

Du sollst die 5 Ergebnisse ja nicht "einfach" addieren - sondern die Bits entsprechend bestücken. Das geht wunderbar, wenn die von rand() erzeugten Zufallszahlen voneinander unabhängig sind - was sie natürlich in den üblichen Implementationen nicht sind.

Am ehesten (wenn man keine Zeitprobleme bekommt) rand() 64x aufrufen und immer nur das [edit]zweit-[/edit]höchste Bit verwenden.

[Walli]

Also ich glaube nicht, dass die bitweise aneinandergebastelten Zahlen wirklich gut verteilt sind.

[Taurin]

MaSTaH schrieb:

Also ich glaube nicht, dass die bitweise aneinandergebastelten Zahlen wirklich gut verteilt sind.

Warum? Angenommen, du willst eine 16-Bit-Zufallszahl A aus zwei 8-Bit-Zahlen B und C
zusammen setzten. Wenn du in die oberen 8-Bit von A die Bits von B einsetzt und
in den niederen teil die von C hast du keine überscheidungen. Jede der 2^16 von A
möglichen Kombinationen kann genau einmal angenommen werden.

Stell dir vor, du hast zwei 10-seitige, unterscheidbare Würfel, mit den Zahlen 0..9 Wenn du würfelst und beide Zahlen aneinander hängst, bekommst du eine Zahl
zwischen 0 und 99. Und du hast genau 100 Kombinationen dieser beiden Würfel. D.h.
jede Kombination wird genau auf einem Ergebnis abgebildet -> Alle Ergebnisse sind
gleich wahrscheinlich (wir haben ein Laplace-Experiment).

[Walli]

Aber dabei lässt du ausser Acht, dass es sich bei rand() um keinen wirklichen Zufall handelt. Naja, im Zweifelsfall testet man die Verteilung per Programm.

[peterchen]

@Taurin:
Eine übliche implementationen von rand() ist

rnd[n+1] = (rnd[n] * a + b) % c;

was bei geschickter Wahl von a, b, und c recht gute "eindimensionale" Zufallszahlen bringt. (Leider ist c häufig eine Zweierpotenz, was das ganze schnell aber unsäglich schlecht für Statitische Anwendungen macht)

Jedoch sind Tupel aufeinanderfolgender ZZ nicht mehr gleichverteilt, da rnd[n+1] eindeutig durch die vorherige Zahl bestimmt ist.

Stell dir einfach vor: du nimmst zwei aufeinanderfolgende ZZ als (x,y) - Koordinaten, un zeichnest immer einen Punkt ein. Große Teile der Fläche werden gar nicht abgedeckt, da es zu einer x-Koordinate immer nur eine bestimmte y-Koordinate gibt.

m.a.w. die kombinierten Zahlen sind zwar recht gleichmäßig über den Wertebereich verteilt, haben aber eine eindeutige, nicht-zufällige Feinstruktur, und sind z.B. für eine Monte-Carlo-Simulation in der Ebene nichts Wert. Kommt halt immer drauf an, was man so braucht.

Gute Generatoren schalten deswegen einen "Mixer" dazwischen, der die Reihenfolge "aufbricht". (Der Mixer wird von der gleichen Sequenz gefüttert, geht aber erstaunlich gut)

ein Test für die Nahkorrelation von ZZ macht sich obiges Prinzip zunutze: x und y werden auf 1.0 normiert, und es werden die Punkte gezählt, die in den Einheitskreis fallen (x^2+y2 <= 1). Das Verhältnis von "Treffern" zu Gesamtwürfen muß sich der Kreisfläche annähern - oder es ist was faul. Das macht man für (x,y)-Paare, und für Tupel höherer Ordnung (also kreis, Kugel, R4-Kugel usw.).

[peterchen]

@DvR: wofür brauchst du die ZZ denn?

[Dr. von Rosenstein]

Ich soll für die Uni Sortieralgorithmen implementieren. Hört sich einfach, aber das ganze soll in MPI gemacht werden und auf einem Cluster laufen. Ziel ist es festzustellen ab wieviel zu sortierenden Werten das verteilte Rechnen schneller ist als das normale "Ein-Prozessor" Rechnen. Sortiert werden sollen 4 Byte große Zahlen. Also 32-Bit Werte. Die Zufallszahlen sind eigentlich nur dafür da um zu testen ob das Teil richtig rechnet. Die Werte mit denen das Programm später laufen sollen werden von außen eingelesen. Ist also eigentlich garnet so wichtig ob die Werte wirklich zufällig sind. Hät mich halt nur interessiert...

[peterchen]

Ja, für den Zweck issses "fast egal", da kannst du die Teile einfach zusammenbasteln wahrscheinlich ist nicht mal gleichverteilung wirklich wichtig - oder du füllst einfach einen vektor, und nimmst dann std::random_shuffle

[Dr. von Rosenstein]

Aber es ist nur "fast egal", wie du schreibst. Weil es bringt ja nichts wenn in 100 zu sortierenden Zahlen nur 10 verschiedene Werte vorkommen. Eine Kette von gleichen Werten braucht man ja nichtmehr zu sortieren. Gut, so extrem wird es nicht werden, aber im Endeffekt werden es auch ein paar mehr als nur 100 Zahlen sein.
Aber das mit dem std::random_shuffle probier ich mal aus. Wenn ich das richtig verstehe, dann kann ich einfach ein Vektor mir ner for Schleife mit den Werten 1 bis 100 füllen und diese dann durcheinander würfeln? Das würde mir wenigstens garantieren das es keine doppelten gibt...