Mersenne-Twister - aka besserer Zufallsgenerator

Übersicht

BlitzBasic

DLLs und Userlibs

	Thunder Betreff: Mersenne-Twister - aka besserer Zufallsgenerator	Do, Aug 17, 2017 21:08 Antworten mit Zitat
ganz kurz und bündig, ich hab eine Lib gebaut, die den Mersenne-Twister und den TT800 implementiert. Beides sehr gute Zufallsgeneratoren, sie haben lange Periodenlängen (MT wiederholt sich nach 2^19937-1 Zahlen, TT800 nach 2^800-1) und vermeiden Probleme die andere Zufallsgeneratoren haben. Siehe: https://de.wikipedia.org/wiki/...-Verhalten Erklärung der Funktionen für Mersenne-Twister (gilt analog für TT800 aber mit tt-präfix statt mt) mtSeed(seed%) ... wie SeedRnd mtSeedAll(seed) ... erlaubt das setzen des gesamten internen Zustands des Zufallsgenerators mit einer Bank (Größe bei Mersenne-Twister: 2496 Bytes, bei TT800: 100 bytes) mtRndInt%() ... liefert einen zufälligen Integer, also alles zwischen -2^31 bis +2^31-1 mtRnd#() ... wie Rnd* mtRand%(min%,max%) ... wie Rand, nur dass beide Parameter gegeben sein müssen. Wichtig: - Das sind Pseudozufallsgeneratoren, kein echter Zufall - Sie sind nicht kryptographisch sicher. Es reicht eine gewisse Menge an outputs zu kennen, um auf den internen State des Generators zu schließen. - trotzdem sind die erstellten Zufallszahlen von guter Qualität Wichtige Details (Kommentar zum Code): - die Init Funktion (die den 32 bit Seed über den internen State streuen) ist von mir adaptiert, nicht klar, wie sich das auf die Seeds auswirkt (worst case: mehrere seeds produzieren den gleichen internen state). - die Rand Funktionen bauen auf Rnd() auf. Bei großen Bereichen könnte es sein, dass manche Zahlen weniger wahrscheinlich sind als andere. - mtRnd(), ttRnd(), mtRand() und ttRand() holen sich intern je 64 bit zufall (weil damit ein zufälliger double mit 53 bit Mantisse zwischen 0 und 1 erstellt wird). ttRndInt() und mtRndInt() rufen nur 32 bit zufall ab. Download (ca 7 KB): https://www.blitzforum.de/upload/file.php?id=13305 Archiv enthält den C++ Code zum selber bauen, die DLL und die Decls datei, sowie einen Speedtest in BB.
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

Thunder

Betreff: Mersenne-Twister - aka besserer Zufallsgenerator

Do, Aug 17, 2017 21:08
Antworten mit Zitat

ganz kurz und bündig, ich hab eine Lib gebaut, die den Mersenne-Twister und den TT800 implementiert.
Beides sehr gute Zufallsgeneratoren, sie haben lange Periodenlängen (MT wiederholt sich nach 2^19937-1 Zahlen, TT800 nach 2^800-1) und vermeiden Probleme die andere Zufallsgeneratoren haben. Siehe: https://de.wikipedia.org/wiki/...-Verhalten

Erklärung der Funktionen für Mersenne-Twister (gilt analog für TT800 aber mit tt-präfix statt mt)
mtSeed(seed%) ... wie SeedRnd

mtSeedAll(seed*) ... erlaubt das setzen des gesamten internen Zustands des Zufallsgenerators mit einer Bank (Größe bei Mersenne-Twister: 2496 Bytes, bei TT800: 100 bytes)
mtRndInt%() ... liefert einen zufälligen Integer, also alles zwischen -2^31 bis +2^31-1
mtRnd#() ... wie Rnd

mtRand%(min%,max%) ... wie Rand

, nur dass beide Parameter gegeben sein müssen.

