c++ - numero - Perché rand()% 6 è di parte?




numero rand c++ (4)

Ci sono profondità nascoste qui:

  1. L'uso del piccolo u in RAND_MAX + 1u . RAND_MAX è definito come un tipo int ed è spesso l' int più grande possibile. Il comportamento di RAND_MAX + 1 sarebbe indefinito in casi in cui si RAND_MAX + 1 un tipo signed . La scrittura di RAND_MAX impone la conversione del tipo di RAND_MAX in unsigned , RAND_MAX così l'overflow.

  2. L'uso di % 6 può (ma su ogni implementazione di std::rand che ho visto no ) introdurre ulteriori distorsioni statistiche sopra e oltre l'alternativa presentata. Tali casi in cui % 6 è pericoloso sono casi in cui il generatore di numeri ha pianure di correlazione nei bit di ordine basso, come un'implementazione IBM piuttosto famosa (in C) di rand negli anni '70, penso, che ha capovolto i bit alti e bassi come "un'ultima fioritura". Un'ulteriore considerazione è che 6 è molto piccolo cfr. RAND_MAX , quindi ci sarà un effetto minimo se RAND_MAX non è un multiplo di 6, che probabilmente non lo è.

In conclusione, in questi giorni, a causa della sua tracciabilità, utilizzerei % 6 . È improbabile che introducano anomalie statistiche oltre a quelle introdotte dal generatore stesso. Se hai ancora dei dubbi, testa il tuo generatore per vedere se ha le proprietà statistiche appropriate per il tuo caso d'uso.

Durante la lettura di come utilizzare std :: rand, ho trovato questo codice su cppreference.com

int x = 7;
while(x > 6) 
    x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

Cosa c'è di sbagliato nell'espressione a destra? L'ho provato e funziona perfettamente.


