Ruby implementiert PRNGs als "einen modifizierten Mersenne Twister mit einer Periode von 2 ** 19937-1." 1
So wie ich MT verstehe, funktioniert es auf 2 ^ 32 verschiedenen Samen. Was mich verwirrt ist, dass Random.new(seed) beliebig große Zahlen wie Random.new(2**100) akzeptiert.
Ich konnte jedoch (logische) Kollisionen nicht finden:
%Vor%Wenn wir den maximalen Saatgutbereich von MT in dem Sinne nutzen möchten, dass wir so viele verschiedene Samen wie möglich verwenden und gleichzeitig Kollisionen mit zwei verschiedenen Samen vermeiden, was erreicht dieser Samenbereich?
Ich habe versucht zu verstehen, was in der zufälligen Implementierung von Ruby passiert, bin aber nicht zu weit gegangen. Ссылка
Die Mersenne-Twister-Sequenz ist 2 ** ( 624 * 32 - 1 ) - 1 lang, und der Startwert wird verwendet, um einen internen Status für den PRNG festzulegen, der sich direkt auf die Position innerhalb dieser Sequenz bezieht.
Die am einfachsten zu findende Wiederholung scheint alle 2 ** ( 624 * 32 ) zu sein, und es kann gezeigt werden, dass sie so funktioniert:
Oder versuchen Sie Folgendes:
%Vor%Der Wiederholungswert bezieht sich auf die Funktionsweise von Mersenne Twister. Der interne Zustand von MT ist ein Array von 624 32-Bit-Ganzzahlen ohne Vorzeichen. Der verknüpfte Ruby-Quellcode packt einen Ruby Fixnum in ein Array - der magic-Befehl ist
%Vor% Allerdings ist dies nicht einfach zu handhaben, es ist in internal.h definiert, also nur wirklich zugänglich, wenn Sie am Ruby-Interpreter selbst arbeiten. Sie können nicht auf diese Funktion innerhalb einer normalen C-Erweiterung zugreifen.
Die gepackte Ganzzahl wird dann mit der Funktion init_by_array in den internen Status des MT geladen. Dies ist eine ziemlich komplex aussehende Funktion - der gepackte Startwert wird nicht wörtlich in den Status geschrieben, sondern der Status wird Element für Element generiert, indem die angegebenen Array-Werte hinzugefügt werden, wobei eine Vielzahl von XORs, Additionen und Querverweisen verwendet werden vorheriger Wert (die Ruby-Quelle fügt hier auch die Indexposition des gepackten Arrays hinzu, kommentierte "nicht-linear", ich denke, das ist eine der referenzierten Modifikationen des Standard-MT)
Beachten Sie, dass die Größe der MT-Sequenz kleiner ist als 2 ** ( 624 * 32 ) - der repeat_every -Wert, den ich hier zeige, überspringt jeweils 2 Sequenzen gleichzeitig, ist aber am einfachsten zu finden Seed-Wert, weil es leicht zu sehen ist, wie es den internen Zustand genau gleich setzt (weil die ersten 624 Items in der Array-Repräsentation des Seeds identisch sind, und das ist alles, was später verwendet wird). Andere Startwerte erzeugen ebenfalls denselben internen Status, aber die Beziehung ist eine komplexe Zuordnung, die jede Ganzzahl im 19938-Bit-Bereich mit einer anderen Ganzzahl kombiniert, die denselben Zustand für MT erzeugt.
Tags und Links ruby random random-seed mersenne-twister