guter zufall (multiply-with-carry prng)

hustbaer

@erik.vikinger:
Dein Kommentar hier ist total sinnfrei. Ein Algorithmus kann nie echte Zufallszahlen generieren. Das liegt in der Natur der Sache. Wieso sollte man dann einen Warnhinweis anbringen?

erik.vikinger

Hallo,

hustbaer schrieb:

Wieso sollte man dann einen Warnhinweis anbringen?

Weil man sonst den Algorithmus komplett durcharbeiten und natürlich auch verstehen müsste um zu sehen das dort keine externen Dinge drin sind die eventuell doch echten Zufall reinbringen könnten. Wer tut das schon?

Grüße
Erik

hustbaer

Man muss garnix durcharbeiten, zumindest nicht bis zu dem Punkt wo man es versteht. Man muss bloss gucken, ob irgendwo auf irgendwelche Dinge wie /dev/rand oder ähnliches zugegriffen wird. Wenn nicht, können es keine echten Zufallszahlen sein.

Davon abgesehen: Alle RNGs die ich kenne sind reine PRNGs (ich meine fertige Implementierungen in diversen Libraries). Wieso also das mit einem Warnhinweis versehen, was der Normalfall ist?
Den Fall zu dokumentieren der von der Norm abweicht, d.h. in diesem Fall einen RNG der wirklich echte Zufallszahlen liefert, ist wohl vernünftiger.

Vor allem da für die meisten Anwendungen ein PRNG, mit einem mehr oder weniger echt zufälligem Seed, vollkommen ausreichend ist.

erik.vikinger

Hallo,

hustbaer schrieb:

wie /dev/rand oder ähnliches

Gerade dieses "ähnliches" ist nicht für jeden erkennbar oder gar beurteilbar.

hustbaer schrieb:

Alle RNGs die ich kenne sind reine PRNGs

Und was ist mit "/dev/urandom"? Auf einem normalen PC (mit halbwegs aktuellem Linux o.ä.) liefert das schon recht ordentlichen Zufall (wenn auch nur wenig) und wenn dann noch ein moderner Intel-Chipsatz oder eine aktuelle VIA-CPU (beide mit Hardware-TRNG) dazu kommt hat man schon eine Rundum-Sorglos-Lösung zur Verfügung (mit bereits ordentlicher Menge).

hustbaer schrieb:

Wieso also das mit einem Warnhinweis versehen, was der Normalfall ist?

Das ist allerdings ein berechtigter Einwand. Wer sich die Mühe macht eine gute Zufalls-Quelle zu implementieren schreibt das auch möglichst dick drauf oder will gar Geld dafür. Trotzdem sollte man IMHO dem unbedarften Anfänger schon möglichst deutlich sagen das nicht überall wo Zufall drauf steht auch Zufall drin ist bzw. das es verschiedene Qualitätsstufen beim Zufall gibt. Ich finde diese PRNGs sollten nicht Zufalls-Generator sondern Sequenz-Generator heißen, einfach um den Unterschied deutlich zu machen.

EDIT : "/dev/random" liefert natürlich keinen echten Zufall, jedenfalls nicht immer

Grüße
Erik

Basher_ist_nicht_BashAr

hustbaer schrieb:

Vor allem da für die meisten Anwendungen ein PRNG, mit einem mehr oder weniger echt zufälligem Seed, vollkommen ausreichend ist.

naja, da musste schon unterscheiden. viele sind für irgendwelche simulationen ausreichend, aber für kryptografie z.b. sind sie nicht so toll.

erik.vikinger schrieb:

"Kein echter Zufall! Niemals in kritischen Systemen einsetzen!"

Du schreibst doch auch nicht auf einen Fernseher:

"Keine echte 3D Welt! Niemals hinein springen!"
Siehe Link
http://data.lustich.de/bilder/l/1120-in-den-fernseher-gesprungen.jpg

Tim schrieb:

Ich dachte du würdest mittlerweile einen anderen prng bevorzugen?

Welchen denn? Würde mich sehr interessieren

volkard

Tim schrieb:

Ich dachte du würdest mittlerweile einen anderen prng bevorzugen?

Ich kann mich nicht erinnern, das gesagt zu haben. Kürzlich drückte ich aus, daß ich den mersenne twister nicht mag (das hat sich in den letzten vier Jahren also nicht geändert).

hustbaer

Was hast du denn gegen den Mersenne Twister? Zu gross (zu viel State)?

hustbaer

@erik.vikinger:
Kurzfassung: es gibt Leute die wissen was sie tun, und es gibt Leute die haben keinen Tau. Wenn jemand weiss was er tut, wird er die Warnung nicht brauchen. Wenn er nicht weiss was er tut, wird er damit nichts anfangen können.

volkard schrieb:

Tim schrieb:

Ich dachte du würdest mittlerweile einen anderen prng bevorzugen?

