Pseudo-Zufallszahlengenerator aus einer berechenbaren Normalzahl

Question

Ist es nicht einfach möglich, einen PRNG so zu konstruieren? Warum ist es nicht getan?

Das heißt, soweit ich weiß, könnten wir einfach eine PRNG haben, die einen Seed n nimmt. Wenn Sie nach einem zufälligen Bit fragen, nimmt es die n-te Stelle der binären Erweiterung der berechenbaren normalen Zahl und erhöht n.

Mein erster Gedanke war, dass wir vielleicht eine berechenbare normale Zahl nicht gefunden hatten, aber wir have. Der verbleibende Gedanke ist, dass es einen guten Grund gibt, nicht - entweder gibt es eine Eigenschaft von PRNGs, die ich nicht kenne, die eine solche Methode nicht hätte, oder sie wäre irgendwie unpraktisch, oder sie wird anderweitig durch andere Methoden überholt.

Answer 1

Das würde die Vorhersage der Ausgabe wirklich einfach machen.

Sagen Sie zum Beispiel, Sie generieren die Ganzzahl 0x54a30b7f. Wenn Sie 4 Pi von Pi (oder zufälliges Rauschen oder eine tatsächliche normale Zahl) haben, wird es wahrscheinlich nur ein (oder vielleicht eine Handvoll) Vorkommen dieser bestimmten Ganzzahl geben und ich kann mit einer ziemlich hohen Wahrscheinlichkeit alle zukünftigen Zahlen vorhersagen. Dies ist ein ernstes Problem im Falle von kryptographisch starken PRNGs. Wenn Sie anstelle des einfachen sequenziellen Scans eine Funktion verwenden, muss ich nur der Funktion folgen, die, wenn es schwierig genug ist, zu einem eigenen PRNG wird.

Wenn Sie sich nicht um die kryptographische Stärke Ihres Generators kümmern, gibt es viel kompaktere Möglichkeiten, Zufallszahlen zu generieren. Beispielsweise hat Mersenne Twister einen viel größeren Zeitraum, ohne dass eine 4GiB-Nachschlagetabelle benötigt wird.