Wichtig:
- Das sind Pseudozufallsgeneratoren, kein echter Zufall
- Sie sind nicht kryptographisch sicher. Es reicht eine gewisse Menge an outputs zu kennen, um auf den internen State des Generators zu schließen.
- trotzdem sind die erstellten Zufallszahlen von guter Qualität

Wichtige Details (Kommentar zum Code):
- die Init Funktion (die den 32 bit Seed über den internen State streuen) ist von mir adaptiert, nicht klar, wie sich das auf die Seeds auswirkt (worst case: mehrere seeds produzieren den gleichen internen state).
- die Rand Funktionen bauen auf Rnd() auf. Bei großen Bereichen könnte es sein, dass manche Zahlen weniger wahrscheinlich sind als andere.
- mtRnd(), ttRnd(), mtRand() und ttRand() holen sich intern je 64 bit zufall (weil damit ein zufälliger double mit 53 bit Mantisse zwischen 0 und 1 erstellt wird). ttRndInt() und mtRndInt() rufen nur 32 bit zufall ab.

Download (ca 7 KB): https://www.blitzforum.de/upload/file.php?id=13305
Archiv enthält den C++ Code zum selber bauen, die DLL und die Decls datei, sowie einen Speedtest in BB.

Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

	diceman	Fr, Aug 18, 2017 21:00 Antworten mit Zitat
Echt Super! Vielen lieben Dank, kann ich grad gut gebrauchen!
Now these points of data make a beautiful line, And we're out of Beta, we're releasing on time.

diceman

Fr, Aug 18, 2017 21:00
Antworten mit Zitat

Echt Super!
Vielen lieben Dank, kann ich grad gut gebrauchen! Smile

Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.

	diceman	Mi, Aug 30, 2017 8:18 Antworten mit Zitat
Könntest du den mtSeedAll()-Befehl nochmal für Doofe erklären? Ist das das Pendant zu Blitz' RndSeed? Also daß ich den derzeitigen Status des Generators abrufe, nachdem dieser bereits ein paar Zahlen produziert hat? Vielen Dank! Außerdem: Was genau machen die .decl und die .cpp -Dateien? Die .dll gehört in den user-lib Ordner, soviel ist klar, und muß bei Distribution des Programms mitgeliefert werden (im Hauptverzeichnis).
Now these points of data make a beautiful line, And we're out of Beta, we're releasing on time.

diceman

Mi, Aug 30, 2017 8:18
Antworten mit Zitat

Könntest du den mtSeedAll()-Befehl nochmal für Doofe erklären? Smile

Ist das das Pendant zu Blitz' RndSeed? Also daß ich den derzeitigen Status des Generators abrufe, nachdem dieser bereits ein paar Zahlen produziert hat?
Vielen Dank!

Außerdem:
Was genau machen die .decl und die .cpp -Dateien?
Die .dll gehört in den user-lib Ordner, soviel ist klar, und muß bei Distribution des Programms mitgeliefert werden (im Hauptverzeichnis).

Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.

	DAK	Mi, Aug 30, 2017 16:46 Antworten mit Zitat
.decls kommen auch in den Userlib-Ordner. Die sagen dem Compiler und der IDE welche Funktionen er aus der DLL einbinden soll, so dass er sie nicht im BlitzBasic-Code sucht. Die cpp-Dateien werden der Sourcecode der DLL sein. Die brauchst du nur, wenn du die DLL selber compilieren willst.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Mi, Aug 30, 2017 16:46
Antworten mit Zitat

.decls kommen auch in den Userlib-Ordner. Die sagen dem Compiler und der IDE welche Funktionen er aus der DLL einbinden soll, so dass er sie nicht im BlitzBasic-Code sucht.

Die cpp-Dateien werden der Sourcecode der DLL sein. Die brauchst du nur, wenn du die DLL selber compilieren willst.

Gewinner der 6. und der 68. BlitzCodeCompo

	Lobby	Mi, Aug 30, 2017 18:09 Antworten mit Zitat
