Get best of the week

Generieren von Pseudozufallszahlen mit einem zellularen Automaten: Regel 30

Pseudozufallszahlengeneratoren geben Zahlen deterministisch an, aber normalerweise sehen solche Zahlen nicht periodisch (zufĂ€llig) aus. Zumindest in den meisten FĂ€llen erfolgt die Verwendung solcher Nummern normalerweise. Der Generator nimmt einen Anfangswert (idealerweise eine echte Zufallszahl) und erzeugt eine Folge von Zahlen, die in AbhĂ€ngigkeit vom Anfangswert und / oder der vorherigen Zahl der Folge arbeiten. Solche Zahlen sind pseudozufĂ€llig (und keine echten Zufallszahlen), da diese Zahlen, wenn der an den Generator ĂŒbergebene Anfangswert bekannt ist, erneut algorithmisch erzeugt werden können. Echte Zufallszahlen werden unter Verwendung spezieller Hardware oder bestimmter physikalischer PhĂ€nomene erzeugt - Pulsschwankungen des Blutvolumens, des atmosphĂ€rischen Drucks, des thermischen Rauschens, der Quantenprozesse usw.



Es gibt viele Möglichkeiten, Pseudozufallszahlen zu generieren. Zum Beispiel der Blum-Blum-Shub-Algorithmus , die Mean-Square- Methode , die Fibonacci-Methode mit Verzögerungen . Heute werden wir ĂŒber die Erzeugung von Zufallszahlen unter Verwendung von Regel 30 sprechen , die einen mehrdeutigen Ansatz verwendet, der die Verwendung eines zellularen Automatenmodells beinhaltet . Diese Methode hat viele Standard-Zufallszahlentests bestanden und wurde in Mathematica verwendet , um zufĂ€llige Ganzzahlen zu generieren.

Mobilfunkautomat


Bevor wir zum Thema von Regel 30 kommen, nehmen wir uns etwas Zeit fĂŒr zellulare Automaten. Ein zellularer Automat ist ein diskretes Modell, das aus einem regelmĂ€ĂŸigen Gitter von Zellen beliebiger Dimension besteht. Jede der Gitterzellen kann sich in einem endlichen Satz von ZustĂ€nden befinden. DarĂŒber hinaus wird fĂŒr jede Zelle ein Konzept wie "Nachbarschaft" definiert. In der NĂ€he einer bestimmten Zelle können beispielsweise alle Zellen eintreten, die sich in einem Abstand von nicht mehr als 2 von ihr befinden. Es gibt Regeln, die bestimmen, wie Zellen miteinander interagieren und zur nĂ€chsten Generation (Status) ĂŒbergehen. Diese Regeln werden hauptsĂ€chlich durch mathematische (programmierbare) Funktionen dargestellt, die vom aktuellen Zustand der Zellen und vom Zustand ihrer Nachbarn abhĂ€ngen.


Beschreibung des zellularen Automaten Mit der

Beschreibung des zellularen Automaten aus der vorherigen Abbildung können Sie herausfinden, dass sich jede Zelle in einem von zwei EndzustĂ€nden befinden kann -0(rot dargestellt) und1(schwarz dargestellt). Jede Zelle geht in die nĂ€chste Generation ĂŒber und nimmt einen neuen Zustand an, der sich aus der Anwendung der OperationXORauf ihre 8 Nachbarnergibt. Die erste Generation (Anfangszustand) des Gitters wird zufĂ€llig eingestellt. Die Funktionsweise dieses zellularen Automaten ist unten gezeigt.


XOR-basierter

zellularer Automat in Aktion Die Idee eines zellularen Automaten entstand in den 1940er Jahren dank Stanislav Ulam und John von Neumann . ZellulĂ€re Automaten haben Anwendung in der Informatik, Mathematik, Physik, in der Theorie komplexer Systeme, in der theoretischen Biologie und bei Problemen der Modellierung der Mikrostruktur von Medien und Materialien gefunden. In den 1980er Jahren fĂŒhrte Stephen Wolfram eine systematische Untersuchung eines eindimensionalen Zellularautomaten (auch als elementarer Zellularautomat bezeichnet) durch, auf dem Regel 30 basiert.

Regel 30


Regel 30 ist ein elementarer (eindimensionaler) zellularer Automat, in dem sich jede Zelle in einem von zwei EndzustĂ€nden befinden kann: 0(rote Zellen in der folgenden Abbildung) und 1(schwarze Zellen). Die Umgebung der Zelle wird durch die beiden nĂ€chsten Nachbarn dargestellt, die sich links und rechts davon befinden. Der nĂ€chste Zustand (Erzeugung) einer Zelle hĂ€ngt von ihrem aktuellen Zustand und vom Zustand ihrer Nachbarn ab. Die Regeln fĂŒr den Übergang von Zellen zum nĂ€chsten Status sind in der folgenden Abbildung dargestellt.


Regel 30

Diese Regeln fĂŒr den Übergang in einen neuen Zustand von Zellen können vereinfacht geschrieben werden alsleft XOR (central OR right).

Wir geben die Zellen des Automaten in Form eines zweidimensionalen Gitters aus, von dem jede Zeile eine Generation (Zustand) darstellt. Wenn die nĂ€chste Generation (Zustand) von Zellen berechnet wird, wird sie unterhalb des letzten bekannten Zustands angezeigt. Jede Zeile enthĂ€lt eine endliche Anzahl von Zellen, die am Ende eine „Schleife“ bilden.


Regel 30 in Aktion

