Ungewollte Größen bei Ausgabe von Zufallszahlen

Mitleid

SeppJ schrieb:

Mitleid schrieb:

SeppJ schrieb:

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

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

Ganz sicher nicht. Laut Standard liefert rand() einfach nur Pseudozufallszahlen zwischen 0 und RAND_MAX. Streng genommen ist noch nicht einmal die Verteilung vorgegeben, aber selbst wenn man von Gleichverteilung ausgeht reicht das nicht. Eher im Gegenteil. Damit der Algorithmus terminiert, müsste garantiert sein, dass in endlicher Zeit mehr als 5 verschiedene Zahlen gezogen werden. Das wäre der Qualität der Zufallszahlen abträglich.

Der Standard garantiert dir, dass für einen bestimmten, mit srand() angenommenen Startwert die Folge der mit rand() erzeugten Pseudozufallszahlen identisch ist. Somit wird das ein endliches Problem, welches sich für jeden Fall wunderbar durchprobieren lässt. Der Beweis der Terminierung kann also stets locker erbracht werden.

SeppJ

Das ist doch Unsinn! Das hat mit der Standardkonformität der Implementierung überhaupt gar nichts zu tun! Du probierst für jede Implementierung einfach nur aus, ob der Algorithmus terminiert. Aber weder garantiert dir der Standard an sich, dass der Algorithmus durch die vorgegebenen Eigenschaften von rand() immer terminiert, noch kennst du die Implementierung und musst für jede davon den Algorithmus erneut testen. Super Beweis!

Und schönerweise hast du damit sogar schon gezeigt, wie der Gegenbeweis läuft: Ich muss nur einen einzigen Startwert finden, der in einer Endlosschleife endet. Es gibt sehr viele Startwerte und sehr viele Implementierungen von rand(). Willst du wirklich da drauf wetten, dass die wirklich alle für alle Startwerte terminieren? Zur Not kann ich mir sogar mein eigenes, standardkonformes rand() schreiben, welches mit Absicht eine Implementierungsschwäche enthält.

volkard

SeppJ schrieb:

Es gibt sehr viele Startwerte und sehr viele Implementierungen von rand(). Willst du wirklich da drauf wetten, dass die wirklich alle für alle Startwerte terminieren?

Ich würde darauf wetten. Das heißt, ich würde den Algo des Threaderstellers ohne Schmerzen in Produktivcode verwenden.

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

Ja, deswegen kann der Standard hier nichts garantieren.

SeppJ

volkard schrieb:

SeppJ schrieb:

Es gibt sehr viele Startwerte und sehr viele Implementierungen von rand(). Willst du wirklich da drauf wetten, dass die wirklich alle für alle Startwerte terminieren?

Ich würde darauf wetten. Das heißt, ich würde den Algo des Threaderstellers ohne Schmerzen in Produktivcode verwenden.

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

edit: Beziehungsweise da würdest du sicherlich ipsecs Algorithmus nehmen, wegen der Laufzeit.

Ach, immer diese pragmatischen Lösungen. Da kann man nie mal richtig schön theoretisieren.

Dobi

SeppJ schrieb:

Aber wie wäre es mit 32000 aus 32767?

Also ich würd in dem Fall lieber die 767 Zahlen, die nicht vorkommen, ziehen.

Mitleid

SeppJ schrieb:

Das ist doch Unsinn! Das hat mit der Standardkonformität der Implementierung überhaupt gar nichts zu tun! Du probierst für jede Implementierung einfach nur aus, ob der Algorithmus terminiert. Aber weder garantiert dir der Standard an sich, dass der Algorithmus durch die vorgegebenen Eigenschaften von rand() immer terminiert, noch kennst du die Implementierung und musst für jede davon den Algorithmus erneut testen. Super Beweis!

Hm, ich weiß nicht, was es da zu lamentieren gibt. Der Standard GARANTIERT, dass da niemals ein echter Zufalls ins Spiel kommen kann. Mehr braucht man nicht.

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.

Man muss auch nicht wetten. Wenn UINT_MAX eine akzeptable Größe hat lässt man das durchprobieren und hat den wasserdichten Beweis, dass das Programm hält. Wenn nicht sieht man sich halt rand() genauer an und fährt einen formalen Beweis. Wo ist das Problem?

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.