Ich kann mich nicht erinnern, das gesagt zu haben. Kürzlich drückte ich aus, daß ich den mersenne twister nicht mag (das hat sich in den letzten vier Jahren also nicht geändert).

Ich finde den Thread leider nicht, aber das was du da sagtest interpretierte ich so. Naja, nicht wichtig.

volkard

hustbaer schrieb:

Was hast du denn gegen den Mersenne Twister? Zu gross (zu viel State)?

Ja, zu viel State. Ich brauche keine Periode von 10^6000, der Rechner hält nichtmal 10^18 Takte lang. Also zahle ich nicht dafür.
Außerdem waren die mords Geschwindigkeitsangaben auf deren Homepage (viermal schneller als rand()!) einfach nicht nachvollziehbar, sie waren falsch wie Messungen von Sun.

Tachyon

volkard schrieb:

Außerdem waren die mords Geschwindigkeitsangaben auf deren Homepage (viermal schneller als rand()!) einfach nicht nachvollziehbar, sie waren falsch wie Messungen von Sun.

Also bei mir kommt das ziemlich gut hin. Keine Ahnung, was Du da gemessen hast.

pointercrash**

Zeitgleich mit mir hat einer an seiner Diplomarbeit gewurschtelt, der aus dem verstärkten weißen Rauschen eines Transistors Zufallszahlen erzeugen wollte. Eine einleuchtende Idee eigentlich.
Das ging aber nicht so leicht, weil die Verstärkerstufe ihre eigene Charakteristik einprägte. Er hat dann noch ewig mit digitalen und analogen Filtern rumgemurkst, um dann festzustellen, daß er sich dafür die Sprungantworten der Filterstufen einheimst, wenn mal ein µ- Meson o.Ä. (also kosmische und terrestrische Strahlung) in die Schaltung einschlägt.
Wie auch immer, die "Zufälligkeit" der damaligen prng hatte er nach drei Monaten noch immer nicht erreicht.

Leider weiß ich nicht, wie die Geschichte ausgegangen ist ..., aber wenn das Ding da schneller als rand() ist, nehme ich es dankbar an.

SeppJ

pointercrash() schrieb:

Zeitgleich mit mir hat einer an seiner Diplomarbeit gewurschtelt, der aus dem verstärkten weißen Rauschen eines Transistors Zufallszahlen erzeugen wollte. Eine einleuchtende Idee eigentlich.
Das ging aber nicht so leicht, weil die Verstärkerstufe ihre eigene Charakteristik einprägte. Er hat dann noch ewig mit digitalen und analogen Filtern rumgemurkst, um dann festzustellen, daß er sich dafür die Sprungantworten der Filterstufen einheimst, wenn mal ein µ- Meson o.Ä. (also kosmische und terrestrische Strahlung) in die Schaltung einschlägt.
Wie auch immer, die "Zufälligkeit" der damaligen prng hatte er nach drei Monaten noch immer nicht erreicht.

Leider weiß ich nicht, wie die Geschichte ausgegangen ist ..., aber wenn das Ding da schneller als rand() ist, nehme ich es dankbar an.

Normalerweise sind Verfahren die echten physiklaischen Zufall nutzen viel zu langsam für Anwendungen im Computer und werden höchstens als seed eingesetzt. Es gibt auch ein paar sehr schnelle echte Zufallsgeneratoren (z.B. mit chaotischen Lasern) die sogar schneller Zufallszahlen erzeugen als ein PRNG, aber auch da hat man ein Problem: Wie bekommt man die Zufallszahlen vom externen Gerät schneller in den Prozessorkern(wo sie gebraucht werden) als dass sich der Prozessorkern selber eine PRN generiert? Da die Notwendigkeit echter Zufallszahlen eher selten ist, hat kein Hardwarehersteller Interesse an der Entwicklung einer schnellen Schnittstelle dafür. Das ist es, woran echter Zufall im Computer letztlich scheitert.

Basher_ist_nicht_BashAr

pointercrash() schrieb:

Zeitgleich mit mir hat einer an seiner Diplomarbeit gewurschtelt, der aus dem verstärkten weißen Rauschen eines Transistors Zufallszahlen erzeugen wollte. Eine einleuchtende Idee eigentlich.

das ist bestimmt seine webseite: http://true-random.com/

hustbaer

volkard schrieb:

hustbaer schrieb:

Was hast du denn gegen den Mersenne Twister? Zu gross (zu viel State)?

Ja, zu viel State. Ich brauche keine Periode von 10^6000, der Rechner hält nichtmal 10^18 Takte lang. Also zahle ich nicht dafür.
Außerdem waren die mords Geschwindigkeitsangaben auf deren Homepage (viermal schneller als rand()!) einfach nicht nachvollziehbar, sie waren falsch wie Messungen von Sun.

Gut, der Speicherverbrauch. Ist natürlich ein Argument wenn die paar kB irgendwo abgehen. Aber doch kein Grund die Mersenne Twister Generatoren allgemein abzulehnen...?

erik.vikinger

