Hallo, Ich habe ein Problem mit Zufallszahlen bzw. ein Problem mit dem Ausgangswert für Pseudozufallszahlen mit srand(). Das Programm sollte plattformunabhängig sein und ich würde mich gerne auf die zum ANSI-Standard gehörenden Funktionen beschränken, aber für statistische Zwecke rufe ich es z.B. 10000 mal hintereinander auf. Als einzigen plattformunabhängigen Wert, der da in Frage kommt, kenne ich da time(0). Die 10000 Programmaufrufe erstrecken sich aber nun leider über ein bisschen mehr als 60 Sekunden. Da hätte ich das Programm auch nur 60 mal aufrufen können. Wie könnte ich den Wert für srand() variieren? clock() liefert bei mir immer nur zwei verschiedene Werte. Aus /dev/*random lesen geht nicht. Andere Ideen habe ich nicht. :-| Ferdinand
* Ferdinand Ihringer
Ich habe ein Problem mit Zufallszahlen bzw. ein Problem mit dem Ausgangswert für Pseudozufallszahlen mit srand(). Das Programm sollte plattformunabhängig sein und ich würde mich gerne auf die zum ANSI-Standard gehörenden Funktionen beschränken, aber für statistische Zwecke rufe ich es z.B. 10000 mal hintereinander auf. Als einzigen plattformunabhängigen Wert, der da in Frage kommt, kenne ich da time(0). Die 10000 Programmaufrufe erstrecken sich aber nun leider über ein bisschen mehr als 60 Sekunden. Da hätte ich das Programm auch nur 60 mal aufrufen können.
PID auslesen (getpid() unter POSIX) geht auch nicht? Ansonsten kann man auch uninitialisierte Variablen vom Stack auslesen, geht natürlich aus jeder Plattform. ftime() wäre auch POSIX, aber eben nicht ANSI C. Gruß, Bernhard -- "Was wir wissen, ist ein Tropfen; was wir nicht wissen, ein Ozean." -- Isaac Newton
On Tuesday 12 October 2004 22:21, Bernhard Walle wrote:
* Ferdinand Ihringer
[2004-10-12 22:08]: Ich habe ein Problem mit Zufallszahlen bzw. ein Problem mit dem Ausgangswert für Pseudozufallszahlen mit srand(). Das Programm sollte plattformunabhängig sein und ich würde mich gerne auf die zum ANSI-Standard gehörenden Funktionen beschränken, aber für statistische Zwecke rufe ich es z.B. 10000 mal hintereinander auf. Als einzigen plattformunabhängigen Wert, der da in Frage kommt, kenne ich da time(0). Die 10000 Programmaufrufe erstrecken sich aber nun leider über ein bisschen mehr als 60 Sekunden. Da hätte ich das Programm auch nur 60 mal aufrufen können.
PID auslesen (getpid() unter POSIX) geht auch nicht? Ansonsten kann man auch uninitialisierte Variablen vom Stack auslesen, geht natürlich aus jeder Plattform. ftime() wäre auch POSIX, aber eben nicht ANSI C.
Nein, POSIX geht eigentlich nicht, außer es gibt getpid() auch für Windows, das nun nicht POSIX-konform ist. Etwas PID-artiges müsste es da ja auch geben. Es würde dort auch mit dem gcc kompiliert werden. Vielleicht helfen ja dessen Erweiterungen, die ich nur sporadisch kenne, da. Auf irgendwelche Abfragen des Betriebssystems will ich eigentlich verzichten. Zu den uninitialisierten Variablen: Also wenn ich uninitialisierte Variablen bei mir abfrage, kommt zumindest kurz hintereinander per Hand immer der selbe Wert, genauso wie der Speicherplatz der selbe ist. Oder habe ich da etwas missverstanden? Ferdinand
Hi Ferdinand! Ferdinand Ihringer schrieb am 12.10.2004 23:35 :
On Tuesday 12 October 2004 22:21, Bernhard Walle wrote:
* Ferdinand Ihringer [2004-10-12 22:08]:
Ich habe ein Problem mit Zufallszahlen bzw. ein Problem mit dem Ausgangswert für Pseudozufallszahlen mit srand(). Das Programm sollte plattformunabhängig sein und ich würde mich gerne auf die zum ANSI-Standard gehörenden Funktionen beschränken, aber für statistische Zwecke rufe ich es z.B. 10000 mal hintereinander auf.
PID auslesen (getpid() unter POSIX) geht auch nicht? Ansonsten kann man auch uninitialisierte Variablen vom Stack auslesen, geht natürlich aus jeder Plattform. ftime() wäre auch POSIX, aber eben nicht ANSI C.
Zu den uninitialisierten Variablen: Also wenn ich uninitialisierte Variablen bei mir abfrage, kommt zumindest kurz hintereinander per Hand immer der selbe Wert, genauso wie der Speicherplatz der selbe ist. Oder habe ich da etwas missverstanden?
Das ist schon klar, da dieser Speicherplatz ja nicht unebedingt in der Zwischenzeit überschrieben wird. Um eine (Pseudo-)Zufallsreihe zu generieren, brauchst du aber nur einen Seed, den du bei der Initialisierung von srand angibst. Alle anderen Zufallszahlen werden auf dieser Basis generiert. Wenn du dennoch mehrere Seeds brauchen solltest (um z.B. mehrere unabhängige Zufallsreihen zu generieren), kannst du auch ein uninitialisertes Array verwenden. Gruß, Michael
* Ferdinand Ihringer
Zu den uninitialisierten Variablen: Also wenn ich uninitialisierte Variablen bei mir abfrage, kommt zumindest kurz hintereinander per Hand immer der selbe Wert, genauso wie der Speicherplatz der selbe ist. Oder habe ich da etwas missverstanden?
Klar, aber du brauchst ja nur einen Wert (nämlich für srand()). Wenn die Sekunde gleich ist, nimmst du halt noch eine uninitialisierte Varialbe dazu und mulitplizierst das ganze. Gruß, Bernhard -- Der Rechner von heute stuerzt ja schon ab, bevor man ihn ueberhaupt eingeschaltet hat. Das ist dann energiesparend und deshalb kein Bug sondern ein Feature.
On Wednesday 13 October 2004 17:20, Bernhard Walle wrote:
* Ferdinand Ihringer
[2004-10-12 23:35]: Zu den uninitialisierten Variablen: Also wenn ich uninitialisierte Variablen bei mir abfrage, kommt zumindest kurz hintereinander per Hand immer der selbe Wert, genauso wie der Speicherplatz der selbe ist. Oder habe ich da etwas missverstanden?
Klar, aber du brauchst ja nur einen Wert (nämlich für srand()). Wenn die Sekunde gleich ist, nimmst du halt noch eine uninitialisierte Varialbe dazu und mulitplizierst das ganze.
Wenn ich das Programm 1000mal starte, brauche ich 1000 Werte. Aber die uninitialisierte Variable bekommt bei mir ziemlich oft den selben Wert zugewiesen bzw. den selben Speicherplatz. Ich könnte aus den 1000 Aufrufen einen Aufruf mit einer internen Schleife für die Wiederholungen machen und dann die seed-Werte 1000mal aufeinander abstimmen oder nur ein srand aufrufen. Dann hätte ich aber dieses Problem sowieso nicht. Es wäre mir aber lieber, wenn es einen Wert gäbe, der einfach so wahrscheinlich verschieden ist, wie die PID oder die Zeit in Millisekunden. Oder ich nehme eine der beiden anderen Varianten... Oder ich verzichte auf die statistische Erhebung unter Windows... Ferdinand
* Ferdinand Ihringer
On Wednesday 13 October 2004 17:20, Bernhard Walle wrote:
* Ferdinand Ihringer
[2004-10-12 23:35]: Zu den uninitialisierten Variablen: Also wenn ich uninitialisierte Variablen bei mir abfrage, kommt zumindest kurz hintereinander per Hand immer der selbe Wert, genauso wie der Speicherplatz der selbe ist. Oder habe ich da etwas missverstanden?
Klar, aber du brauchst ja nur einen Wert (nämlich für srand()). Wenn die Sekunde gleich ist, nimmst du halt noch eine uninitialisierte Varialbe dazu und mulitplizierst das ganze.
Wenn ich das Programm 1000mal starte, brauche ich 1000 Werte. Aber die uninitialisierte Variable bekommt bei mir ziemlich oft den selben Wert zugewiesen bzw. den selben Speicherplatz. Ich könnte aus den 1000 Aufrufen einen Aufruf mit einer internen Schleife für die Wiederholungen machen und dann die seed-Werte 1000mal aufeinander abstimmen oder nur ein srand aufrufen. Dann hätte ich aber dieses Problem sowieso nicht.
Den gleichen Speicherplatz wenn die Programme gleichzeitig laufen? Kannst du mir erklären wie das gehen soll? (Bitte nicht den &variable als "Speicherplatz" rechnen, dein Programm sieht einen anderen Adressraum.) Dass die Werte gleich sind, kann natürlich schon passieren. Ich weiß jetzt nicht, wie die Betriebssysteme das intern handhaben.
Es wäre mir aber lieber, wenn es einen Wert gäbe, der einfach so wahrscheinlich verschieden ist, wie die PID oder die Zeit in Millisekunden. Oder ich nehme eine der beiden anderen Varianten... Oder ich verzichte auf die statistische Erhebung unter Windows...
Auch unter Windows gibt es eine Funktion, die PID herauszufinden. Auch gibt es natürlich unter beiden Plattformen Funktionen, die Zeit genauer als in Sekunden herauszufinden. Ein paar #define's rein und gut ist. Oder eine Bibliothek verwenden, die das kapselt. Oder Cygwin verwenden. Oder ... Gruß, Bernhard -- Das Wichtigste im Leben ist die Wahl des Berufes. Der Zufall entscheidet darüber. -- Blaise Pascal (1623 - 1662)
On Wednesday 13 October 2004 21:13, Bernhard Walle wrote:
* Ferdinand Ihringer
[2004-10-13 20:26]: Wenn ich das Programm 1000mal starte, brauche ich 1000 Werte. Aber die uninitialisierte Variable bekommt bei mir ziemlich oft den selben Wert zugewiesen bzw. den selben Speicherplatz. Ich könnte aus den 1000 Aufrufen einen Aufruf mit einer internen Schleife für die Wiederholungen machen und dann die seed-Werte 1000mal aufeinander abstimmen oder nur ein srand aufrufen. Dann hätte ich aber dieses Problem sowieso nicht.
Den gleichen Speicherplatz wenn die Programme gleichzeitig laufen?
Das tun sie ja nicht. Ich schrieb in der ersten Mail auch "für statistische Zwecke rufe ich es z.B. 10000 mal hintereinander auf.". Nagut, ganz eindeutig ist das nicht, aber fast.
Es wäre mir aber lieber, wenn es einen Wert gäbe, der einfach so wahrscheinlich verschieden ist, wie die PID oder die Zeit in Millisekunden. Oder ich nehme eine der beiden anderen Varianten... Oder ich verzichte auf die statistische Erhebung unter Windows...
Auch unter Windows gibt es eine Funktion, die PID herauszufinden. Auch gibt es natürlich unter beiden Plattformen Funktionen, die Zeit genauer als in Sekunden herauszufinden. Ein paar #define's rein und gut ist. Oder eine Bibliothek verwenden, die das kapselt. Oder Cygwin verwenden. Oder ...
Ursprünglich wollte ich auch nur wissen, ob es irgendwie mit der Standardbibliothek geht. Und das geht anscheinend nicht. Damit hat sich die Frage geklärt und ich nehme einpaar defines. :-) Ferdinand
Hallo, Am Tue, 12 Oct 2004, Bernhard Walle schrieb:
* Ferdinand Ihringer
[2004-10-12 22:08]: Ich habe ein Problem mit Zufallszahlen bzw. ein Problem mit dem Ausgangswert für Pseudozufallszahlen mit srand(). Das Programm sollte plattformunabhängig sein und ich würde mich gerne auf die zum ANSI-Standard gehörenden Funktionen beschränken, aber für statistische Zwecke rufe ich es z.B. 10000 mal hintereinander auf. Als einzigen plattformunabhängigen Wert, der da in Frage kommt, kenne ich da time(0).
BTW: "eigentlich" sollte das wohl 'time(NULL)' sein. Oder noch korrekter: time( (time_t *)0 ); *SCNR*
Die 10000 Programmaufrufe erstrecken sich aber nun leider über ein bisschen mehr als 60 Sekunden. Da hätte ich das Programm auch nur 60 mal aufrufen können.
PID auslesen (getpid() unter POSIX) geht auch nicht? Ansonsten kann man auch uninitialisierte Variablen vom Stack auslesen, geht natürlich aus jeder Plattform. ftime() wäre auch POSIX, aber eben nicht ANSI C.
Und vielleicht 'gettimeofday' oder statt 'time'. Das mit der PID ist sicherlich auch noch ne Idee. Evtl. koennte mann das Ergebnis auch noch durch einen Hash-Algorithmus schicken, z.B. MD5 oder SHA1 und dies dann wieder auf 'sizeof(unsigned int)' "kuerzen" (und zwar nicht mit nem einfachen 'mod'). -dnh -- As it turned out, this cute girl I had been talking to spoke Russian. One instant gift at hand. As it turned out we had a lot in common. We both liked girls for one thing. Ah well. -- stevo
Hallo, On Wednesday 13 October 2004 00:08, David Haller wrote:
Am Tue, 12 Oct 2004, Bernhard Walle schrieb:
* Ferdinand Ihringer
[2004-10-12 22:08]: Ich habe ein Problem mit Zufallszahlen bzw. ein Problem mit dem Ausgangswert für Pseudozufallszahlen mit srand(). Das Programm sollte plattformunabhängig sein und ich würde mich gerne auf die zum ANSI-Standard gehörenden Funktionen beschränken, aber für statistische Zwecke rufe ich es z.B. 10000 mal hintereinander auf. Als einzigen plattformunabhängigen Wert, der da in Frage kommt, kenne ich da time(0).
BTW: "eigentlich" sollte das wohl 'time(NULL)' sein.
Im Quelltext steht auch NULL statt 0 drin. Ich wollte hier nur nicht zu ausschweifend werden.
Die 10000 Programmaufrufe erstrecken sich aber nun leider über ein bisschen mehr als 60 Sekunden. Da hätte ich das Programm auch nur 60 mal aufrufen können.
PID auslesen (getpid() unter POSIX) geht auch nicht? Ansonsten kann man auch uninitialisierte Variablen vom Stack auslesen, geht natürlich aus jeder Plattform. ftime() wäre auch POSIX, aber eben nicht ANSI C.
Und vielleicht 'gettimeofday' oder statt 'time'. Das mit der PID ist sicherlich auch noch ne Idee.
Alles schön, aber alles 'nur' POSIX...
Evtl. koennte mann das Ergebnis auch noch durch einen Hash-Algorithmus schicken, z.B. MD5 oder SHA1 und dies dann wieder auf 'sizeof(unsigned int)' "kuerzen" (und zwar nicht mit nem einfachen 'mod').
Eine Frage aus reinem Interesse: Wie würde man das machen? Einfach von den 16-MD5 die sizeof(unsigned int) ersten Bytes nehmen? Ferdinand
Ferdinand Ihringer schrieb:
[...] Eine Frage aus reinem Interesse: Wie würde man das machen? Einfach von den 16-MD5 die sizeof(unsigned int) ersten Bytes nehmen?
Zum Beispiel. Oder die sizeof(unsigned int)-Portionen per bitweisem XOR falten. Hashes bringen aber nur dann etwas, wenn die Anzahl der gehashten Bits nicht kleiner als die Anzahl der Bits im Hashwert sind. Von nix kommt nix ;-) Gruß, Alex
Hallo, Am Wed, 13 Oct 2004, Ferdinand Ihringer schrieb:
On Wednesday 13 October 2004 00:08, David Haller wrote: [..]
Und vielleicht 'gettimeofday' oder statt 'time'. Das mit der PID ist sicherlich auch noch ne Idee. [..] Evtl. koennte mann das Ergebnis auch noch durch einen Hash-Algorithmus schicken, z.B. MD5 oder SHA1 und dies dann wieder auf 'sizeof(unsigned int)' "kuerzen" (und zwar nicht mit nem einfachen 'mod').
Eine Frage aus reinem Interesse: Wie würde man das machen? Einfach von den 16-MD5 die sizeof(unsigned int) ersten Bytes nehmen?
Das wäre eine Möglichkeit. Oder die 128 bit in Blöcke zu je sizeof(int) teilen und die Blöcke verXORen oder so. Das hilft allerdings immer noch nicht dagegen, daß du innerhalb einer Sekunde immer den gleichen seed bekommst. Schau mal in /usr/src/linux/drivers/char/random.c (v.a. auch die Kommentare) und schau mal, ob du da nicht noch ein "besseres" Zufallselement in den seed reinbekommst. Ich würde jedenfalls im ./configure auf /dev/urandom testen und wenn das vorhanden ist das zum initialisieren verwenden. Ob und wie du unter Win* an Zufallsdaten oder zumindest an eine genauere "Zeit" als 'time()' rankommst weiß ich nicht. Vorhanden ist sowas aber wohl. Da musst du dann halt wohl oder übel mit ein paar #defines / #ifdefs rumwerfen. -dnh -- "It's fifteen hundred miles to Ankh-Morpork, we've got three hundred and sixty-three elephants, fifty carts of forage, the monsoon's about to break and we're wearing... we're wearing... sort of things, like glass, only dark... dark glass things on our eyes... ... Let's go!" -- T. Pratchett, "Moving Pictures"
On Thursday 14 October 2004 02:51, David Haller wrote: [..]
Schau mal in /usr/src/linux/drivers/char/random.c (v.a. auch die Kommentare) und schau mal, ob du da nicht noch ein "besseres" Zufallselement in den seed reinbekommst.
Ich sah eben mal drüber und fand erstmal nichts. [..]
Ob und wie du unter Win* an Zufallsdaten oder zumindest an eine genauere "Zeit" als 'time()' rankommst weiß ich nicht. Vorhanden ist sowas aber wohl.
Ja, es müsste sogar GetTimeOfDay (wenn auch mit double als Rückgabewert) geben. Das gibt es zumindest bei Delphi und das dürfte dort als Teil der Win-API sein...
Da musst du dann halt wohl oder übel mit ein paar #defines / #ifdefs rumwerfen.
Das werde ich wohl tun müssen.
-- "It's fifteen hundred miles to Ankh-Morpork, we've got three hundred and sixty-three elephants, fifty carts of forage, the monsoon's about to break and we're wearing... we're wearing... sort of things, like glass, only dark... dark glass things on our eyes... ... Let's go!" -- T. Pratchett, "Moving Pictures"
Aber da ist es doch für dich schon deutlich schwerer, alle lustigen Sentenzen aus Scheibenweltromanen zu siggen... Ferdinand
Ferdinand Ihringer schrieb:
[..]
Ob und wie du unter Win* an Zufallsdaten oder zumindest an eine genauere "Zeit" als 'time()' rankommst weiß ich nicht. Vorhanden ist sowas aber wohl.
Ja, es müsste sogar GetTimeOfDay (wenn auch mit double als Rückgabewert) geben. Das gibt es zumindest bei Delphi und das dürfte dort als Teil der Win-API sein...
Falls du das Win-API nutzen kannst/möchtest, könntest du u.a. folgende Funktionen verwenden, um an Seeds zu kommen. DWORD GetTickCount() Anzahl Millisekunden seit das System gestartet wurde void GetSystemTime(LPSYSTEMTIME) Datum/Uhrzeit (UTC) des Systems in einer SYSTEMTIME Struktur. BOOL QueryPerformanceCounter(LARGE_INTEGER*) Hochauflösender, systemspezifischer Zähler HRESULT CoCreateGuid(GUID*) 128 global (weltweit) eindeutige Bits. Kein folgender Aufruf wird nochmal dieselbe GUID erzeugen. Ansonsten könnte man auch in Betracht ziehen, den Seed aus einer Benutzereingabe oder dem Laufzeitverhalten des Programmes selbst zu erzeugen. Gruß, Alex
Hallo! On Thu, 2004-10-14 at 02:51, David Haller wrote:
Schau mal in /usr/src/linux/drivers/char/random.c (v.a. auch die Kommentare) und schau mal, ob du da nicht noch ein "besseres" Zufallselement in den seed reinbekommst.
Der Zufallsgenerator im Kernel verwendet IMHO Daten aus den IDE-, Mouse-, und Tastatur-Treibern(Wann kam der IRQ, Zeitl. Abstand zum letzten IRQ, verknüpft mit den Nutzdaten... hängt vom Treiber ab), um einen Entropie-Pool anzulegen. Da wird mal kräftig drüber"gehasht", und dann das ganze in den Pool für /dev/random (und /dev/urandom) geworfen.
Ich würde jedenfalls im ./configure auf /dev/urandom testen und wenn das vorhanden ist das zum initialisieren verwenden.
Würde ich auch tun, aber wenn's um Sicherheit geht, ist /dev/random besser. /dev/urandom verwendet alte Werte wieder, wenn der Entropie-Pool leer ist. (Passiert gerne mal auf diskless workstations oder embedded devices) Gruß Manfred Gahr
Hallo, Am Thu, 14 Oct 2004, Manfred Gahr schrieb:
On Thu, 2004-10-14 at 02:51, David Haller wrote:
Schau mal in /usr/src/linux/drivers/char/random.c (v.a. auch die [..] Ich würde jedenfalls im ./configure auf /dev/urandom testen und wenn das vorhanden ist das zum initialisieren verwenden.
Würde ich auch tun, aber wenn's um Sicherheit geht, ist /dev/random besser. /dev/urandom verwendet alte Werte wieder, wenn der Entropie-Pool leer ist. (Passiert gerne mal auf diskless workstations oder embedded devices)
Nein, das nicht, aber /dev/urandom degeneriert dann zu einem normalen PRNG (aber guten, IIRC MD5 basiert), der aber eben aus /dev/random initialisiert wurde, ist also immer noch besser als ein aus /dev/random initialisiertes 'rand()'. Für Kryptographisches oder um einen PRNG zu initialisieren sollte man also /dev/random verwenden (zumindest unter Linux! [1]), ansonsten sollte man /dev/urandom verwenden. Das steht übrigens auch in random.c. -dnh [1] denn auf anderen Unices mit /dev/random ist das oft nicht sicher genug bzw. auch nur ein PRNG. -- He's wandering the wilds of West Buttfsck, administering a little personal attention to Jenny L. User [family motto: "My ISBN isn't working"]. -- K.T. Wiegman
participants (6)
-
Alexander Veit
-
Bernhard Walle
-
David Haller
-
Ferdinand Ihringer
-
Manfred Gahr
-
Michael Wenger