Mersenne-Twister Funktionsweise

Werbeanzeige

Sk!p

Alter Hase

Beiträge: 568

28.12.2013, 19:37

Mersenne-Twister Funktionsweise

Hallo,

unter anderem bei den Contests habe ich den folgenden Mersenne-Twister gefunden und ein paar Fragen zu.
Die erste wäre die, was in der Funktion Seed passiert. Ich habe gelesen, dass man die ersten 624 Startwerte vorgibt, aber hier werden die ja nach einem ganz bestimmten Pattern erzeugt. Woher kommt das? Wie heißt diese Methode und wie kommt man auf die genauen Faktoren?

C-/C++-Quelltext

// Mersenne Twister-Zufallsgenerator
class MTRand
{
public:
    MTRand(uint seed = 0) { this->seed(seed); }

    void seed(uint seed)
    {
        next = 0;
        const unsigned long long int factor = 69069;
        mt[0] = seed;
        for(uint i = 1; i != 624; ++i) mt[i] = static_cast<uint>(factor * mt[i - 1] + 1);
    }

    float float_0_to_1()
    {
        const uint x = (*this)() & 0xFFFFFF;
        return static_cast<float>(x) / 0xFFFFFF;
    }

    uint operator ()()
    {
        if(next == 624) { generateNumbers(); next = 0; }
        uint x = mt[next++];
        x ^= x >> 11;
        x ^= (x << 7) & 0x9D2C5680;
        x ^= (x << 15) & 0xEFC60000;
        x ^= x >> 18;
        return x;
    }

private:
    void generateNumbers()
    {
        const uint xorTab[] = { 0, 0x9908B0DF };
        for(uint i = 0; i != 227; ++i) { const uint x = (mt[i] & 0x80000000) | (mt[i + 1] & 0x7FFFFFFF); mt[i] = mt[i + 397] ^ (x >> 1) ^ xorTab[x & 1]; }
        for(uint i = 227; i != 624; ++i) { const uint x = (mt[i] & 0x80000000) | (mt[i + 1] & 0x7FFFFFFF); mt[i] = mt[i - 227] ^ (x >> 1) ^ xorTab[x & 1]; }
        const uint x = (mt[623] & 0x80000000) | (mt[0] & 0x7FFFFFFF);
        mt[623] = mt[396] ^ (x >> 1) ^ xorTab[x & 1];
    }

    uint mt[624];
    uint next;
};

Zum Seitenanfang

Legend

Alter Hase

Beiträge: 731

Beruf: Softwareentwickler

29.12.2013, 01:17

Das einzige was ich sicher weiß, ist das der MT bei falsche Initialisierung dieses Arrays (z.B. alles 0 wenn ich mich richtig erinnere) keinerlei Zufall produziert. Und wenn die Initialisierung relativ "wenig" zufällig ist, soll es eine Weile dauern bis der MT trotzdem qualitativ gute Zufallszahlen generiert.

"Wir müssen uns auf unsere Kernkompetenzen konzentrieren!" - "Juhu, wir machen eine Farm auf!"

Netzwerkbibliothek von mir, C#, LGPL: https://sourceforge.net/projects/statetransmitt/