Hallo,

@hustbaer

Kurzfassung: es gibt Leute die wissen was sie tun,

Richtig, die können selber prüfen was sie wollen. Wir beide sind bestimmt in der Lage einen ?RNG grob auf seine Tauglichkeit zu prüfen.

und es gibt Leute die haben keinen Tau.

Und gerade um die geht es mir. Warum gibt es die Kennzeichnungspflichtig für Eier im Einzelhandel? Damit auch jemand der keine Ahnung vom Fach hat in der Lage ist eine vernünftige Entscheidung zu treffen. Und genau das wird verhindert wenn auf jedem X-beliebigen Algorithmus "Zufall" drauf steht obwohl gar kein Zufall drin ist. Der durchschnittliche Programmierer, der vom seltenen Spezialgebiet der "Nutzbarmachung des Zufalls" keine Ahnung hat, wird sich nicht die Mühe machen und prüfen ob Library X seinen Ansprüchen wirklich genügt sondern sich auf das Wort "Zufall" verlassen. Genau deshalb bin ich dafür das diese PRNGs das R im Nahmen nicht haben dürften. Und nur weil jeder auf seinen Kram etwas draufschreibt was gar nicht drin ist wird das deshalb nicht weniger Falsch.

Wenn jemand weiss was er tut, wird er die Warnung nicht brauchen.

Möglicherweise, aber sie könnte ihm die Mühe einer eigenen Prüfung sparen.

Wenn er nicht weiss was er tut, wird er damit nichts anfangen können.

Da möchte ich nur auf die Eier verweisen, das System funktioniert IMHO recht gut (inwiefern sich auch alle Erzeuger korrekt dran halten kann ich natürlich nicht beurteilen).

Grüße
Erik

erik.vikinger schrieb:

Genau deshalb bin ich dafür das diese PRNGs das R im Nahmen nicht haben dürften. Und nur weil jeder auf seinen Kram etwas draufschreibt was gar nicht drin ist wird das deshalb nicht weniger Falsch.

Dafür ist doch das P da. Mal ne andere Frage wie bekomme ich von einem "Zufalls"generator x "Zufalls"zahlen im Bereich [10 100)?

Basher_ist_nicht_BashAr

Tim schrieb:

Mal ne andere Frage wie bekomme ich von einem "Zufalls"generator x "Zufalls"zahlen im Bereich [10 100)?

meinste das: http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html ?

hustbaer

Ich gehe mal davon aus dass der Output des Generators gleichverteilt ist, und dass man das Ergebnis auch wieder gleichverteilt haben will.

----

Im ersten Schritt bringt man normalerweise den Anfang der Range auf 0, d.h. wir suchen eine Zahl im Bereich [0, 90). (Auf die addieren wir nachher einfach 10 drauf, damit wir wieder auf [10, 100) kommen.)

Nun könnte man einfach eine Zahl ziehen, und sie mittels Modulo in den gewünschten Bereich bringen. Bloss würde das die Gleichverteilung zerstören.

Angenommen der Generator hat eine Output-Range von [0, 200).
Dann würden 0, 90 und 180 mittels Module auf 0 abgebildet,
1, 91 und 181 auf 1,
...
19, 109 und 199 auf 19,
20 und 110 auf 20,
21 und 111 auf 21,
etc.

Kurz: die Zahlen 0 bis 19 würden 1,5 mal häufiger vorkommen als die Zahlen 20 bis 89.

Die IMO einfachste (und AFAIK "üblichste") Möglichkeit dem zu begegnen, ist, gezogene Zahlen von 180 bis 199 einfach zu verwerfen.

Verallgemeinert, in Pseudo-Code, könnte das ca. so aussehen:

int GetNumber(Generator& g, int lowerBound, int upperBoundExclusive)
{
    int newUpperBoundExclusive = upperBoundExclusive - lowerBound;
    int generatorUpperBoundExclusive = g.GetUpperBoundExclusive(); // wir gehen davon aus dass die untere Schwelle des Generators immer 0 ist
    int n = generatorUpperBoundExclusive / newUpperBoundExclusive; // integer Division, Ergebnis immer abgerundet
    assert(n > 0); // sonst haben wir ein Problem
    int acceptableUpperBoundExclusive = n * newUpperBoundExclusive;

    int x = 0;
    do
    {
        x = g.GetNumber();
    }
    while (x >= acceptableUpperBoundExclusive);

    x = x % newUpperBoundExclusive;
    x = x + lowerBound;
    return x;
}

Das aufwendigste an der ganzen Sache ist dabei, sicherzustellen, dass nirgends ein Überlauf passiert. Und, falls die geforderte Range grösser werden kann, als die die der Generator ausspuckt, muss man sich natürlich statt dem einfachen assert() etwas besseres einfallen lassen. Beispielsweise in jedem Durchlauf zwei (oder mehr) Zahlen zu ziehen, und diese zu einer grösseren zusammenzusetzen.