Ungewollte Größen bei Ausgabe von Zufallszahlen

SeppJ

Mitleid schrieb:

SeppJ schrieb:

...Zur Not kann ich mir sogar mein eigenes, standardkonformes rand() schreiben, welches mit Absicht eine Implementierungsschwäche enthält.

Da dein "geschwächtes" rand() die Werte ebenfalls reproduzierbar berechnen MUSS um standardkonform zu sein, hast du an der Stelle aber nichts gewonnen.

uint32_t interner_zustand = 1;
bool nimm_dumme_werte;

void my_srand(uint32_t seed)
{
 interner_zustand=seed;
 if (seed == 123456789) 
  nimm_dumme_werte = true;
}

uint32_t my_rand()
{
 if (!nimm_dumme_werte) 
  return interner_zustand = 1664525*interner_zustand + 1013904223;
 return (interner_zustand = 1664525*interner_zustand + 1013904223) % 5;
}

Sollte standardkonform sein. Wenn du etwas findest, was dagegen spricht, bessere ich gerne nach. Leider hat mein Zufallsgenerator ein ganz ungünstiges Verhalten, wenn der seed 123456789 war . Tja, solche Dinge passieren eben.

edit: Ups, laut Standard muss der Generator ohne srand so laufen, als hätte man srand(1) gemacht.
@volkard unter mir (falls du dies noch liest, was ich nicht annehme ), bei dir muss das auch noch geändert werden. Übrigens viel schöner als mein doch sehr konstruierter Generator . Ich hatte mit dem Gedanken gespielt einen LCG mit ungünstigem Multiplikator zu nehmen (Zweierpotenzen sollten sehr kurze Periode haben), aber das war mir zu viel Arbeit.

volkard

Und hier ist's doch glatt aus Versehen passiert.

uint64_t interner_zustand=4711;

void my_srand(uint64_t seed)
{
   interner_zustand=seed;
}

uint32_t my_rand()
{
   interner_zustand=1967773755*(interner_zustand&0xffffffff)+(interner_zustand>>32);
   return x;
}

Das Biest liefert normalerweise sehr hübschen Zufall, bestehtz auch die die-hard-Tests. Außer, man ruft my_srand(0) auf. Dann ist es tot.

hustbaer

SeppJ schrieb:

Ok, bei 6 aus 49 stehen die Chancen noch recht gut . Aber wie wäre es mit 32000 aus 32767?

Dann zieht man halt einfach die 767 aus 32767 die man nicht braucht. EDIT: oops, wurde ja schon erwähnt, überlesen /EDIT

BTW: bei der "vector + rausnehmen" Variante muss man ja mit wechselndem Modulo-Wert arbeiten. Kann das nicht - je nach Generator - die "Qualität der Gleichverteilung" beeinflussen?

volkard

hustbaer schrieb:

Kann das nicht - je nach Generator - die "Qualität der Gleichverteilung" beeinflussen?

http://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Modulo_bias

SeppJ

hustbaer schrieb:

BTW: bei der "vector + rausnehmen" Variante muss man ja mit wechselndem Modulo-Wert arbeiten. Kann das nicht - je nach Generator - die "Qualität der Gleichverteilung" beeinflussen?

Wenn du auf solche Kleinigkeiten guckst, dann hast du das gleiche Problem aber auch bei der naiven Methode, da 49 keine Zweierpotenz ist. Oder verstehe ich gerade nicht wo drauf du hinaus willst? Du meinst doch, dass man RAND_MAX verschiedene Zahlen nicht gleichmäßig auf 49, 48, 37 usw. Container verteilen kann, oder? Falls ja, wieso sollte das was ausmachen, wenn die Containerzahl sich ändert? Das wird doch sogar tendenziell eher besser, weil jedes Mal andere Container den Vorteil abbekommen.

hustbaer

Ne, den Teil dass 2^blubb nicht durch 49 teilbar ist meine ich gar nicht. Das lässt sich ja wie in dem Artikel beschrieben relativ easy fixen, indem man halt Zahlen die >= N * floor(2^blubb / N) sind verwirft.

Trotzdem arbeitet man nicht mit einem fixen Modulo-Wert.

Angenommen ein Generator macht mit Modulo 100 schön gleichverteilte Werte. Und auch mit Modulo 99 und Modulo 98 uswusf.
Also quasi die Folge rgn(100), rgn(100), rgn(100), rgn(100), rgn(100), rgn(100), ... hat ne schöne Verteilung, die Folge rgn(99), rgn(99), rgn(99), rgn(99), rgn(99), rgn(99), ... ebenso etc.

Das heisst aber doch noch lange nicht, dass auch die Folge rgn(100), rgn(99), rgn(98), rgn(97), rgn(96), rgn(95), ... "schön" verteilt ist. Oder doch?
(Der Begriff "gleichverteilt" ist hier ja vermutlich nicht mehr anwendbar, aber ich denke ihr wisst was ich mit "schön" meine)

Ich weiss bloss nicht, ob es Generatoren gibt die einerseits "gut genug" sind um überhaupt ne brauchbare Gleichverteilung zu liefern und "Modulo safe" sind, andereseits aber "schlecht genug" sind um mit wechselndem Modulo Probleme zu machen.

BTW: das primäre Problem mit Modulo in Verbindung mit rand() ist wohl, dass rand() so oft als LCG implementiert ist, und daher die untersten paar Bits des Ergebnisses total für die Tonne sind wenn man einfach Modulo rechnet. Wurde aber sicher schon erwähnt.

hustbaer

SeppJ schrieb:

Das wird doch sogar tendenziell eher besser, weil jedes Mal andere Container den Vorteil abbekommen.

