Qual è il modo migliore per produrre doppi casuali su POSIX?

Question

Vorrei ottenere distribuzione uniforme nell'intervallo [0.0, 1.0)

Se possibile, si prega di consentire all'implementazione di utilizzare byte casuali da /dev/urandom.

Sarebbe anche bello se la tua soluzione fosse sicura per i thread . Se non sei sicuro, ti preghiamo di indicarlo.

Vedi alcune soluzioni a cui ho pensato dopo aver letto altre risposte.

Answer 1

Questo sembra essere abbastanza buono:

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);

Questo si basa sull'implementazione drand48 di NetBSD.

Answer 2

Semplice : un doppio ha 52 bit di precisione assumendo IEEE. Quindi genera un intero casuale senza segno a 52 bit (o più grande) (ad esempio leggendo byte da dev / urandom), convertilo in un doppio e dividilo per 2 ^ (numero di bit che era).

Ciò fornisce una distribuzione numericamente uniforme (in quanto la probabilità che un valore si trovi in ??un dato intervallo è proporzionale all'intervallo) fino alla 52a cifra binaria.

Complicato : tuttavia, ci sono molti doppi valori nell'intervallo [0,1) che non è possibile generare sopra. Per essere precisi, la metà dei valori nell'intervallo [0,0,5) (quelli che hanno il bit meno significativo impostato) non possono verificarsi. Tre quarti dei valori nell'intervallo [0,0.25) (quelli che hanno uno dei loro almeno 2 bit impostati) non possono verificarsi, ecc., Essendo possibile solo un valore positivo inferiore a 2 ^ -51, nonostante un doppio sia in grado di rappresentare miliardi di tali valori. Quindi non si può dire che sia veramente uniforme su tutta la gamma specificata con la massima precisione.

Ovviamente non vogliamo scegliere una di quelle doppie con uguale probabilità, perché il numero risultante sarà in media troppo piccolo. Abbiamo ancora bisogno della probabilità che il risultato in un determinato intervallo sia proporzionale all'intervallo, ma con una maggiore precisione su quali intervalli funzionano.

Penso le seguenti opere. Non ho studiato o testato in modo particolare questo algoritmo (come probabilmente puoi dire dal modo in cui non esiste un codice), e personalmente non lo userei senza trovare riferimenti adeguati che indichino che è valido. Ma ecco qui:

• Inizia l'esponente su 52 e scegli un numero intero senza segno casuale a 52 bit (assumendo 52 bit di mantissa).
• Se il bit più significativo dell'intero è 0, aumenta l'esponente di uno, sposta l'intero a sinistra di uno e riempi il bit meno significativo con un nuovo bit casuale.
• Ripeti fino a quando non colpisci un 1 nel punto più significativo, oppure l'esponente diventa troppo grande per il tuo doppio (1023. O forse 1022).
• Se hai trovato un 1, dividi il tuo valore per 2 ^ esponente. Se hai tutti gli zero, restituisci 0 (lo so, non è in realtà un caso speciale, ma sottolinea l'importanza di un ritorno 0 molto improbabile [Modifica: in realtà potrebbe essere un caso speciale - dipende se vuoi o meno generare denorms. In caso contrario, una volta che hai abbastanza 0 in una riga, scarti qualsiasi cosa rimasta e restituisci 0. Ma in pratica è così improbabile da essere trascurabile, a meno che la fonte casuale non sia casuale).

Non so se ci sia davvero un uso pratico per un doppio così casuale, intendiamoci. La tua definizione di casuale dovrebbe dipendere fino a un certo punto. Ma se puoi trarre vantaggio dal fatto che tutti e 52 i suoi bit significativi sono casuali, questo potrebbe effettivamente essere utile.

Answer 3

La lettura da file è AFAIK thread-safe, quindi l'uso di fopen () per leggere da / dev / urandom produrrà "veramente casuale" byte.

Anche se potrebbero esserci potenziali gotcha, ritengo che qualsiasi insieme di tali byte a cui si accede come numero intero, diviso per il numero intero massimo di quella dimensione, produrrà un valore in virgola mobile compreso tra 0 e 1 con approssimativamente quella distribuzione.

Esempio:

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

Il trucco è che hai bisogno di un randomizzatore a 54 bit che soddisfi le tue esigenze. Alcune righe di codice con un unione per attaccare quei 54 bit nella mantissa e hai il tuo numero. Il trucco non è il doppio float, il trucco è il tuo randomizzatore desiderato.

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 è il tuo valore casuale

Answer 6

/ dev / urandom non è POSIX e non è generalmente disponibile.

Il modo standard di generare un doppio uniformemente in [0,1) è generare un numero intero nell'intervallo [0,2 ^ N) e dividerlo per 2 ^ N. Quindi scegli il tuo generatore di numeri casuali preferito e usalo. Per le simulazioni, la mia è la Mersenne Twister , poiché è estremamente veloce, ma non ancora ben correlata . In realtà, può farlo per te e ha anche una versione che darà più precisione per i numeri più piccoli. In genere gli dai un seme per cominciare, che aiuta per la ripetibilità per il debug o mostrando agli altri i tuoi risultati. Ovviamente, puoi fare in modo che il tuo codice prenda un numero casuale da / dev / urandom come seme se non ne viene specificato uno

Per scopi crittografici, invece, dovresti utilizzare una delle librerie crittografiche standard là fuori, come openssl ) che utilizzerà effettivamente / dev / urandom quando disponibile.

Per quanto riguarda la sicurezza dei thread, la maggior parte non lo sarà, almeno con le interfacce standard, quindi dovrai creare un layer in cima o usarli solo in un thread. Quelli che sono sicuri per i thread ti forniscono uno stato che modificano, in modo che invece tu stia effettivamente eseguendo più generatori di numeri casuali non interagenti, che potrebbero non essere quello che stai cercando.