32-Bit Zufallszahl...

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