Darf rand() auch richtig zufällig?

03/06/2010 - 18:43 von Markus Wichmann | Report spam
Hi all,

ich hab hier keinen C-Standard vorliegen, wohl aber den aktuellen Draft
vom 11. August 2008. Jedenfalls steht da drin:

7.20.2.1p4: The rand function returns a pseudo-random integer.

7.20.2.2p2: [...] If srand is then called with the same seed value, the
sequence of pseudo-random numbers shall be repeated. [...]

Da ich unzufrieden mit dem Zufallszahlgenerator der glibc bin
(Hyperebenen-Verhalten: Ich habe einen Audio-Player im Shuffle-Modus
laufen; wird der n-te Eintrag der Playlist abgespielt, ist fast sicher,
dass zwei bis drei Stücke spàter der n+1-te Eintrag abgespielt wird),
trage ich mich mit dem Gedanken, den Generator zu ersetzen.

Idee 1: Benutze /dev/urandom. Das gibt aber u.U. echte Zufallszahlen
zurück, und ich weiß nicht, ob man immer die gleiche Reihe bekommt, wenn
man die Datei gleich seedet. Außerdem dürfte die Geschichte mit dem
Öffnen der Datei witzig werden. Und die Geschichte mit den Race
Conditions: Seeding erfolgt durch Schreiben in die Datei. Wenn jetzt
mehrere Prozesse kurz hintereinander srand() benutzen, wird nur der Seed
vom letzten Aufruf verwendet (der Letzte siegt!)... öhm... wàre diese
Implementierung trotzdem standardkonform? Wenn es nicht klar geworden
ist, ich meine sowas hier:

#include <unistd.h>
#include <fctnl.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <limits.h>

#define RAND_MAX INT_MAX

void srand(unsigned int seed)
{
int fd;
fd = open("/dev/urandom", O_WRONLY);
if (fd == -1) return; /* Fehlschlag ist nicht vorgesehen, oder? */
write(fd, &seed, sizeof seed);
close(fd);
}

int rand()
{
int fd, rv;
fd = open("/dev/urandom", O_RDONLY);
if (fd == -1) return (int)strdup("Houston, we have a problem");
read(fd, &rv, sizeof rv);
close(fd);
}

Idee 2: Nimm keinen linearen Generator. Hat jemand Ideen? Ich dachte an
sowas wie

x_{n+1} = x_n^10 (mod INT_MAX)

Anmerkungen zu Performance, Standardkonformitàt oder Zufàlligkeit?
 

Lesen sie die antworten

#1 Marcel Müller
03/06/2010 - 19:29 | Warnen spam
Markus Wichmann wrote:
7.20.2.1p4: The rand function returns a pseudo-random integer.

7.20.2.2p2: [...] If srand is then called with the same seed value, the
sequence of pseudo-random numbers shall be repeated. [...]



Soweit nichts Neues.


Idee 1: Benutze /dev/urandom. Das gibt aber u.U. echte Zufallszahlen
zurück,



Falls es existiert, tut es das, was die Plattform hergibt. Die Qualitàt
der Implementierung kann durchaus unterschiedlich ausfallen. Manche
Systeme erzeugen echte Zufallszahlen aus Quantenmechanischen Prozessen,
wie z.B. Diodenrauschen. Natürlich nur in begrenzter Anzahl. Dazwischen
heißt es wieder PRNG.

und ich weiß nicht, ob man immer die gleiche Reihe bekommt, wenn
man die Datei gleich seedet.



AFAIK nein.

Außerdem dürfte die Geschichte mit dem
Öffnen der Datei witzig werden. Und die Geschichte mit den Race
Conditions: Seeding erfolgt durch Schreiben in die Datei. Wenn jetzt
mehrere Prozesse kurz hintereinander srand() benutzen, wird nur der Seed
vom letzten Aufruf verwendet (der Letzte siegt!)...



/dev/urandom seeded man nicht, wenn man nicht muss. Das macht das OS bei
Start selber, nicht wie bei der CLIB.

öhm... wàre diese
Implementierung trotzdem standardkonform?



Nein.

Aber warum zur Hölle willst du die LIBC modifizieren. Rufe doch einfach
eine andere Zufallszahlenfunktion aus deiner Anwendung auf. Die kann
dann tun, was sie will.


void srand(unsigned int seed)
{
int fd;
fd = open("/dev/urandom", O_WRONLY);
if (fd == -1) return; /* Fehlschlag ist nicht vorgesehen, oder? */
write(fd, &seed, sizeof seed);
close(fd);
}

int rand()
{
int fd, rv;
fd = open("/dev/urandom", O_RDONLY);
if (fd == -1) return (int)strdup("Houston, we have a problem");
read(fd, &rv, sizeof rv);
close(fd);
}



Achso, LIBC-Funktion per Linker-Prioritàt überladen. Naja, wenn es sonst
nirgends in der Anwendung genutzt wird.

Aber wenn dann schon (s.o.)
void srand(unsigned int seed)
{ }
oder noch besser ganz weglassen.

Und das ist totaler Unsinn:
if (fd == -1) return (int)strdup("Houston, we have a problem");


Da sind die letzten paar Bits immer 0 und der Rest auch mehr oder minder
konstant. Wenn dann schon ein Fallback auf LIBC. Spàtestens jetzt gibt
es Ärger mit dem Namen-Überladen. (OK, mit #define bekommt man das auch
gedengelt.)

Idee 2: Nimm keinen linearen Generator. Hat jemand Ideen? Ich dachte an
sowas wie

x_{n+1} = x_n^10 (mod INT_MAX)

Anmerkungen zu Performance, Standardkonformitàt oder Zufàlligkeit?



Solche selber gestricken Lösungen sind in aller Regel Mist, wenn man
nicht vom Fach ist. Die obige ist es jedenfalls, wenn die Potenz nicht
mit voller Genauigkeit durchgerechnet wird. Und selbst dann.
Außerdem ist INT_MAX nicht notwendigerweise eine Mersenne Primzahl.
(2^31-1 ist es allerdings).

Ehrlich gesagt kann ich fast nicht glauben, dass die LIBC rand Funktion
soo schlecht sein soll. Ich habe sie auch schon zu genau diesem Zweck
verwendet. Allerdings andere Plattform; die ist aber auch von gnu libc6
abgeschrieben.


Marcel

Ähnliche fragen