Quel est le meilleur moyen de produire un double aléatoire sur POSIX?

Question

Je souhaite que la distribution uniforme soit dans la plage [0.0, 1.0)

.

Si possible, veuillez laisser l'application implémenter des octets aléatoires provenant de / dev / urandom.

Il serait également intéressant que votre solution soit thread-safe . Si vous n'êtes pas sûr, veuillez l'indiquer.

Voir une solution à laquelle j'ai pensé après avoir lu d'autres réponses.

Answer 1

Cela semble être un très bon moyen:

unsigned short int r1, r2, r3;
// let r1, r2 and r3 hold random values
double result = ldexp(r1, -48) + ldexp(r2, -32) + ldexp(r3, -16);

Ceci est basé sur l'implémentation drand48 de NetBSD.

Answer 2

Simple : un double a une précision de 52 bits en supposant IEEE. Générez donc un entier aléatoire non signé de 52 bits (ou supérieur) (par exemple, en lisant des octets dans dev / urandom), convertissez-le en double et divisez-le par 2 ^ (nombre de bits c'était).

Ceci donne une distribution numériquement uniforme (en ce sens que la probabilité qu'une valeur soit dans une plage donnée est proportionnelle à la plage) jusqu'au 52ème chiffre binaire.

Compliqué : toutefois, il existe de nombreuses valeurs doubles dans la plage [0,1) que ce qui précède ne peut pas générer. Pour être précis, la moitié des valeurs comprises dans la plage [0,0.5) (celles dont le bit de poids le moins significatif est défini) ne peuvent pas se produire. Trois quarts des valeurs comprises dans la plage [0,0.25) (celles qui ont l'un de leurs 2 bits minimum au minimum) ne peuvent pas se produire, etc., de sorte qu'une seule valeur positive inférieure à 2 ^ -51 soit possible, malgré un double étant capable de représenter des milliards de ces valeurs. On ne peut donc pas dire qu'il soit vraiment uniforme sur toute la plage spécifiée avec une précision absolue.

Bien sûr, nous ne voulons pas choisir l’un de ces doubles avec une probabilité égale, car le nombre obtenu sera en moyenne trop petit. Nous avons toujours besoin que la probabilité que le résultat se situe dans une plage donnée soit proportionnelle à la plage, mais avec une précision plus grande pour la plage qui fonctionne.

Je pense les travaux suivants. Je n'ai pas particulièrement étudié ou testé cet algorithme (comme vous pouvez probablement le constater, il n'y a pas de code), et personnellement, je ne l'utiliserais pas sans trouver les références appropriées indiquant qu'il est valide. Mais voici:

• Désactivez l'exposant à 52 et choisissez un entier non signé aléatoire de 52 bits (en supposant 52 bits de mantisse).
• Si le bit le plus significatif du nombre entier est 0, augmentez l'exposant de un, décale le nombre entier restant de un et remplissez le bit le moins significatif avec un nouveau bit aléatoire.
• Répétez l'opération jusqu'à atteindre le 1 dans la position la plus significative ou l'exposant devient trop grand pour votre double (1023. Ou éventuellement 1022).
• Si vous avez trouvé un 1, divisez votre valeur par 2 ^ exposant. Si vous avez tous les zéros, retournez 0 (Je sais, ce n'est pas vraiment un cas particulier, mais il faut souligner à quel point il est peu probable qu'un retour 0 soit [Edit: en fait, cela pourrait être un cas spécial - cela dépend si vous voulez générer ou non Si ce n’est pas le cas, une fois que vous avez suffisamment de 0 dans une rangée, vous perdez tout ce qui reste et vous renvoyez 0. Mais dans la pratique, il est peu probable que ce soit négligeable, sauf si la source aléatoire n’est pas aléatoire).

Je ne sais pas s'il existe réellement une utilisation pratique pour un tel double aléatoire, remarquez. Votre définition du hasard devrait dépendre dans une certaine mesure de son utilité. Mais si vous pouvez tirer parti des 52 bits significatifs qui sont aléatoires, cela pourrait être utile.

Answer 3

La lecture à partir de fichiers est AFAIK thread-safe, donc, utiliser fopen () pour lire à partir de / dev / urandom donnera "vraiment aléatoire". octets.

Bien qu’il puisse y avoir des pièges potentiels, un groupe d’octets auxquels on accède en tant qu’entier, divisé par l’entier maximal de cette taille, donnera une valeur à virgule flottante comprise entre 0 et 1 avec approximativement cette distribution.

Par exemple:

FILE* f = fopen("/dev/urandom", "r");
int32_t int;
fread(&int, sizeof(int32_t), 1, f);
fclose(f);
double theRandomValue = int / (double) (2 ** 32 - 1);

Answer 4

Le truc, c’est que vous avez besoin d’un randomiseur 54 bits qui répond à vos besoins. Quelques lignes de code avec une union pour coller ces 54 bits dans la mantisse et vous avez votre numéro. L'astuce n'est pas le double jeu. L'astuce est votre randomiseur souhaité.

Answer 5

#include <stdlib.h>
printf("%f\n", drand48());

/ dev / random:

double c;
fd = open("/dev/random", O_RDONLY);
unsigned int a, b;
read(fd, &a, sizeof(a));
read(fd, &b, sizeof(b));
if (a > b)
   c = fabs((double)b / (double)a);
else
    c = fabs((double)a / (double)b);

c est votre valeur aléatoire

Answer 6

/ dev / urandom n'est pas POSIX et n'est généralement pas disponible.

La méthode standard pour générer un double uniformément dans [0,1) consiste à générer un entier compris dans la plage [0,2 ^ N) et à le diviser par 2 ^ N. Alors, choisissez votre générateur de nombre aléatoire préféré et utilisez-le. Pour les simulations, le mien est Mersenne Twister , car il est extrêmement rapide, mais pas encore bien corrélé . En fait, il peut le faire pour vous, et a même une version qui donnera plus de précision pour les plus petits nombres. En règle générale, vous lui donnez un germe, ce qui facilite la répétabilité pour le débogage ou pour montrer vos résultats aux autres. Bien sûr, vous pouvez demander à votre code de saisir un nombre aléatoire de / dev / urandom en tant que graine si aucun n’est spécifié.

Pour des raisons de chiffrement, vous devriez plutôt utiliser l’une des bibliothèques de chiffrement standard, telle que openssl . qui utilisera bien / dev / urandom lorsque disponible.

En ce qui concerne la sécurité des threads, la plupart ne le seront pas, du moins avec les interfaces standard. Vous devrez donc créer un calque par-dessus ou ne les utiliser que dans un seul thread. Ceux qui sont thread-safe ont-ils fourni un état qu'ils modifient, de sorte que vous exécutez en réalité plusieurs générateurs de nombres aléatoires sans interaction, ce qui peut ne pas être ce que vous cherchez.