Generieren Sie eine beliebige Ganzzahl
Ich entschuldige mich im Voraus, da ich mit keiner formalen Vorstellung von Zufälligkeit sehr erfahren bin.
Der Titel sagt das meiste davon: Ich möchte innerhalb einer angemessenen Zeit eine zufällige Ganzzahl generieren, in der jede Ganzzahl erscheinen kann, ob mit gleicher Häufigkeit oder nicht, ist nicht wichtig. Als Add-On ist der Computerspeicher kein Problem, da selbst bei unendlichem Speicherplatz zum Speichern dieser generierten Zahlen nicht klar ist, wie dies geschehen könnte. Ich habe keine Fortschritte bei der Suche nach einem geeigneten Algorithmus gemacht, aber hier sind meine Beobachtungen.
Wenn Sie eine reelle Zahl zufällig generieren können, können Sie Funktionen wie die Floor-Funktion verwenden, um eine beliebige Ganzzahl zu generieren. Wenn Sie zufällig eine reelle Zahl zwischen einem beliebigen Intervall generieren könnten$[a,b]$, dann könnten Sie asymptotische Funktionen wie verwenden $\tan$ eine beliebige reelle Zahl zu generieren.
Wenn ich eine Menge S habe, die eine größere oder gleiche Kardinalität zu den ganzen Zahlen hat, und ich kann zufällig ein Element innerhalb von S erzeugen, dann kann ich zufällig jede ganze Zahl erzeugen, indem ich Mitglieder von S auf die ganzen Zahlen abbilde.
Ich weiß, dass es Sequenzen wie die Prime-Gap-Sequenz gibt, die zufällig sind und beliebig große ganze Zahlen enthalten, aber nicht einfach zu berechnen sind.
Das ist es jedoch in Bezug auf das, was ich mir vorstellen kann. Es würde mich nicht wundern, wenn es keine einfache Lösung für das Problem gäbe, aber wenn jemand einen Grund hat, warum dies nicht möglich ist, würde ich es auch gerne hören.
Antworten
Die beliebige Größe hat keine Bedeutung, da die Berechnung nicht anhalten kann!
Bedenken Sie, dass Sie für jedes Bit der zufälligen Ganzzahl eine Münze werfen, dann können Sie sehen, dass der Münzwurf niemals endet.
Man sollte vorsichtig sein, wenn man mit der beliebigen Größe spielt. Mathematisch kann man das sagen lassen$x$ sei eine zufällige ganze Zahl, dh $x \stackrel{R}{\leftarrow} \mathbb Z$Wenn Sie jedoch versuchen, einen Wert davon zu finden, werden Sie der Erzeugung davon gegenüberstehen. Wenn Sie eine einheitliche zufällige Ganzzahl wollen, wird dies offensichtlich fehlschlagen!
Nehmen wir nun an, Sie haben ein Limit wie $0\color{red}{<} x \leq 2^L$Dann können Sie LFSRs verwenden , um Zufallszahlen im Bereich zu generieren. Wenn ein LFSR mit Größe$L$ ist maximal dann ist es periodisch und es hat eine Periode von $2^L-1$. In dieser Zeit besucht es alle möglichen$L$-Bit-Zahlen außer dem All-Null-Zustand. Sie können einen Samen aus der Zeit erhalten und ihn verwenden.
Beachten Sie, dass LFSR weit davon entfernt ist, ein kryptografisch sicherer zufälliger Pseudogenerator (CSPRNG) zu sein. Nur haben$2L$ Die vom LFSR ausgegebene Bitmenge reicht aus, um die nächsten Bits aufgrund des Berlakamp-Massay-Algorithmus zu bestimmen - und tatsächlich reicht die Gaußsche Eliminierung aus, BM ist jedoch viel schneller -.