Komme mit Verwendung von Mersenne-Twister nicht ganz klar

Hallo,

ich habe hier den Mersenne-Twister in C++ runtergeladen, komme aber mit dessen Verwendung nicht ganz klar:

Header-Datei: http://www.bedaux.net/mtrand/mtrand.h.html
Cpp-Datei: http://www.bedaux.net/mtrand/mtrand.cpp.html

und der Code der Test-Datei:

// test program mttest.cpp, see mtreadme.txt for information
#include "mtrand.h"
#include <cstdio>

int main() {
  unsigned long init[4] = {0x123, 0x234, 0x345, 0x456}, length = 4;
  MTRand_int32 irand(init, length); // 32-bit int generator
// this is an example of initializing by an array
// you may use MTRand(seed) with any 32bit integer
// as a seed for a simpler initialization
  MTRand drand; // double in [0, 1) generator, already init

// generate the same numbers as in the original C test program
  std::printf("1000 32-bit integer random numbers:\n");
  for (int i = 0; i < 1000; ++i) {
    std::printf("%10lu ", irand());
    if ((i % 5) == 4) std::printf("\n");
  }
  std::printf("\n1000 random numbers in [0, 1):\n");
  for (int i = 0; i < 1000; ++i) {
    std::printf("%10.8f ", drand());
    if ((i % 5) == 4) std::printf("\n");
  }
}

Ich habe einen Vektor gegeben, der eine variable Größe haben kann, meist jedoch über eine Million Elemente enthält.
Nun möchte ich 1000 ganzzahlige Zufallszahlen erzeugen und zwar im Bereich von 0 bis zur Größe dieses Vektors. Aber ich krieg es mit obigem Code einfach nicht hin, dass er mir Zahlen in diesem Bereich ausspuckt.
Wo genau muss ich was im Code ändern, damit er das tut? Muss ich in Zeile

std::printf("%10lu ", irand());

irgendwie irand() durch irgendwas teilen teilen? Falls ja, durch was?

Danke für jede Antwort!

SeppJ

Natürlich musst du den Zufallszahlenbereich irgendwie transformieren. Wie genau, kommt auf deine Ansprüche an. Ein kleines modulo mit der gewünschten Obergrenze gibt dir schon einmal aus einer Gleichverteilung über einen größeren Bereich wieder eine Gleichverteilung mit der neuen, kleineren Obergrenze. Dieses Verfahren hat jedoch einen winzigen statistischen Fehler, da sich die konkreten Wahrscheinlichkeiten für bestimmte Werte um einen Wert 1/(Verhältnis von alter Obergrenze zu neuer Obergrenze) unterscheiden können, falls die Zahlen nicht genau aufeinander abgestimmt sind. Da beim Mersenne-Twister die alte Obergrenze 2^64 ist, ist dies in der Regel ein extrem kleiner Fehler.

Falls dich dieser Fehler stört, dann rechnest du erst einmal modulo der nächst größeren Zweierpotenz. Dies ist nämlich ein solcher Fall wo die Zahlen zueinander passen und man keinen statistischen Fehler macht. Dann wirfst du einfach alle Zahlen weg, welche dir zu groß sind. Nachteil dieser Methode ist natürlich größerer Rechenaufwand, da du nun im Schnitt mehr als eine Zufallszahlenziehung pro angenommener Zahl brauchst. Im schlimmsten Fall (neue Obergrenze ist um 1 größer als eine Zweierpotenz) kann der Durchschnitt sogar nahe bei 2 Ziehungen pro Zahl liegen.

Ich bin jetzt ehrlich gesagt etwas verwirrt, wieso jemand einen professionellen Zufallszahlengenerator benutzt aber solche Grundlagen nicht kennt. Habe ich irgendwie falsch verstanden, was du überhaupt wissen wolltest?

