generando un numero casuale compreso tra 0 e n dove n può essere> RAND_MAX

Question

Come posso generare un numero casuale compreso tra 0 e n dove n può essere> RAND_MAX in c, C++?

Grazie.

Answer 1

Do x numeri casuali (da 0 a RAND_MAX) e aggiungere insieme, dove

x = n% RAND_MAX

Answer 2

contempla la generazione in due fasi, quindi combinare i numeri risultanti.

Answer 3

Assumendo C++, hai provato a guardare una discreta libreria di numeri casuali, come Boost.Random. Altrimenti potrebbe essere necessario combinare più numeri casuali.

Answer 4

Ci sono molti modi per farlo.

Se si sta bene con meno granularità (maggiore possibilità di duplicazione), quindi qualcosa come (in pseudocodice) rand() * n/RAND_MAX funzionerà per diffondere i valori su un intervallo più ampio. Il problema è che nel tuo codice reale dovrai evitare l'overflow, sia tramite casting rand() o n per un tipo abbastanza grande (es. Int 64-bit se RAND_MAX è 0xFFFFFFFF) per mantenere il risultato della moltiplicazione senza overflow, o utilizzare un'API moltiplicatore-diviso (come MulDiv64 di GNU o MulDiv di Win32) ottimizzata per questo scenario.

Se si desidera ottenere la gran quantità su ciascun numero intero, è possibile chiamare rand() più volte e aggiungere i risultati. Un'altra risposta suggerisce di chiamare rand() per ogni blocco a 8-bit/16-bit/32-bit in base alla dimensione di RAND_MAX.

Ma, IMHO, le idee di cui sopra possono diventare rapidamente complicate, inaccurate o entrambe. La generazione di numeri casuali è un problema risolto in altre librerie ed è probabilmente molto più semplice prendere a prestito il codice esistente (ad esempio da Boost) piuttosto che provare a eseguire il rollover. Open source random number generation algorithm in C++? ha risposte con più collegamenti se desideri qualcosa oltre a Boost.

[EDIT: revisione dopo una giornata impegnativa ... intendeva tornare indietro e ripulire la mia risposta veloce stamattina, ma mi sono tirato indietro e sono tornato solo ora. :-)]

Answer 5

supponiamo che si desidera generare un numero casuale a 64 bit, si potrebbe fare questo:

uint64_t n = 0; 
for(int i = 0; i < 8; ++i) { 
    uint64_t x = generate_8bit_random_num(); 
    n = (n << (8 * i)) | x; 
} 

Naturalmente si potrebbe farlo 16/32 bit alla volta di troppo, ma questo illustra il concetto.

Come si generano quei numeri casuali 8/16/32-bit dipende da voi. Potrebbe essere semplice come rand() & 0xff o qualcosa di meglio a seconda di quanto ti interessa della casualità.

Answer 6

Considerare una variabile casuale che può assumere valori {0, 1} con P(0) = P(1) = 0.5. Se si desidera generare valori casuali tra 0 e 2 sommando due disegni indipendenti, si avrà P(0) = 0.25, P(1) = 0.5 e P(2) = 0.25.

Pertanto, utilizzare una libreria appropriata a meno che non ci si interessi del PDF dell'RNG.

Vedere anche il capitolo 7 in Numerical Recipes.(Questo è un collegamento all'edizione precedente ma è quello che ho studiato comunque ;-)

Answer 7

Se stai cercando una distribuzione uniforme (o qualsiasi distribuzione per quella modalità), devi fare attenzione che le proprietà statistiche di l'output è sufficiente per le tue esigenze. Se non puoi usare direttamente l'output di un generatore di numeri casuali, dovresti fare molta attenzione nel cercare di combinare i numeri per raggiungere i tuoi bisogni.

Al minimo è necessario assicurarsi che la distribuzione sia appropriata. Se siete alla ricerca di una distribuzione uniforme di numeri interi da 0 a M, e si dispone di qualche uniforme generatore di numeri casuali g() per produrre uscite che sono più piccoli di M, assicuratevi di fare non eseguire una delle seguenti operazioni:

• uscite metti k di g() insieme finché sono abbastanza grandi (il risultato è uniforme)
• take r = g() + (g() < < 16), quindi calcolare r% M (se l'intervallo di r non è un multiplo pari di M, peserà determinati valori nell'intervallo leggermente più di altri, lo stesso shift-left è univoco discutibile sg() emette un intervallo tra 0 e una potenza di 2 meno 1)

Oltre a ciò, v'è il potenziale di cross-correlazione tra i termini della sequenza (generatori di numeri casuali dovrebbero produrre identically- indipendente uscite distribuite).

Leggi l'arte della Programmazione del computer vol. 2 (Knuth) e/o Ricette numeriche e porre domande fino a quando non ti senti sicuro.

Answer 8

I numeri casuali sono un argomento molto specializzato che, a meno che tu non sia un esperto di matematica, è molto facile sbagliare. Quindi consiglierei di non creare un numero casuale da più fonti, nel caso in cui utilizzi una buona libreria.

avrei primo sguardo a boost::Random

Se questo non è prova suffecient di questo gruppo sci.crypt.random-numbers porre la domanda non ci dovrebbero essere in grado di aiutare.

Answer 9

Se l'implementazione ha un tipo intero abbastanza grande da contenere il risultato si ha bisogno, è generalmente più facile per ottenere una distribuzione decente, semplicemente utilizzando un generatore che produce la gamma richiesto che cercare di combinare le uscite dal generatore più piccolo .

Naturalmente, nella maggior parte dei casi, è sufficiente scaricare il codice per qualcosa come il Mersenne Twister o (se hai bisogno di un generatore di qualità crittografico) Blum-Blum-Shub e dimenticarti di scriverne uno tuo.