Frage zu srand()

Hallo,

ich habe für mich und einen Freund ein Spiel geschrieben, das über Netzwerk gespielt werden kann. Dabei hängt vieles von rand() ab. Vorher habe ich srand(time(0) benutzt. Allerdings kam es oft vor, dass wir in der gleichen Sekunde gestartet haben. Ich bin jetzt also auf der Suche, nach möglichst "zufälligen" Startwerten. Im Moment benutze ich folgendes:

unsigned int randomnumber(0); //variable initialisieren

randomnumber = time(0) % 100000000; //mit Zeit seit 1970 verrechnen

randomnumber += (GetTickCount() % 100000000); //mit Zeit seit Systemstart verrechnen

unsigned int *array = new unsigned int [ 100 ];  // int array
unsigned int tmp = (array[23] / 2);              // anlegen und
tmp += (array[47] / 2);                          // zwei nicht
randomnumber += (tmp % 100000000);               // initialisierte Werte
delete [] array;                                 // verrechnen

srand(randomnumber); //schließlich kombination aus den 3
                     //"Verfahren" für srand benutzen

Hat jemand weitere Ideen bzw. verbesserungsvorschläge, wie man das weiter "randomisieren" kann?

Firefighter

Eventuell wäre das für dich etwas:

boost random libary

Danke für die Anregung,
Allerdings ist das eher ein kleines Projekt und ich wollte jetzt keine weiteren Librarys einbauen bzw. mich da einarbeiten

Ich habe jetzt meinen algorithmus etwas geändert

unsigned int randomnumber(0);
srand(time(0));
randomnumber = time(0) % 1300000000;
randomnumber += (GetTickCount() % 1300000000);

unsigned int *array = new unsigned int [ 1000 ];  
unsigned int tmp = (array[rand()%1000] / 2);     // Das Arrayelement
tmp += (array[rand()%1000] / 2);                 // zufällig bestimmen
randomnumber += (tmp % 1300000000);
delete [] array;

srand(randomnumber); //schließlich kombination aus den 3 
                     //"Verfahren" für srand benutzen

Allerdings gibt es bei der Methode ein Problem:
Die beiden Werte aus dem Array sollten ja mit einer zufälligen Bit Sequenz belegt sein und somit einen zufälligen Wert repräsentieren. Allerdings waren in meinen Testläufen die Werte dieser beiden elemente immer 0. Hat jemand eine Ahnung, wie ich an "wirklich nicht initialisierte Werte im Arbeitsspeicher ungleich 0" herankomme?
Und hat jemand weitere Ideen, wie "zufällige" Werte mit in den Seed Wert einfließen könnten?

BTW: erwartet srand int oder unsigned int? Also kann die Funktion auch mit Werten größer int_max und kleiner unsigend_int_max umgehen (ca. 4 Mrd)?

freaky

http://www.cplusplus.com/reference/clibrary/cstdlib/srand/
Wie du siehst ein unsigned int.
srand benutze ich eig. immer so:

srand(unsigned(time(NULL)));

Du kannst es damit mal versuchen.

Ok, Danke für den Tipp.

Ich habe gerade herausgefunden, dass, wenn ich das Array nicht mit new sondern statisch auf dem Stack über int array[1000] erzeuge, die einzelnen Arraywerte wirklich uninitialisiert und ungleich 0 sind. Liegt das an meinem Compiler oder ist dieses Verhalten "normal" ?

freaky

Das ist normal. Wenn ich über new ein int Array anlege, sind die Werte nach dem 2. Wert des Arrays bei der Ausgabe alle gleich 0. Bei dem Stack Array jedoch kommen andere Werte raus.

volkard

srand() schrieb:

Ich habe jetzt meinen algorithmus etwas geändert
[cpp]
unsigned int randomnumber(0);
srand(time(0));

nein. niemals unklare algorithmen benutzen, um die zufälligkeit zu verbessern.
bleib beim alten aussummieren der einzelzufälle. vielleicht mit zwischendurch bekannter bitverwürfelung wie randomnumber*=2654435761;
[cpp]randomnumber+=time(0);
[/cpp]
klar.

randomnumber = time(0) % 1300000000;

warum das %1300000000?

randomnumber += (GetTickCount());

klar.

srand(randomnumber); //schließlich kombination aus den 3 
                     //"Verfahren" für srand benutzen

auch klar, darum gehts ja.

Und hat jemand weitere Ideen, wie "zufällige" Werte mit in den Seed Wert einfließen könnten?

mußt du eine ini-datei laden? wenn ja, muß die zeit dafür, dann haste eine leckere abhängigkeit von mechanischen teilen der festplatte.

außerdem schau

inline long long rdtsc(){
  __asm rdtsc;
}

an.

außerdem vielleicht mausposition, clock(), prozessorauslastung, menge des freien speichers, freier festplattenplatz, ip-adresse, falls dein prog am netzt hängen muss, ping-zeit nach google.de und vielleicht gibs ja random-server-dienste ( http://random.irb.hr/ ), auf dem 64-er hat man die soundkarte beauftragt, rauschen auszugeben und hats wieder aufgenommen, gibt es weitere rauschquellen wie angeschlossene mikrofone oder webcams, irgendwo kann man bestimmt leicht auslesen, wielange das windows schon läuft, screenshot machen und hashen (crc32 oder orgendein string-hash reicht, muß nicht immer md5 sein), prozessliste auslesen und hashen, numlock-status, mal schnell 20M mit new allokieren und und die zeit messen und damit wieder von platte anderen prozessen und dergleichen abhängig werden, einfach mal die ersten 10000 primzahlen berechnen (eratostenes, cache-effekte) und die zeit mit rdtsc messen, ...
da kann man sich jahrelang austoben und immer noch was neues einfließen lassen.

Danke für die ganze Flut an Tipps!

Jetzt bin ich erstmal ne Weile beschäftigt, das zu implementieren

Wirklich tolles Forum und kompetente Leute

volkard

Aber eigntlich glaube ich, daß

unsiged long long randomnumber=0;//unsigned __int64
randomnumber+=rdtsc();
randomnumber*=2654435761;
srand(randomnumber);

völlig ausreichend ist.
Die Anzahl der Prozessortakte seit der Rechner an ist. In nur einer Sekunde zählt der bei einem 1GHz-Rechner um eine Milliarde hoch, das sind 30 Bits! Wenn der Mensch beim Starten im Spiel ist, solltest Du dabei locker 30 zufällige Bits gewonnen haben. Relativ eintönig könnte es nur werden, wenn das Prog beim Windows-Start automatisch mitgestartet wird und deshalb immer in der gleichen Zehntel-Sekunde nach Anmachen startet (immernoch 26 Bits!).

Zur Sicherheit dazu noch die GetSystemTimeAsFileTime addieren, also die Uhrzeit mit 100ns-Auflösung und der Käse ist gegessen.

unsiged long long randomnumber=0;//unsigned __int64

randomnumber+=rdtsc();
randomnumber*=2654435761;

//ungetestet
FILETIME ft;
GetSystemTimeAsFileTime(&ft);
ULARGE_INTEGER uli;
uli.LowPart=dwLowDateTime;
uli.HighPart=dwHighDateTime;
randomnumber+=uli.QuadPart;
randomnumber*=2654435761;

srand(unsigned(randomnumber));

Die Zufälligkeit entsteht durch die Anzahl der einfließenden Bits und die Machtlosigkeit des Zufall-Angreifers, die Zeiten auf viel weniger als eine Sekunde schätzen zu können. Er kann schlecht auf die Zehntelsekunde genau raten, wie lange der Rechner schon an ist (26 Bits), er kann schlecht auf die Zentelsekunde die Uhrzeit raten (23 Bits).
Das Bitverwürfeln bringt keinen Sicherheitsgewinn. Das soll nur dafür sorgen, daß die vorderen Bits aus Stunde und Jahr auch hinten wirken, und nicht langweilig abgeschnippelt werden.

der cast in

srand(static_cast<unsigned int>(randomnumber));

oder gleichwertig

srand(unsigned(randomnumber));

hat nur den sinn, die compilerwarnung "achtung: da werden bits weggeworfen" wegzumachen. weggeworfen werden sie eh, wenn srand einen unsigned int will und randomnumber mehr bits hat.

Das habe ich ja versuch, mit "% 1300000000" zu verhindern.
Für den Fall, dass time(0) eine Zahl größer als 1,3Mrd ausgibt, wird die Zahl entsprechend verkleinert. Ebenso für GetTickCount() (wenn der Rechner mehrere Tage an ist) und die Zahlen aus dem Array (diese könnten ja zusammen 4,2 Mrd, also unsigned_int_max sein). Somit kann in keinem Fall ein Overflow für unsigned int entstehen, denn die drei Zahlen zusammen sind maximal 3,9Mrd groß.

Ich habe das jetzt folgendermaßen implementiert. Fünf Faktoren sollten für meinen Zweck mehr als ausreichend sein (soll ja keine professionelle Anwendung sein; daher ist es mir auch egal, wenn es "unsauber" implementiert ist. Trotzdem bin ich für Anregungen und Tipps dankbar! :D)

unsigned int inittime = GetTickCount();    
//irgendwas mehr oder weniger zeitaufwendiges anstellen

srand(unsigned(time(0)));

unsigned int randomnumber(0);

randomnumber = time(0) % 1300000000;            // sekunden seit 1970

randomnumber += (GetTickCount() % 1300000000);  // ms seit PC start

unsigned int array [ 1000 ];                    // int array
unsigned int tmp = (array[rand()%1000] / 2);    // anlegen und
tmp += (array[rand()%1000] / 2);                // zwei nicht
randomnumber += (tmp % 1300000000);             // initialisierte Werte
                                                // verwenden

POINT pt;                                       // Mauszeigerposition verwenden
::GetCursorPos( &pt );
randomnumber += pt.x;
randomnumber += pt.y;

inittime = GetTickCount() - inittime;           // Gucken, wie lang der Rechner für den
randomnumber += inittime;                       // initialisierungsprozess braucht

srand(randomnumber); //srand initialisieren mit 5 Faktoren

volkard

srand() schrieb:

randomnumber += pt.x;
randomnumber += pt.y;

Da ihr beide das Spiel übers Menu startet und zufällig den Eintrag auch an der gleichen Position habt, ist der Zufall auf sagen wie mal +-10 pixels in x- und y-Richtung beschränkt. Sagen wir der Einfachheit halber mal, es seien nur die 21 werte zwischen 0 und 20 möglich.

pt.x+pt.x kann dann nur die 41 verschiedenen werte zwischen 0 und 40 annehmen.
pt.x*100+pt.y könnte aber 21*21=441 verschiedene werte annehmen. (Ah, das ist also der wahre Grund fürs Bitverwürfeln.)

also

volkard schrieb:

randomnumber += pt.x*100;
randomnumber += pt.y;

Ich initialisiere srand beim Start des Programms. Das bedeutet, dass es also darauf ankommt, wo sich die exe des Programms befindet. Also ist es schon OK so.

volkard

es ist immernoch schädlich, einen zufall vom anderen abhängig zu machen.
erst srand(time(0)) und dann rand() als arrayindizes zu nehmen, ist einfach nicht ok. vielleicht kommen in den "zufälligen" arraywerten gleiche werte vor. egal, welche der beiden kombinierten zufallsquellen schwächelt, zufällig die gleiche sekunde oder zufällig der gleiche speicherinhalt, die abhängige kombination schwächelt als folge erst recht.

benutze die beiden quellen getrennt.

randomnumber += (time(0) % 1300000000);

und

//array anlegen und auf zufällige werte drin hoffen
unsigned int array [100];

//hashcode aller werte berechnen, sollte nicht länger als eine mikrosekunde dauern
unsigned int tmp = 0;
for(int i=0;i<100;++i)
   tmp=tmp*33+array[i];

//und dem zufall zufügen
randomnumber += (tmp % 1300000000);

Das ist eine gute Idee. Bloß ist es nicht "unsauber" in Kauf zu nehmen, dass die Summe der Arraywerte * 33 (mit Sicherheit) größer als unsigned_int_max ist?

edit: Ich habe gerade nachgelesen, wie C++ overflow von Zahlen handelt. Wäre es da nicht sinnvoll in meinem Algorithmus die " % 1300000000" wegzulassen und auch auf dieses Overflow Verhalten aufzubauen?

volkard

srand() schrieb:

Das ist eine gute Idee. Bloß ist es nicht "unsauber" in Kauf zu nehmen, dass die Summe der Arraywerte * 33 (mit Sicherheit) größer als unsigned_int_max ist?

das ist sehr sauber. denn es ist bekannt, was dann passiert.
es wird immer zwischendurch abgeschnitten und es werden nur die hinteren 32 bits genommen.
das ist das gleiche, als würde mit megalangzahlen mit tausenden von stellen gerechnet werden und es würden erst ganz zum schluß alle vorderen bits abgeschnitten und die hinteren 32 bits genommen werden.

an sich geht statt der 33 jede ungerade zahl. dabei ist die 33 eine erprobte zahl beim hashen von strings. hier dürfte sie auch nicht schlecht sein. außerdem kann der prozessor sehr schnell mit 33 multiplizieren.

auf der seite zuvor die 2654435761 hat den gleichen trick gemacht. sie ist 2^32*goldenerSchnitt und hat neben der verwürfelung den vorteil, daß n*2654435761 mit aufeinanderfolgenden werten für n extrem weit auseinaderliegen.