Hmm, ich brauche einfach Zufallszahlen, die im Bereich 0 bis mehrere Millionen liegen sollen. Man hat mir gesagt, ich solle den Mersenne-Twister dazu verwenden. Die Zahlen sollen so schnell wie möglich ermittelt werden, da später eine Laufzeitmessung erfolgen soll. Mit dem Twister hatte ich mich bisher nie beschäftigt. Falls jemand eine bessere Möglichkeit kennt große Zufallszahlen zu erzeugen...bin ganz Ohr.

volkard

SeppJ schrieb:

Im schlimmsten Fall (neue Obergrenze ist um 1 größer als eine Zweierpotenz) kann der Durchschnitt sogar nahe bei 2 Ziehungen pro Zahl liegen.

Je nach dem, was man will. Der Grund für die Zweierpotenz könnte auch darin liegen, bei manchen Rechnern oder compilezeitunbekannter Obergrenze die Division zu sparen.

Beispiel:
Ich brauche eigentlich x=rand64()%63.
Ich rechne nicht x=rand64()%128 und werfe alle x>=63 weg. Dazu ist der MT dann doch zu teuer.
Ich rechne (1<<64)%63=16, (1<<64)-16=18446744073709551600
Und mache y=rand(), werfe nur die paar y>=18446744073709551600 weg und mache x=y%63.

SeppJ schrieb:

Ich bin jetzt ehrlich gesagt etwas verwirrt, wieso jemand einen professionellen Zufallszahlengenerator benutzt aber solche Grundlagen nicht kennt. Habe ich irgendwie falsch verstanden, was du überhaupt wissen wolltest?

An der Wahl des Mersenne Twisters erkennt man meistens schon, daß ein Einsteiger am Werke ist. Mißt man ihn nämlich selber aus, kommt er viel langsamer an, als man gelesen hat.

SeppJ

volkard schrieb:

Beispiel:
Ich brauche eigentlich x=rand64()%63.
Ich rechne nicht x=rand64()%128 und werfe alle x>=63 weg. Dazu ist der MT dann doch zu teuer.
Ich rechne (1<<64)%63=16, (1<<64)-16=18446744073709551600
Und mache y=rand(), werfe nur die paar y>=18446744073709551600 weg und mache x=y%63.

Ahh, netter Trick, kannte ich noch nicht . Wobei du vermutlich 65 meinst, oder?

SeppJ

Heiliger schrieb:

Falls jemand eine bessere Möglichkeit kennt große Zufallszahlen zu erzeugen...bin ganz Ohr.

Was heißt hier groß? Die Größe spielt überhaupt gar keine Rolle bei Zufallszahlen. Das einzige was zählt sind deine Ansprüche an Geschwindigkeit und Verteilung. Das kann von einfachen linearen Kongruenzgeneratoren gehen die innerhalb von wenigen CPU Takten Zahlen ziehen aber die bei anspruchsvolleren statistischen Tests durchfallen, über professionellere Generatoren wie z.B. den von dir gewählten MT die gerne einen Faktor 10-100 langsamer sein können (was aber immer noch schnell ist!) aber dafür auch anspruchsvolle statistische Tests bestehen, bis hin zu kryptografisch sicheren Generatoren die dann schon sehr viel Aufwand betreiben. Deren Verteilungen sind dann zwar auch nicht besser als die vom MT, dafür sind aber noch bestimmte Anforderungen an die Berechenbarkeit des inneren Zustandes des Generators gegeben. Oder für die extrem gehobenen Ansprüche natürlich echte (d.h. physikalische) Zufallszahlengeneratoren. Da gibt es zwar prinzipiell auch extrem schnelle, aber das Problem ist oftmals die Anbindung die über irgendeine lahme Computerschnittstelle erfolgen muss.

Allen gemeinsam ist, dass die Wertebereiche der Zufallszahlen keine Rolle spielen. Selbst wenn der Generator nur 0 und 1 liefert, nimmt man eben 32 Stück um Zahlen zwischen 0 und 2^32 zu erzeugen.

Ok, danke. Dann weiß ich jetzt wie ich vorzugehen habe.

volkard

SeppJ schrieb:

Wobei du vermutlich 65 meinst, oder?

Klar.