Nö, den Vorteil haben immer die ersten. Wechseln tut bloss wie viele und wie stark. Der letzte hat aber immer die Arschkarte (ausgenommen die paar Durchläufe wo N grad ne Zweierpotenz ist).

Mitleid

@Sepp & Volkard

Dass Funktionen rand() konstruierbar sind für die das Programm nicht hält, ändert nichts an der Beweisbarkeit der Terminierung. Worauf wollt ihr hinaus?

volkard

Mitleid schrieb:

@Sepp & Volkard
Dass Funktionen rand() konstruierbar sind für die das Programm nicht hält, ändert nichts an der Beweisbarkeit der Terminierung. Worauf wollt ihr hinaus?

Daß die Aussage, der Standard garantiere eine Terminierung einfach falsch ist.

Mitleid

volkard schrieb:

Daß die Aussage, der Standard garantiere eine Terminierung einfach falsch ist.

Schön. Nur hat niemand diese Aussage ausgesagt.

volkard

Mitleid schrieb:

Die Annahme, dass rand() sich standardkonform verhält reicht.

Mitleid

Ach, das nehmt ihr euch zu Herzen. Da habt ihr euch aber auch alle Mühe gegeben mich falsch zu verstehen. Man müsste das halt zusammen mit dem Zitat lesen.

Was ich meinte ist es reicht um dann zeigen zu können, dass das Programm terminiert. Zeigen muss man es natürlich für ein bestimmtes rand() schon noch.

Z.B. dadurch, dass man es für alle möglichen Startwerte (seeds) durchrechnet und prüft ob das Ding hält. Zusammen mit den Aussagen des Standards hat man dann bewiesen, dass das Programm auf jeden Fall hält. Dürfte im Fall des Threadstartes höchsten ca. eine Stunde dauern.

Da der Standard berechnete Pseudozufallszahlen garantiert, kann man, wie gesagt, auch formal rangehen. Z.B. ist leicht zu zeigen, dass Sepps Vorschlag nicht in jedem Fall terminiert.

Für deine Funktion (was immer die auch zurückliefert ) braucht es formal nur mehr Mühe bzw. beim Ausprobieren mehr Rechenkapazität. Dann mietest du dir halt für einen Monat den aktuellsten Petaflop Rechner. Aber, den Beweis hast du dann ebenfalls geführt.

SeppJ

Mitleid schrieb:

Für deine Funktion (was immer die auch zurückliefert ) braucht es formal nur mehr Mühe bzw. beim Ausprobieren mehr Rechenkapazität. Dann mietest du dir halt für einen Monat den aktuellsten Petaflop Rechner. Aber, den Beweis hast du dann ebenfalls geführt.

Aber man hätte bewiesen, dass es nicht terminiert. Womit nun allgemein bewiesen ist, dass der Standard nicht die unbedingte Terminierung des Programms garantiert, weil schon mehrere Gegenbeispiele gefunden wurden. Und somit ist nun auch allgemein gezeigt, dass der Algorithmus nicht zwangsläufig terminiert, egal ob mit echten Zufallszahlen oder mit einem PRNG. Und das ist das genaue Gegenteil deiner ursprünglichen Aussage.

hustbaer

Mitleid schrieb:

Ach, das nehmt ihr euch zu Herzen. Da habt ihr euch aber auch alle Mühe gegeben mich falsch zu verstehen. Man müsste das halt zusammen mit dem Zitat lesen.

Ne. Deine Aussage war nicht anders zu verstehen.

Wenn ich etwas trotz Standard immer "für eine bestimmte Implementierung" zeigen muss, dann ist es doch vollkommen egal, was der Standard dieser Implementierung vorschreibt oder nicht.

Im Prinzip kann man deine Aussage (laut letztem Beitrag) reduzieren auf: "Das Problem ist grundsätzlich analysierbar, und vielleicht kommt man sogar zu einem Ergebnis.". Was jetzt keine besonders interessante Aussage ist.

Man musste daher wohl davon ausgehen dass du etwas anderes meinst.

Mitleid

Hm, ...

hustbaer schrieb:

Wenn ich etwas trotz Standard immer "für eine bestimmte Implementierung" zeigen muss, dann ist es doch vollkommen egal, was der Standard dieser Implementierung vorschreibt oder nicht.

Würde der Standard erlauben, dass rand() z.B. über eine physikalische Einrichtung echte Zufallszahlen abholt, hätte man den Fall, den ipsec anspricht.

hustbaer schrieb:

Im Prinzip kann man deine Aussage (laut letztem Beitrag) reduzieren auf: "Das Problem ist grundsätzlich analysierbar, und vielleicht kommt man sogar zu einem Ergebnis.". Was jetzt keine besonders interessante Aussage ist.

Meine Aussage enthält viel weniger. Deswegen ist mir der Widerspruch ja so schleierhaft. Ich sage lediglich, dass man wegen der Implementierung von rand(), also dem Ausschluß von echten Zufallszahlen, den Nachweis der Terminierung führen kann, beispielsweise durch Ausprobieren der garantiert konstanten Anzahl aller möglichen Fälle.

hustbaer schrieb:

Man musste daher wohl davon ausgehen dass du etwas anderes meinst.

Die Aussage, dass man allein durch den Standard, die Terminierung für alle möglichen Implementierung von rand() zeigen kann, ist so absurd, dass man eigentlich nicht davon ausgehen musste. Jeder kann sich in zwei Sekunden hundert Gegenbeispiele für rand() ausdenken, bei denen das Programm nicht terminiert.

Egal, jetzt ist dann ja alles klar.