Nein, einen Befehl wie BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] RndSeed scheint es hier nicht zu geben. Sehr viel mehr verwundert mich, was mtSeed im Detail macht, denn der Zustand des Generators ist hier eben nicht nur ein int sondern einige Bytes mehr. mtSeedAll ist dazu da um den ganzen Zustand zu setzen.
TheoTown - Eine Stadtaufbausimulation für Android, iOS, Windows, Mac OS und Linux

Lobby

Mi, Aug 30, 2017 18:09
Antworten mit Zitat

Nein, einen Befehl wie BlitzBasic: [AUSKLAPPEN]

RndSeed

scheint es hier nicht zu geben.

Sehr viel mehr verwundert mich, was mtSeed im Detail macht, denn der Zustand des Generators ist hier eben nicht nur ein int sondern einige Bytes mehr. mtSeedAll ist dazu da um den ganzen Zustand zu setzen.

TheoTown - Eine Stadtaufbausimulation für Android, iOS, Windows, Mac OS und Linux

	Thunder	Do, Aug 31, 2017 18:55 Antworten mit Zitat
Wie gesagt, der interne zustand dieser Zufallsgeneratoren ist sehr groß (der Mersenne-Twister hat einen Zustand von 624 * 32 Bit), also kann ich keinen Befehl wie RndSeed bereitstellen, der nur ein Int zurückgibt. Es wäre natürlich möglich einen Befehl zu schreiben, der eine Bank mit den internen Zustandsbits des Zufallsgenerators füllt (das wäre dann ein Pendant zu den SeedAll-Befehlen, siehe unten). mtSeedAll setzt den gesamten Zustand der Zufallsgeneratoren, indem du eine Bank als Parameter übergibst die so groß ist, wie der interne Zustand des jeweiligen Generators. Die Bits werden dann einfach hinüberkopiert. Die SeedAll-Befehle sind die einzigen, mit denen du die Generatoren wirklich vollständig seeden kannst. Mit den *Seed-Befehlen hast du nur 32 bits seed für einen Zustand, der viel mehr als 32 bits hat (in dem Fall werden durch einen einfacheren Zufallsgenerator die Zustandsbits aus dem 32 bit seed erzeugt). Ich hoffe das war halbwegs verständlich. Ansonsten haben Lobby und DAK alles gesagt glaube ich.
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

Thunder

Do, Aug 31, 2017 18:55
Antworten mit Zitat

Wie gesagt, der interne zustand dieser Zufallsgeneratoren ist sehr groß (der Mersenne-Twister hat einen Zustand von 624 * 32 Bit), also kann ich keinen Befehl wie RndSeed

bereitstellen, der nur ein Int zurückgibt. Es wäre natürlich möglich einen Befehl zu schreiben, der eine Bank mit den internen Zustandsbits des Zufallsgenerators füllt (das wäre dann ein Pendant zu den *SeedAll-Befehlen, siehe unten).

mtSeedAll setzt den gesamten Zustand der Zufallsgeneratoren, indem du eine Bank als Parameter übergibst die so groß ist, wie der interne Zustand des jeweiligen Generators. Die Bits werden dann einfach hinüberkopiert. Die *SeedAll-Befehle sind die einzigen, mit denen du die Generatoren wirklich vollständig seeden kannst. Mit den *Seed-Befehlen hast du nur 32 bits seed für einen Zustand, der viel mehr als 32 bits hat (in dem Fall werden durch einen einfacheren Zufallsgenerator die Zustandsbits aus dem 32 bit seed erzeugt).

Ich hoffe das war halbwegs verständlich. Ansonsten haben Lobby und DAK alles gesagt glaube ich.

Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

Übersicht

BlitzBasic

DLLs und Userlibs

Nach Oben

BlitzBasic Portal

Mersenne-Twister - aka besserer Zufallsgenerator

Thunder

Betreff: Mersenne-Twister - aka besserer Zufallsgenerator

diceman

diceman

DAK

Lobby

Thunder