Pseudo-Zufallszahlengenerator von einer berechenbaren normalen Zahl

Question

Ist es nicht leicht möglich, eine PRNG in einer solchen Weise zu konstruieren? Warum ist es nicht getan?

Das ist, soweit ich weiß, wir könnten einfach ein PRNG haben, die einen Samen n nimmt. Wenn Sie nach einem Zufallsbit fragen, ist es die n-te Ziffer der binären Erweiterung der berechenbaren normalen Zahl nimmt und erhöht n.

Mein erster Gedanke war, dass vielleicht hatten wir keine berechenbare normale Zahl gefunden, aber wir haben . Der verbleibende Gedanke ist, dass es einen guten Grund ist nicht zu-- entweder gibt es eine Eigenschaft von PRNGs, die ich bin nicht vertraut mit, dass ein solches Verfahren würde nicht haben, oder es wäre unpraktisch, irgendwie, oder anderweitig durch andere Methoden überflügelt.

Answer 1

Das würde die Ausgabe wirklich einfach macht die Vorhersage.

Nehmen wir zum Beispiel, erzeugen Sie die ganze Zahl 0x54a30b7f. Wenn Sie 4GiB von pi (oder zufälligen Rauschen oder einer tatsächlichen normalen Zahl) haben, stehen die Chancen es nur geht ein (oder vielleicht eine Handvoll) Auftreten dieser speziellen integer sein und ich kann mit ziemlich hohen Wahrscheinlichkeit aller zukünftigen Zahlen vorhersagen. Dies ist ein ernsthaftes Problem im Fall von kryptographisch starken PRNGs. Wenn anstelle von einfachen sequentiellen Scan Sie eine Funktion verwenden, muss ich nur noch die Funktion folgen, wenn es schwierig genug ist, folgen sie in ein PRNG dreht sich in seinem eigenen Recht.

Wenn Sie nicht besorgt über die Verschlüsselungsstärke Ihres Generators sind, dann gibt es viel kompakte Möglichkeiten zur Erzeugung von Zufallszahlen. Mersenne Twister , zum Beispiel, hat einen viel größeren Zeitraum ohne eine Tabelle 4GiB Lookup erforderlich ist.