Mersenne-Twister, state-vector-Länge und period-parameter

tomax

Hi,

ich hab mir unter http://www-personal.umich.edu/~wagnerr/MersenneTwister.html
eine C++-Implementation vom "Mersenne-Twister" runtergeladen
und funktioniert auch.

Mein simpler Test-Code sieht so aus:

MTRand mtrand;
mtrand.seed(123);
for(i = 0; i < 128; ++i) {
    cout << mtrand.randInt() << " ";
}

Den Quellcode der Header-Datei kann man dabei hier sehen:
http://www-personal.umich.edu/~wagnerr/MersenneTwister.h

Mir geht es um die beiden Konstanten in den Zeilen 75 und 79:

enum { N = 624 };     // length of state vector
enum { M = 397 };     // period parameter

Je kleiner ich N setze, desto schneller wird dabei anscheinend das Test-Programm,
in einigen Fällen darf N aber nicht kleiner M sein, sonst "Segementation Fault".
Nur wie wirkt sich die Manipulation von N und/oder M auf die Qualität der
erzeugten Zufallszahlen aus ?

Mein Ziel ist es, in einer Schleife möglichst schell und hochwertig
pro seed 128 uint-Zufallszahlen zu erzeugen, denn seed wechseln
und wieder 128 uint-Zufallszahlen erzeugen, seed wechseln usw.

Wie muss ich dafür N und M für eine möglichst schnelle und hochwertige
Ausführung setzen ?

Christoph

Ich denke nicht, dass diese Konstanten dafür gedacht sind, geändert zu werden. Die Eigenschaften von Pseudozufallszahlen-Generatoren hängen normalerweise ganz entscheidend von solchen "magischen" Konstanten ab. Diese Konstanten richtig zu wählen ist aber alles andere als trivial und oft mit komplizierter Mathematik verbunden.
Solange du nicht die Mathematik hinter Mersenne Twister nachvollzogen hast, würde ich diese Konstanten so lassen, wie sie sind. Wenn du sie änderst, kannst du davon ausgehen, dass du wahrscheinlich nur noch ziemlich schlechte Zufallszahlen erhältst, weil die mathematischen Eigenschaften nicht mehr gegeben sind.

SeppJ

N und M (und auch die ganzen anderen Zahlen die vorgegeben sind) solltest du besser nicht anrühren.

tomax schrieb:

Mein Ziel ist es, in einer Schleife möglichst schell und hochwertig
pro seed 128 uint-Zufallszahlen zu erzeugen, denn seed wechseln
und wieder 128 uint-Zufallszahlen erzeugen, seed wechseln usw.

Das hört sich äußerst abenteuerlich an. Wieso willst du das machen?

tomax

schade, dann muss ich N und M wohl so lassen, aber trotzdem danke für die
Antworten.

Ein wenig irritiert mich am Mersenne-Twister,
dass das wiederholte "setzen eines seeds mit anschliessender
Erzeugung von 128 Zufallzahlen" auf meinem Rechner ein wenig langsamer
ist, als wenn man das mit srandom(seed)/random() macht.
Denn der "Mersenne-Twister" wird ja als "very fast" gepriesen.

Warum ich Zufallszahlenketten mit wechselnden Seed erzeugen will,
hat den Hintergrund von "vorhersagbaren Zufallszahlen".
Ich benötige einen Pool von Pseudo-Zufallszahlenketten.
Ein paar von den Zahlenketten will ich mir für spätere Weiterverarbeitung
merken, aus Resourcengründen möchte ich aber nicht die Zufallszahlen
selbst speichern, sondern nur den seed und später im
Programm die Zufallszahlenkette erneut erzeugen.

volkard

tomax schrieb:

Denn der "Mersenne-Twister" wird ja als "very fast" gepriesen.

Alle meine Messungen hatten den MT recht langsam. Schon seit vielen Jahren. Fein, daß ich von Dir mal meine Messungen bestätigt finde. Ob die "very fast" nun hype sind oder Lüge oder ich nur immer die falsche Hardware kaufe, wer weiß?
Ich bevorzuge den MWC.

SeppJ

tomax schrieb:

Warum ich Zufallszahlenketten mit wechselnden Seed erzeugen will,
hat den Hintergrund von "vorhersagbaren Zufallszahlen".
Ich benötige einen Pool von Pseudo-Zufallszahlenketten.
Ein paar von den Zahlenketten will ich mir für spätere Weiterverarbeitung
merken, aus Resourcengründen möchte ich aber nicht die Zufallszahlen
selbst speichern, sondern nur den seed und später im
Programm die Zufallszahlenkette erneut erzeugen.

Denk daran, dass der Mersenne-Twister nicht gut darauf anspricht, wenn man ihm keinen vollständigen Seed gibt. Und der ist 624 Wörter lang (weiß jetzt nicht genau welcher Datentyp, vermutlich 32-Bit Wörter). Das könnte länger sein als deine 128 Zufallszahlen.

volkard schrieb:

tomax schrieb:

Denn der "Mersenne-Twister" wird ja als "very fast" gepriesen.

Alle meine Messungen hatten den MT recht langsam. Schon seit vielen Jahren. Fein, daß ich von Dir mal meine Messungen bestätigt finde. Ob die "very fast" nun hype sind oder Lüge oder ich nur immer die falsche Hardware kaufe, wer weiß?
Ich bevorzuge den MWC.

Hallo? Er vergleicht den MT mit rand aus der Standardbibliothek! Wer weiß was dahinter für ein Algorithmus steht. Vermutlich irgendein LCG.

