[Metalab] brauche zufallszahlengenerator

[Clifford Wolf]

Hi,

On Thu, Feb 23, 2012 at 09:41:54PM +0000, matthias liszt wrote:
> ja, und zwar mit ziemlich langer periode , so ca. 10 Milliarden ...
> vielleicht hats ja grad wer bei der hand ...

der klassiker waere der Mersenne-Twister [1]. ich persoenlich verwende
aber sehr gerne xorshift128 [2]. von ?rand48 wuerde ich abraten. ich hab
kuerzlich erst zwei tage damit zugebracht einen bug auf die schlechte
zufaelligkeit (in den unteren bits) von ?rand48 zurueckzufuehren..

xorshift128 besteht die Diehard testsuite und die TestU01 testsuite
(Mersenne-Twister faellt in TestU01 bei den tests auf lineare Komplexität
durch -- das sollte aber in der regel nicht stoerend sein). xorshift128
hat eine periodenlaenge von 2^128 - 1. Das ist in der groessenordnung
von 10^38. Also 100 Millionen mal 10 Milliarden mal 10 Milliarden mal
10 Milliarden.

Die Periodenlaege vom Mersenne-Twister ist so gross, dass es unsinnig ist
noch von einer periode zu sprechen. ich hab jetzt nachgesehen: sie ist in
der Groessenordung von 10^6000. Das ist ein fsck'in googol hoch 60!

Die C-implementierung von xorshift128 sieht so aus:

--snip--
uint32_t xor128(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;
 
  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
--snap--

Bei der initializierung muss man nur darauf achten, dass mindestens ein bit
in den zustandsregistern x, y, z und w gesetzt ist. wenn ganz wenige oder
nur ein bit gesetzt sind braucht xorshift128 etwa 10 zyklen in einen
zustand mit gleichverteilten bits. (Mersenne-Twister etwa 800.000). D.h.
es ist im zweifelsfall ausreichend den zustand irgendwie zu setzen, dann
ein bit auf 1 zu zwinden und 10 zyklen laufen zu lassen. das finde ich sehr
praktisch, weil so bei der initialisierung nichts schief laufen kann..

von xorshift128 habe ich auch eine javascript implementierung geschrieben:
http://svn.clifford.at/handicraft/2011/eetrainer/pseudorand.js

lg,
 - clifford

[1] http://en.wikipedia.org/wiki/Mersenne_twister
[2] http://en.wikipedia.org/wiki/Xorshift

-- 
You can never learn too much linear algebra.
 -- Prof. Benedict Gross in the 2003 Harvard abstract algebra course