Esistono due problemi con rand() % 6 (l'1 1+ non influisce su nessuno dei due problemi).

Innanzitutto, come hanno sottolineato diverse risposte, se i bit bassi di rand() non sono adeguatamente uniformi, anche il risultato dell'operatore residuo non è uniforme.

In secondo luogo, se il numero di valori distinti prodotti da rand() non è un multiplo di 6, il resto produrrà valori più bassi che valori alti. Questo è vero anche se rand() restituisce valori perfettamente distribuiti.

Come esempio estremo, fingi che rand() produca valori distribuiti uniformemente nell'intervallo [0..6] . Se si osservano i resti per quei valori, quando rand() restituisce un valore nell'intervallo [0..5] , il resto produce risultati distribuiti uniformemente nell'intervallo [0..5] . Quando rand() restituisce 6, rand() % 6 restituisce 0, proprio come se rand() avesse restituito 0. Quindi si ottiene una distribuzione con il doppio di 0 rispetto a qualsiasi altro valore.

Il secondo è il vero problema con rand() % 6 .

Il modo per evitare questo problema è scartare i valori che potrebbero produrre duplicati non uniformi. Calcolate il multiplo più grande di 6 che è minore o uguale a RAND_MAX e ogni volta che rand() restituisce un valore maggiore o uguale a quel multiplo lo rifiutate e chiamate nuovamente `rand (), quante volte è necessario.

Così:

int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
    value = rand();

Questa è una diversa implementazione del codice in questione, intesa a mostrare più chiaramente cosa sta succedendo.


Si può pensare a un generatore di numeri casuali come a lavorare su un flusso di cifre binarie. Il generatore trasforma il flusso in numeri tagliandolo in pezzi. Se la funzione std:rand funziona con un RAND_MAX di 32767, utilizza 15 bit in ogni slice.

Quando si prendono i moduli di un numero compreso tra 0 e 32767 inclusi, si trovano 5462 "0" e "1", ma solo 5461 "2", "3", "4" e "5". Quindi il risultato è distorto. Maggiore è il valore RAND_MAX, minore sarà il pregiudizio, ma è inevitabile.

Ciò che non è di parte è un numero nell'intervallo [0 .. (2 ^ n) -1]. È possibile generare un numero (teoricamente) migliore nell'intervallo 0..5 estraendo 3 bit, convertendoli in un numero intero nell'intervallo 0..7 e rifiutando 6 e 7.

Si spera che ogni bit nel flusso di bit abbia le stesse probabilità di essere uno '0' o un '1' indipendentemente da dove si trova nel flusso o dai valori di altri bit. Ciò è eccezionalmente difficile in pratica. Le molte diverse implementazioni dei PRNG software offrono diversi compromessi tra velocità e qualità. Un generatore congruenziale lineare come std::rand offre la massima velocità per la più bassa qualità. Un generatore crittografico offre la massima qualità per la velocità più bassa.


Questo codice di esempio mostra che std::rand è un caso di legder cargo cult legder che dovrebbe far alzare le sopracciglia ogni volta che lo vedi.

Ci sono diversi problemi qui:

Il contratto che la gente di solito assume - anche le povere anime sfortunate che non conoscono meglio e non ci penseranno esattamente in questi termini - è che i campioni di rand della distribuzione uniforme sugli interi in 0, 1, 2, ... RAND_MAX e ogni chiamata produce un campione indipendente .

Il primo problema è che il contratto assunto, campioni casuali uniformi indipendenti in ciascuna chiamata, non è in realtà ciò che dice la documentazione - e in pratica, le implementazioni storicamente non sono riuscite a fornire nemmeno il più simulacro di indipendenza. Ad esempio, C99 §7.20.2.1 'La funzione rand ' dice, senza elaborazione:

La funzione rand calcola una sequenza di numeri pseudo casuali nell'intervallo da 0 a RAND_MAX .

Questa è una frase insignificante, perché la pseudorandomness è una proprietà di una funzione (o famiglia di funzioni ), non di un numero intero, ma ciò non impedisce nemmeno ai burocrati ISO di abusare della lingua. Dopotutto, gli unici lettori che ne sarebbero sconvolti sanno meglio che leggere la documentazione per rand per paura che le loro cellule cerebrali si deteriorino.

Una tipica implementazione storica in C funziona così:

static unsigned int seed = 1;

static void
srand(unsigned int s)
{
    seed = s;
}

static unsigned int
rand(void)
{
    seed = (seed*1103515245 + 12345) % ((unsigned long)RAND_MAX + 1);
    return (int)seed;
}

Ciò ha la sfortunata proprietà che anche se un singolo campione può essere distribuito uniformemente sotto un seme casuale uniforme (che dipende dal valore specifico di RAND_MAX ), si alterna tra numeri pari e dispari in chiamate consecutive - dopo

int a = rand();
int b = rand();

l'espressione (a & 1) ^ (b & 1) produce 1 con probabilità del 100%, il che non è il caso di campioni casuali indipendenti su qualsiasi distribuzione supportata su numeri pari e dispari. Così, è emerso un culto del carico che si dovrebbe scartare i pezzi di basso ordine per inseguire la bestia sfuggente di "migliore casualità". (Avviso spoiler: questo non è un termine tecnico. Questo è un segno che la cui prosa stai leggendo o non sa di cosa stanno parlando, o pensa che tu sia privo di conoscenza e debba essere condannato.)

Il secondo problema è che anche se ogni chiamata RAND_MAX il campionamento indipendentemente da una distribuzione casuale uniforme su 0, 1, 2, ..., RAND_MAX , il risultato di rand() % 6 non verrebbe distribuito uniformemente in 0, 1, 2, 3, 4, 5 come un tiro di dado, a meno che RAND_MAX sia congruente a -1 modulo 6. RAND_MAX semplice: Se RAND_MAX = 6, quindi da rand() , tutti i risultati hanno uguale probabilità 1/7, ma da rand() % 6 , il il risultato 0 ha probabilità 2/7 mentre tutti gli altri risultati hanno probabilità 1/7.

Il modo giusto per farlo è con il campionamento del rifiuto: prelevare ripetutamente un campione casuale uniforme indipendente da 0, 1, 2, ..., RAND_MAX e rifiutare (ad esempio) i risultati 0, 1, 2, ..., ((RAND_MAX + 1) % 6) - 1 se ne ottieni uno, ricomincia da capo; altrimenti, restituisci s % 6 .

unsigned int s;
while ((s = rand()) < ((unsigned long)RAND_MAX + 1) % 6)
    continue;
return s % 6;

In questo modo, l'insieme degli esiti da rand() che accettiamo è equamente divisibile per 6, e ogni possibile esito da s % 6 è ottenuto per lo stesso numero di esiti accettati da rand() , quindi se rand() è distribuito uniformemente allora anche s . Non vi è alcun limite al numero di prove, ma il numero previsto è inferiore a 2 e la probabilità di successo aumenta esponenzialmente con il numero di prove.

La scelta di quali risultati di rand() si rifiuta è irrilevante, a condizione che si mappi un numero uguale di essi su ciascun numero intero inferiore a 6. Il codice su cppreference.com fa una scelta diversa , a causa del primo problema sopra - che nulla è garantito sulla distribuzione o indipendenza degli output di rand() , e in pratica i bit di ordine inferiore esibivano schemi che non 'sembrano abbastanza casuali' (non importa che il prossimo output sia una funzione deterministica di quello precedente).

Esercizio per il lettore: dimostra che il codice su cppreference.com produce una distribuzione uniforme sui tiri di dado se rand() produce una distribuzione uniforme su 0, 1, 2, ..., RAND_MAX .

Esercizio per il lettore: perché potresti preferire rifiutare l'uno o l'altro sottoinsieme? Quale calcolo è necessario per ogni prova nei due casi?

Un terzo problema è che lo spazio seme è così piccolo che anche se il seme è distribuito uniformemente, un avversario armato di conoscenza del tuo programma e di un risultato ma non il seme può facilmente prevedere il seme e i risultati successivi, il che li fa sembrare non così dopo tutto casuale. Quindi non pensare nemmeno di usarlo per la crittografia.

Puoi seguire la stravagante strada std::uniform_int_distribution classe std::uniform_int_distribution C ++ 11 con un dispositivo casuale appropriato e il tuo motore casuale preferito come il sempre popolare twister Mersenne std::mt19937 per giocare a dadi con tuo cugino di quattro anni , ma anche questo non sarà idoneo a generare materiale chiave crittografico, e il tornado di Mersenne è anche un terribile maiale spaziale con uno stato multi-kilobyte che sta causando il caos nella cache della CPU con un tempo di impostazione osceno, quindi è male anche per , ad esempio , simulazioni parallele di Monte Carlo con alberi riproducibili di sottocomputer; la sua popolarità probabilmente deriva principalmente dal suo nome accattivante. Ma puoi usarlo per lanciare dadi giocattolo come in questo esempio!

Un altro approccio consiste nell'utilizzare un semplice generatore di numeri pseudocasuali crittografici con un piccolo stato, come un semplice PRNG di cancellazione rapida dei tasti , o solo un codice di flusso come AES-CTR o ChaCha20 se si è sicuri ( ad esempio , in una simulazione Monte Carlo per ricerca nelle scienze naturali) che non ci sono conseguenze avverse nella previsione dei risultati passati se lo stato viene mai compromesso.





std