Come funziona rand()? Ha certe tendenze? C'è qualcosa di meglio da usare?

Question

Ho letto che ha qualcosa a che fare con il tempo, anche tu hai compreso da tempo.h, quindi ho pensato molto, ma come funziona esattamente? Inoltre, ha qualche tendenza verso numeri pari o dispari o qualcosa del genere? E infine c'è qualcosa con una migliore distribuzione nella libreria standard C o nel framework Foundation?

Answer 1

rand numeri di ritorno generati da un pseudo-random number generator (PRNG). La sequenza di numeri che restituisce è deterministica, in base al valore con cui è stato inizializzato il PRNG (chiamando srand).

I numeri devono essere distribuiti in modo tale da apparire alquanto casuali, pertanto, ad esempio, i numeri pari e dispari devono essere restituiti all'incirca alla stessa frequenza. L'effettiva implementazione del generatore di numeri casuali non è stata specificata, quindi il comportamento effettivo è specifico per l'implementazione.

La cosa importante da ricordare è che rand non restituisce numeri casuali; restituisce numeri pseudo-casuali e i valori che restituisce sono determinati dal valore di inizializzazione e dal numero di volte in cui è stato chiamato lo rand. Questo comportamento va bene per molti casi d'uso, ma non è appropriato per altri (ad esempio, rand non sarebbe appropriato per l'uso in molte applicazioni crittografiche).

Answer 2

Come funziona rand()?

http://en.wikipedia.org/wiki/Pseudorandom_number_generator

Ho letto che ha qualcosa a che fare con il tempo , anche si ottiene da compreso time.h

rand() non ha nulla a che fare con la tempo. Tuttavia, è molto comune utilizzare time() per ottenere il "seme" per il PRNG in modo da ottenere numeri "casuali" diversi ogni volta che si esegue il programma.

Inoltre, ce l'ha tutte le tendenze verso pari o dispari numeri o qualcosa del genere?

Dipende dal metodo esatto utilizzato. C'è un'implementazione popolare di rand() che sostituisce tra numeri pari e dispari. Quindi evita di scrivere codice come rand() % 2 che dipende dal fatto che il bit più basso sia casuale.

Answer 3

In breve:

• si utilizza time.h per ottenere un seme, che è un numero casuale iniziale. C poi fa un mucchio di operazioni su questo numero per ottenere il prossimo numero casuale, quindi le operazioni su quello per ottenere il successivo, quindi ... ottieni l'immagine.

• rand() è in grado di toccare tutti i numeri interi possibili. Non preferirà i numeri pari o dispari indipendentemente dal seme di input, felicemente. Tuttavia, ha dei limiti: si ripete in tempi relativamente brevi e in quasi tutte le implementazioni fornisce solo numeri fino a 32767.

• C non ha un altro generatore di numeri casuali incorporato. Se hai bisogno di una soluzione veramente dura, ci sono molti pacchetti disponibili online, ma l'algoritmo Mersenne Twister è probabilmente la scelta più popolare.

Ora, se siete interessati sui motivi quanto sopra perché è vero, ecco i dettagli scabrosi su come rand() opere:

rand() è quello che viene chiamato un "linear congruential generator." Ciò significa che impiega un'equazione della forma:

x _{n + 1 =} (* a **** x _n + b * ***) mod m

dove x _n è il numero casuale n^th e un e b sono alcuni numeri interi predeterminati. L'aritmetica viene eseguita modulo m, con m solito 2 seconda della macchina, in modo che solo i più bassi 32 bit vengono mantenute nel calcolo di x _{n + 1}.

In inglese, quindi, l'idea è questa: per ottenere il numero casuale successivo, moltiplicare l'ultimo numero casuale per qualcosa, aggiungere un numero e quindi prendere le ultime cifre.

alcune limitazioni sono subito evidente:

• In primo luogo, è necessario un numero casuale di partenza. Questo è il "seme" del tuo generatore di numeri casuali, ed è qui che hai sentito parlare di time.h. Dal momento che vogliamo un numero veramente casuale, è pratica comune chiedere al sistema a che ora è (in forma intera) e usarlo come il primo "numero casuale". Inoltre, questo spiega perché usare lo stesso seme due volte sarà sempre dare esattamente la stessa sequenza di numeri casuali. Questo suona male, ma in realtà è utile, dal momento che il debug è molto più facile quando si controlla gli ingressi al vostro programma

• In secondo luogo, un e b devono essere scelti molto, molto attentamente o otterrai dei risultati disastrosi. Fortunatamente, l'equazione per un generatore congruenziale lineare è abbastanza semplice che la matematica è stata elaborata in dettaglio. Risulta che la scelta di un un che soddisfa * un *** mod8 = 5 assieme *** b * = 1 assicurerà che tutte m interi sono equiprobabili, indipendentemente scelta delle sementi.Si vuole anche un valore di un che è davvero grande, in modo che ogni volta che si moltiplicarlo per x _n si innescare una il modulo e tritare fuori un sacco di cifre, oppure molti numeri di fila sarà solo essere multipli l'uno dell'altro Di conseguenza, due valori comuni di a (ad esempio) sono 1566083941 e 1812433253 secondo Knuth. La libreria GNU C capita di utilizzare un = 1.103.515,245 mila e b = 12345. Un elenco di valori per molte implementazioni è disponibile allo wikipedia page for LCGs.

• In terzo luogo, il generatore congruenziale lineare si ripeterà effettivamente a causa di quel modulo. Questo può essere un bel problema, ma il risultato di tutto è felicemente molto semplice: la sequenza si ripeterà dopo m dei numeri di generati. Nella maggior parte dei casi, ciò significa che il generatore di numeri casuali si ripeterà ogni 2 cicli. Sembra molto, ma in realtà non è per molte applicazioni. Se stai facendo un serio lavoro numerico con le simulazioni Monte Carlo, questo numero è irrimediabilmente inadeguato.

• Un quarto problema molto meno ovvio è che i numeri in realtà non sono in realtà casuale. Hanno una specie di correlazione divertente. Se si prende tre numeri interi consecutivi, (x, y, z), da un LCG con un certo valore di un e m, questi tre punti sarà sempre caduta sul reticolo di punti generati da tutte le combinazioni lineari dei tre punti (1, a, a), (0, m, 0), (0, 0, m). Questo è noto come il Teorema di Marsaglia e, se non lo capisci, va bene. Tutto ciò significa che: le terzine di numeri casuali di un LCG mostreranno correlazioni a qualche livello profondo e profondo. Di solito è troppo profondo per te o me per notare, ma è lì. È possibile anche ricostruire il primo numero in una sequenza "casuale" di tre numeri se vi viene data la seconda e la terza! Questo non è affatto positivo per la crittografia.

La parte buona è che LCGs come rand() sono molto, molto basso ingombro. Normalmente richiede solo 32 bit per conservare lo stato, il che è davvero piacevole. È anche molto veloce, richiede pochissime operazioni. Ciò lo rende buono per i sistemi embedded non critici, i videogiochi, le applicazioni casuali, cose del genere.

I PRNG sono un argomento affascinante. Wikipedia è sempre un buon posto dove andare se hai fame per saperne di più sulla storia o sulle varie implementazioni che ci sono oggi.