@Threadersteller: MT ist höst sich ein bisschen nach Overkill für deine Zwecke an. Wahrscheinlich bist du mit einem etwas einfacheren Algorithmus wie TAUS2 oder GFSR4 besser beraten. Die sind auch für Simulationen geeignet.
Wo wir gerade von der Anwendung sprechen: Was für ein Anwendungszweck liegt hier denn vor?

volkard

SeppJ schrieb:

Hallo? Er vergleicht den MT mit rand aus der Standardbibliothek! Wer weiß was dahinter für ein Algorithmus steht. Vermutlich irgendein LCG.

Angefangen habe ich zu messen als der MT recht neu war. Damals wurde er auf der MT-Seite gegen normale LCGs getestet (genau aus Standard-) und war angeblich deutlich schneller. Konnte ich nicht messend bestätigen. Vielelich weil ich den LCG von Microsoft als Standard hatte, nee, ich hab ja auch andere versucht, aber MS-Compiler waren es schon. Und nur x86-Hardware.
Vielleicht ist der MT gut, wenn man ein ordentliches Motherboard hat, aber kackt ab, wenn man einen 60€-Prozessor(war vor 2 Jahren 240€ und ist noch geil) auf ein 40€-Board(war immer nur als Schrott designed) steckt.

tomax

Morgen,

SeppJ schrieb:

Hallo? Er vergleicht den MT mit rand aus der Standardbibliothek! Wer weiß was dahinter für ein Algorithmus steht. Vermutlich irgendein LCG.

Heißt daß, das der MT schon langsamer sein kann und darf als rand aus der Standardbibliothek,
denn dafür liefert er hochwertigere Zufallszahlen ?

Ich kenn mich auch nicht sonderlich gut aus mit der bunten Welt der PRNG's,
MWC, TAUS2 oder GFSR4 kenne ich noch gar nicht. Ich werde mich mal allgemeiner
versuchen schlau zu machen über PRNG's.

SeppJ schrieb:

Denk daran, dass der Mersenne-Twister nicht gut darauf anspricht, wenn man ihm keinen vollständigen Seed gibt. Und der ist 624 Wörter lang (weiß jetzt nicht genau welcher Datentyp, vermutlich 32-Bit Wörter). Das könnte länger sein als deine 128 Zufallszahlen.

Hm, versteh ich nicht ganz, aber vielleicht löst die fertige
C++-Implementierung, die ich runtergeladen habe, die Problematik ja schon,
dort kann der seed einfach über einen uint gesetzt werden.

SeppJ schrieb:

Was für ein Anwendungszweck liegt hier denn vor?

Das ist gar nicht so einfach zu erklären und würde den Thread thematisch sprengen. Ich mach später vielleicht nen neuen Thread auf.

SeppJ

tomax schrieb:

Heißt daß, das der MT schon langsamer sein kann und darf als rand aus der Standardbibliothek,
denn dafür liefert er hochwertigere Zufallszahlen ?

Jain. Es ist nicht festgelegt, was für ein Generator hinter rand steckt. Meistens dürfte das ein einfacher LCG sein. Die sind sehr schnell und liefern keine sehr guten Zufallszahlen. MT ist wesentlich langsamer und liefert wesentlich bessere Zufallszahlen, die auch für professionelle (aber nicht kryptografische!) Anwendungen geeignet sind. Für Hobbyzwecke (Spieleprogrammierung und so) ist aber auch ein LCG gut genug.

SeppJ schrieb:

Denk daran, dass der Mersenne-Twister nicht gut darauf anspricht, wenn man ihm keinen vollständigen Seed gibt. Und der ist 624 Wörter lang (weiß jetzt nicht genau welcher Datentyp, vermutlich 32-Bit Wörter). Das könnte länger sein als deine 128 Zufallszahlen.

Hm, versteh ich nicht ganz, aber vielleicht löst die fertige
C++-Implementierung, die ich runtergeladen habe, die Problematik ja schon,
dort kann der seed einfach über einen uint gesetzt werden.

Der MT spricht sehr schlecht darauf an, wenn man ihn nur mit wenigen Zahlen als seed füttert (weil dann der Rest des internen Zustands am Anfang auf 0 gesetzt wird). Dann muss man erstmal ein paar tausend Zahlen ziehen bis er richtig in Gang gekommen ist.

Was ich oben meinte ist, dass der interne Zustand (also ein vollständiger Seed) länger ist als 128 Zahlen. Daher wäre es einfacher diese 128 Zahlen zu speichern als einen vollständigen Seed. Falls du aber wie du vorschlägst bloß einen int als Seed nimmst, solltest du wie schon gesagt den MT erstmal etwas Anlaufzeit geben, bevor du die Zahlen aufzeichnest.
MT ist halt nicht wirklich darauf ausgelegt, 128 Zufallszahlen zu liefern, sondern eher ein paar Millionen und aufwärts.

tomax

jetzt hab ich die MT-Problematik verstanden, danke.

tomax

habe jetzt übrigens mal den MWC-Generator von der Performance
auf wiederholtes "seed setzen und 128 Zufalls-UINT erzeugen" getestet.

Er ist in dieser Einsatzart deutlich schneller als rand aus der Standardlib
und damit auch schneller als der MT.
Über die Güte der Zahlen kann ich jedoch bislang nichts sagen.

Dank für Info und Gruß

wxSkip

Übrigens erzeugt rand() bei mir nur Zahlen zwischen 1 und 32767 während der MT bis 2^32-1 geht, von daher auch verständlich, wenn das ein bisschen länger dauert.
Unter ein paar Millionen Zufallszahlen ist da aber nix zu spüren.