Das obige Muster ergibt sich aus dem Anfangszustand (Zeile 0), wenn eine Zelle einen Zustand1(schwarz) hat und alle sie umgebenden Zellen einen Zustand0(rot) haben. Der Zustand der Zellen in der nĂ€chsten Generation (Zeile 1) wird gemĂ€ĂŸ der obigen Regel berechnet. Das vertikale Gitter reprĂ€sentiert die Zeit, und die Schnittpunkte von Zeilen und Spalten reprĂ€sentieren den Zustand einer bestimmten Zelle in einem bestimmten Stadium der Entwicklung des Systems.


Generation t und Generation t + 1

WĂ€hrend sich das Muster entwickelt, erscheinen hĂ€ufig rote Dreiecke unterschiedlicher GrĂ¶ĂŸe darin, aber im Allgemeinen kann ein unterscheidbares Muster in der resultierenden Struktur nicht erkannt werden. Das obige Fragment des Gitters wird zu einem willkĂŒrlich gewĂ€hlten Zeitpunkt hergestellt. Hier können Sie Chaos und AperiodizitĂ€t sehen. Diese Eigenschaft ist Regel 30 und wird zum Generieren von Pseudozufallszahlen verwendet.

Pseudozufallszahlengenerierung


Wie bereits erwĂ€hnt, zeigt Regel 30 aperiodisches und chaotisches Verhalten. Infolgedessen fĂŒhrt seine Anwendung zur Erzeugung komplexer und anscheinend zufĂ€lliger Muster nach einfachen und genau definierten Regeln. Um Zufallszahlen unter Verwendung von Regel 30 zu erzeugen, wird die zentrale Gitterspalte verwendet, aus der eine Folge von nZufallsbits ausgewĂ€hlt wird , aus der die gewĂŒnschte nBit-Zufallszahl erzeugt wird . Die nĂ€chste Zufallszahl wird unter Verwendung der folgenden nBits aus der Spalte erzeugt.


Generieren von Zufallszahlen mit Regel 30

Wenn Sie immer mit der Auswahl von Zellen aus der ersten Zeile beginnen, ist die generierte Zahlenfolge immer vorhersehbar. Und das brauchen wir nicht. Um Pseudozufallszahlen zu erstellen, verwenden wir einen zufĂ€lligen Anfangswert (z. B. die aktuelle Zeit), ĂŒberspringen die entsprechende Anzahl von Zeilen und wĂ€hlen anschließend Sequenzen ausnZeilen aus und erstellen darauf basierende Zufallszahlen.

Die mit Regel 30 erzeugten Pseudozufallszahlen sind nicht kryptografisch sicher, aber fĂŒr Simulationen geeignet - bis wir unangemessene Anfangswerte wie verwenden0.

Einer der Hauptvorteile der Anwendung von Regel 30 zur Erzeugung von Pseudozufallszahlen besteht darin, dass Sie viele Zufallszahlen im parallelen Modus erstellen können, indem Sie zufÀllig viele Spalten mit einer LÀnge von n Bits auswÀhlen. Hier ist ein Beispiel einer pseudo-zufÀllige Folge von 8-Bit - Zahlen , die durch dieses Verfahren erzeugt , um den Anfangswertes unter Verwendung von 0: 220, 197, 147, 174, 117, 97, 149, 171, 240, 241.

Der Anfangswert kann zusĂ€tzlich verwendet werden, um den Anfangszustand des Modells festzulegen (Zeile Nr. 0). Infolgedessen können Pseudozufallszahlen einfach durch Auswahl erhalten werdennBit von der mittleren Spalte, beginnend bei Zeile Null. Dieser Ansatz ist effektiver, hĂ€ngt jedoch stark von der QualitĂ€t des Anfangswertes ab. Ein falsch ausgewĂ€hlter Anfangswert kann zum Auftreten gut vorhergesagter Zahlen fĂŒhren. Eine Demonstration dieses Ansatzes finden Sie hier .

Regel 30 in der realen Welt


Regel 30 ist in der Natur in Form eines Musters auf der Schale der Gastropodenart Conus textile zu sehen . Der Bahnhof Cambridge North ist von Tafeln eingerahmt, die die Evolutionsergebnisse eines nach Regel 30 konstruierten Modells darstellen.

Zusammenfassung


Wenn Sie Regel 30 interessant finden, empfehle ich, Ihre eigene Simulation mit der p5- Bibliothek zu schreiben . Dieser Algorithmus kann in einer ziemlich allgemeinen Form implementiert werden, die es demselben Programm ermöglicht, Muster fĂŒr verschiedene Regeln zu generieren - 90, 110, 117 usw. Mit verschiedenen Regeln erzeugte Muster sind sehr interessant. Wenn Sie möchten, können Sie zum nĂ€chsten Level gehen. Sie können das Modell auf drei Dimensionen erweitern und die Entwicklung von Mustern untersuchen. Ich denke, dass das Programmieren viel Freude bereiten kann, wenn es eine visuelle Komponente hat.

Es ist erstaunlich, wenn zwei scheinbar nicht miteinander verbundene Bereiche der Wissenschaft, zellulĂ€re Automaten und Kryptographie, zusammen etwas Überraschendes ergeben. Obwohl der hier beschriebene Algorithmus aufgrund der Entstehung effizienterer Algorithmen nicht mehr weit verbreitet ist, ermutigt er uns, zellulĂ€re Automaten kreativ zu nutzen.

Liebe Leser! Welche Pseudozufallszahlengeneratoren verwenden Sie?

More articles:


All Articles