Ungewollte Größen bei Ausgabe von Zufallszahlen
-
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 Folgergn(100), rgn(100), rgn(100), rgn(100), rgn(100), rgn(100), ...hat ne schöne Verteilung, die Folgergn(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.
-
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).
-
@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?
-
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.
-
volkard schrieb:
Daß die Aussage, der Standard garantiere eine Terminierung einfach falsch ist.
Schön. Nur hat niemand diese Aussage ausgesagt.
-
Mitleid schrieb:
Die Annahme, dass rand() sich standardkonform verhält reicht.
-
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.
-
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.
-
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.
-
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.
