Algoritmo per il funzionamento di un generatore di numeri casuali. Generatori di numeri casuali. Metodo della congruenza lineare

I numeri casuali sono un semplice elemento della crittografia di cui si parla meno, ma che è altrettanto importante quanto il resto. Quasi tutti i sistemi di sicurezza informatica che utilizzano la crittografia richiedono numeri casuali - per chiavi, numeri univoci nei protocolli, ecc. - e la sicurezza di tali sistemi spesso dipende dalla casualità dei suoi numeri. numeri casuali. Se il generatore di numeri casuali è inaffidabile, l’intero sistema crolla.

A seconda della persona con cui parli, generare numeri casuali sembra banale o impossibile. Teoricamente questo è impossibile. John von Neumann, il padre dell’informatica, disse: “Chi crede che esistano metodi aritmetici per ottenere cifre casuali certamente pecca”. Voleva dire che è impossibile inserire qualcosa di casuale in tutti i sensi le parole sono il risultato di una bestia deterministica come un computer. Questo è vero, ma per fortuna ci sono alcune cose che possiamo fare. Ciò di cui abbiamo bisogno da un generatore di numeri casuali non è che i numeri siano veramente casuali, ma che non possano essere previsti e riprodotti. Se soddisfiamo queste due condizioni, potremo raggiungere la sicurezza.

D’altra parte, se violiamo queste due condizioni, non c’è sicurezza. Nel 1994, un generatore computerizzato di numeri casuali per le lotterie fu installato in un casinò di Montreal. Un giocatore attento che ha trascorso molto tempo al casinò ha notato che i numeri vincenti erano gli stessi ogni giorno. Ha vinto con successo tre jackpot di fila e ha ricevuto $ 600.000. (Dopo essersi torti le mani, digrignato i denti e aver indagato su tutto, il casinò ha pagato le vincite.)

Esistono diverse classi ampie di generatori di numeri casuali. Alcuni di essi si basano su processi fisici che possono essere considerati del tutto casuali. Alla National Security Agency piace utilizzare il rumore elettrico dei diodi nelle sue apparecchiature per creare numeri casuali. Altre possibilità sono i contatori Geiger o i ricevitori di interferenze radio. Un sistema su Internet utilizza Camera digitale, puntato su diversi flash. Altri sistemi utilizzano la turbolenza dell'aria nelle unità o la temporizzazione dei pacchetti di rete.

Alcuni generatori di numeri casuali tracciano i movimenti casuali dell'utente. Il programma potrebbe chiedere all'utente di digitare una lunga stringa di caratteri arbitrari sulla tastiera; può utilizzare una sequenza di caratteri o anche il tempo tra la pressione di un tasto per generare numeri casuali. Un altro programma può facilmente richiedere all'utente di spostare il mouse avanti e indietro o di grugnire nel microfono.

Alcuni generatori di numeri casuali applicano queste informazioni immesse senza modifiche. In altri, serve come seme (numero iniziale) per generatori matematici di numeri casuali. Questa tecnica funziona meglio se il sistema richiede più numeri casuali di quelli forniti dall'input.

Qualunque sia l'origine della casualità, il generatore creerà una serie di bit casuali. Possono quindi essere utilizzati come chiavi crittografiche e per tutto ciò di cui il sistema ha bisogno.

Tutti i fenomeni che ci accadono sono di due tipi: casuali e naturali. Ad esempio, non avevi abbastanza fatture per acquistare un registratore e hai deciso di acquistare un lettore, ad es. l'azione è logica e prevista. Ma, andando al negozio, scopri l'importo richiesto, che ha cambiato casualmente i piani. Il funzionamento del generatore di numeri casuali dipende completamente dal meccanismo specificato nell'operatore, in modo che tutti i numeri emessi siano pseudocasuali nell'evento corrente. Operatori che ritornano numeri casuali, si riferiscono al tempo, cioè al tempo di sistema. Quelli. Sia nel mondo che nella programmazione, nulla è completamente assoluto.

funzione Rand

Nella programmazione C sono stati inventati operatori incorporati per ottenere valori casuali, che ci danno i risultati richiesti. E quindi, per creare un numero casuale, usa funzione Rand, Quale operatore rand utilizzato per ottenere numeri casuali che restituiscono un intervallo compreso tra 0 e una determinata costante. Inoltre, questa costante è dichiarata nella direttiva di sistema “stdlib.h”, su cui si basa questa funzione rand. La sintassi di questa funzione è semplice: int m= rand(); quelli. viene restituito un numero intero. Dopo aver testato nella pratica l'operatore, vedrai che i numeri che appaiono all'avvio dell'applicazione sono identici. La svista è che l'operatore rand lavora con la stessa ora di sistema, che è stata preservata durante la compilazione. Questo generatore di numeri casuali è legato a un algoritmo per modificare l'ora del programma, quindi tutto funziona in modo errato.

Ora riguardo a srand e random

Per questo problema era indispensabile una funzione che azzerasse il tempo integrato ogni volta che veniva chiamato l'operatore rand, e gli sviluppatori del software hanno fatto funzione sand. L'azione consente alla funzione Rand di accedere ogni volta non al timer installato, ma all'attuale timer integrato, il che apre la possibilità al generatore di funzionare correttamente - per produrre valori casuali. Recentemente, nella programmazione C++, il meccanismo per l'emissione di numeri casuali è stato migliorato grazie alla comparsa dei microsecondi. Inoltre, la gamma dei valori è stata ampliata e tutte le innovazioni attuali sono state trasformate nella funzione casuale.

Ogni persona, indipendentemente dal grado di gioco d'azzardo e avventurismo, in un modo o nell'altro si è imbattuta in un concetto come una lotteria. E solo pochi si sono chiesti come avviene la distribuzione casuale combinazioni vincenti numeri Come esce questo o quel numero? Cosa fa pendere la bilancia verso il vincitore? Diamo un'occhiata a questo in dettaglio.

Tutti noi abbiamo incontrato un fenomeno come una lotteria almeno una volta nella nostra vita. Ma poche persone hanno pensato o immaginato esattamente come funziona questo sistema, cos'è un generatore di numeri per una lotteria e qual è il suo principio di funzionamento.

Il concetto di generatore di numeri

Un generatore di numeri casuali per una lotteria è un determinato dispositivo o un determinato programma che produce numeri situati in un intervallo designato in un ordine casuale (più correttamente, pseudo-casuale). Per un certo tipo di lotteria, ad esempio "Sportloto", vengono generati numeri compresi tra 1 e 49.

Esistono generatori di numeri hardware e software per la lotteria. Qualsiasi linguaggio di programmazione ha la funzione RAND(); è responsabile della produzione di numeri pseudo-casuali in un dato intervallo.

Perché si afferma che i risultati forniti sono pseudo-casuali e che il generatore di numeri della lotteria funziona esattamente secondo questo principio?

Funzione RAND: concetto e modalità di utilizzo

La funzione RAND() è un programma o, ad esempio, un dispositivo con un algoritmo deterministico che, nelle stesse condizioni specificate, mostrerà costantemente gli stessi risultati. Ma affinché le condizioni di una vera sequenza casuale siano valide, non deve esserci alcuna dipendenza da condizioni iniziali o parametri. Pertanto, da evitare casi simili, viene inoltre utilizzata una speciale procedura RANDOMIZE, che rimuove la prevedibilità delle condizioni iniziali, rendendole casuali.

Oltre al principio di generazione a noi già noto, viene utilizzato un altro tipo di generatore di lotteria. Diamo un'occhiata qui sotto.

Generatore di numeri 6 su 45

Generatore di numeri per la lotteria 6 su 45 - programma utilizzato per ottenere numeri fortunati. In questo caso è possibile impostare Opzioni aggiuntive per ottenere risultati migliori.

È possibile specificare criteri di selezione, ad esempio:

• Quantità numeri vincenti, che devono essere ottenuti nel risultato finale.
• Indicare l'intervallo di numeri in cui verrà effettuata la selezione.
• I numeri possono essere ordinati sia in ordine crescente che decrescente.
• Seleziona il tipo e il metodo di separazione.
• Elimina i duplicati o lascia la selezione non ordinata.
• Copia il collegamento al risultato e inseriscilo nella pagina in nei social network allo scopo di pubblicare il risultato.

Generatore di numeri: istruzioni per l'uso

• L'output predefinito è cinque numeri. Modificando le impostazioni, puoi ottenere fino a 250 combinazioni vincenti casuali.
• Impostiamo l'intervallo, lo standard va da 0 a 36, ​​ma puoi specificare un massimo fino a 9.999.999.999.
• Selezioniamo l'ordinamento richiesto per il nostro tipo di lotteria: ascendente, discendente o posizionando i numeri in ordine casuale.
• Il passo successivo è indicare come i numeri saranno separati l'uno dall'altro: virgola, punto, spazio, punto e virgola.
• Ci liberiamo delle ripetizioni casuali che si sono verificate durante il processo di campionamento.

In questo modo otteniamo numeri selezionati di alta qualità che possono essere i più fortunati e vincenti.

Si noti che idealmente la curva di densità di distribuzione dei numeri casuali apparirebbe come mostrata in Fig. 22.3. Cioè, nel caso ideale, ogni intervallo include stesso numero punti: N io = N/K , Dove N — numero totale punti, K numero di intervalli, io= 1, , K .

Va ricordato che la generazione di un numero casuale arbitrario consiste in due fasi:

• generare un numero casuale normalizzato (cioè distribuito uniformemente da 0 a 1);
• conversione di numeri casuali normalizzati R io a numeri casuali X io, che vengono distribuiti secondo la legge di distribuzione (arbitraria) richiesta dall'utente o nell'intervallo richiesto.

I generatori di numeri casuali secondo il metodo per ottenere i numeri sono suddivisi in:

• fisico;
• tabellare;
• algoritmico.

RNG fisico

Un esempio di RNG fisico può essere: una moneta (“testa” 1, “croce” 0); dado; un tamburo con una freccia divisa in settori con numeri; generatore di rumore hardware (HS), che utilizza un dispositivo termico rumoroso, ad esempio un transistor (Fig. 22.422.5).

RNG tabellare

Gli RNG tabulari utilizzano tabelle appositamente compilate contenenti numeri verificati non correlati, cioè non dipendenti l'uno dall'altro, come fonte di numeri casuali. Nella tabella La Figura 22.1 mostra un piccolo frammento di tale tabella. Percorrendo la tabella da sinistra a destra, dall'alto al basso, si ottengono numeri casuali distribuiti uniformemente da 0 a 1 con il numero di cifre decimali richiesto (nel nostro esempio utilizziamo tre cifre decimali per ogni numero). Poiché i numeri nella tabella non dipendono l'uno dall'altro, la tabella può essere attraversata diversi modi, ad esempio, dall'alto verso il basso o da destra a sinistra oppure, ad esempio, puoi selezionare i numeri che si trovano in posizioni pari.

Dignità questo metodoè che produce numeri veramente casuali poiché la tabella contiene numeri non correlati verificati. Svantaggi del metodo: per l'archiviazione grande quantità i numeri richiedono molta memoria; Ci sono grandi difficoltà nel generare e controllare questo tipo di tabelle; le ripetizioni nell'utilizzo di una tabella non garantiscono più la casualità della sequenza numerica, e quindi l'attendibilità del risultato.

C'è una tabella contenente 500 numeri verificati assolutamente casuali (tratti dal libro di I. G. Venetsky, V. I. Venetskaya “Concetti e formule matematici e statistici di base nell'analisi economica”).

RNG algoritmico

I numeri generati da questi RNG sono sempre pseudo-casuali (o quasi-casuali), cioè ogni numero successivo generato dipende da quello precedente:

R io + 1 = F(R io) .

Le sequenze composte da tali numeri formano dei loop, cioè esiste necessariamente un ciclo che si ripete numero infinito una volta. I cicli ripetuti sono chiamati periodi.

Il vantaggio di questi RNG è la loro velocità; i generatori non richiedono praticamente risorse di memoria e sono compatti. Svantaggi: i numeri non possono essere definiti del tutto casuali, poiché esiste una dipendenza tra loro, così come la presenza di punti nella sequenza di numeri quasi casuali.

Consideriamo diversi metodi algoritmici per ottenere RNG:

• metodo dei quadrati mediani;
• metodo dei prodotti medi;
• metodo di agitazione;
• metodo della congruenza lineare.

Metodo del quadrato medio

C'è un numero di quattro cifre R 0 . Questo numero viene quadrato e inserito R 1 . Avanti da R 1 prende il nuovo numero casuale centrale (quattro cifre centrali) e lo scrive R 0 . Quindi la procedura viene ripetuta (vedere Fig. 22.6). Tieni presente che in effetti non devi prendere un numero casuale ghij, UN 0.ghij con uno zero e un punto decimale aggiunti a sinistra. Questo fatto si riflette come in Fig. 22.6, e nelle successive figure simili.

Svantaggi del metodo: 1) se ad alcune iterazioni il numero R 0 diventa uguale a zero, quindi il generatore degenera, quindi è importante la scelta corretta del valore iniziale R 0; 2) il generatore ripeterà la sequenza M N passi (dentro scenario migliore), Dove N cifra del numero R 0 , M base del sistema numerico.

Ad esempio nella Fig. 22.6: se il numero R 0 sarà rappresentato nel sistema di numerazione binario, quindi la sequenza numeri pseudocasuali si ripete in 2 4 = 16 passi. Si noti che la ripetizione della sequenza può avvenire prima se il numero iniziale viene scelto male.

Il metodo sopra descritto è stato proposto da John von Neumann e risale al 1946. Poiché questo metodo si è rivelato inaffidabile, è stato rapidamente abbandonato.

Metodo del prodotto medio

Numero R 0 moltiplicato per R 1, dal risultato ottenuto R 2 viene estratta la parte centrale R 2 * (questo è un altro numero casuale) e moltiplicato per R 1 . Tutti i numeri casuali successivi vengono calcolati utilizzando questo schema (vedi Fig. 22.7).

Metodo di agitazione

Il metodo shuffle utilizza le operazioni per spostare ciclicamente il contenuto di una cella a sinistra e a destra. L'idea del metodo è la seguente. Lascia che la cella memorizzi il numero iniziale R 0 . Spostando ciclicamente il contenuto della cella verso sinistra di 1/4 della lunghezza della cella, otteniamo un nuovo numero R 0*. Allo stesso modo, ciclando il contenuto della cella R 0 a destra di 1/4 della lunghezza della cella, otteniamo il secondo numero R 0**. Somma di numeri R 0* e R 0** fornisce un nuovo numero casuale R 1 . Ulteriore R 1 è inserito R 0, e l'intera sequenza di operazioni viene ripetuta (vedi Fig. 22.8).

Si prega di notare che il numero risultante dalla somma R 0* e R 0 ** , potrebbe non rientrare completamente nella cella R 1 . In questo caso, le cifre extra devono essere scartate dal numero risultante. Spieghiamo questo in Fig. 22.8, dove tutte le celle sono rappresentate da otto cifre binarie. Permettere R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Poi R 0 * + R 0 ** = 100110010 2 = 306 10 . Come puoi vedere, il numero 306 occupa 9 cifre (nel sistema numerico binario) e la cella R 1 (uguale a R 0) può contenere un massimo di 8 bit. Pertanto, prima di inserire il valore in R 1, è necessario rimuovere un bit “extra”, più a sinistra, dal numero 306, ottenendo come risultato R 1 non andrà più a 306, ma a 00110010 2 = 50 10 . Si noti inoltre che in linguaggi come Pascal, il "ritaglio" di bit extra quando una cella trabocca viene eseguito automaticamente in base al tipo specificato della variabile.

Metodo della congruenza lineare

Il metodo della congruenza lineare è una delle procedure più semplici e comunemente utilizzate attualmente per simulare numeri casuali. Questo metodo utilizza il mod( X, sì) , che restituisce il resto quando il primo argomento viene diviso per il secondo. Ogni numero casuale successivo viene calcolato in base al numero casuale precedente utilizzando la seguente formula:

R io+ 1 = mod( K · R io + B, M) .

Viene chiamata la sequenza di numeri casuali ottenuta utilizzando questa formula sequenza lineare congruente. Molti autori chiamano una successione lineare congruente quando B = 0 metodo moltiplicativo congruente, e quando B ≠ 0 — metodo misto congruente.

Per un generatore di alta qualità, è necessario selezionare coefficienti adeguati. È necessario che il numero M era piuttosto grande, poiché il periodo non può averne di più M elementi. D’altra parte, la divisione utilizzata in questo metodo è un’operazione piuttosto lenta, quindi per un computer binario la scelta logica sarebbe M = 2 N, poiché in questo caso la ricerca del resto della divisione si riduce all'interno del computer all'operazione logica binaria “AND”. È comune anche la scelta del numero primo più grande M, meno di 2 N: nella letteratura specializzata è dimostrato che in questo caso le cifre di ordine basso del numero casuale risultante R io+1 si comportano in modo altrettanto casuale come quelli più vecchi, il che ha un effetto positivo sull'intera sequenza di numeri casuali nel suo insieme. Ad esempio, uno dei Numeri di Mersenne, pari a 2 31 1, e quindi, M= 2 31 1 .

Uno dei requisiti per le sequenze lineari congruenti è che la lunghezza del periodo sia la più lunga possibile. La durata del periodo dipende dai valori M , K E B. Il teorema che presentiamo di seguito ci permette di determinare se è possibile raggiungere il periodo lunghezza massima per valori specifici M , K E B .

Teorema. Sequenza lineare congruente definita da numeri M , K , B E R 0, ha un periodo di lunghezza M se e solo se:

• numeri B E M relativamente semplice;
• K 1 volta P per ogni numero primo P, che è un divisore M ;
• K 1 è un multiplo di 4, se M multiplo di 4.

Infine, concludiamo con un paio di esempi di utilizzo del metodo della congruenza lineare per generare numeri casuali.

È stato stabilito che una serie di numeri pseudo-casuali generati sulla base dei dati dell'esempio 1 verrebbe ripetuta ogni M/4 numeri. Numero Qè impostato arbitrariamente prima dell'inizio dei calcoli, tuttavia, va tenuto presente che la serie dà l'impressione di essere in generale casuale K(e quindi Q). Il risultato può essere leggermente migliorato se B strano e K= 1 + 4 · Q in questo caso la riga verrà ripetuta ogni M numeri. Dopo una lunga ricerca K i ricercatori si sono stabiliti sui valori di 69069 e 71365.

Un generatore di numeri casuali che utilizza i dati dell'esempio 2 produrrà numeri casuali non ripetitivi con un periodo di 7 milioni.

Il metodo moltiplicativo per generare numeri pseudocasuali fu proposto da D. H. Lehmer nel 1949.

Controllo della qualità del generatore

La qualità dell'intero sistema e l'accuratezza dei risultati dipendono dalla qualità dell'RNG. Pertanto, la sequenza casuale generata dal RNG deve soddisfare una serie di criteri.

I controlli effettuati sono di due tipi:

• controlli sull'uniformità della distribuzione;
• test di indipendenza statistica.

Controlla l'uniformità della distribuzione

1) L'RNG dovrebbe produrre valori prossimi ai seguenti parametri statistici caratteristici di una legge casuale uniforme:

2) Prova di frequenza

Un test di frequenza ti consente di scoprire quanti numeri rientrano in un intervallo (M R – σ R ; M R + σ R) , cioè (0,5 0,2887; 0,5 + 0,2887) o, in definitiva, (0,2113; 0,7887). Poiché 0,7887 0,2113 = 0,5774, concludiamo che in un buon RNG, circa il 57,7% di tutti i numeri casuali estratti dovrebbe rientrare in questo intervallo (vedere Figura 22.9).

È inoltre necessario tenere conto del fatto che il numero di numeri che rientrano nell'intervallo (0; 0,5) dovrebbe essere approssimativamente uguale al numero di numeri che rientrano nell'intervallo (0,5; 1).

3) Test del chi quadrato

Il test del chi quadrato (test del χ2) è uno dei test statistici più conosciuti; è il metodo principale utilizzato in combinazione con altri criteri. Il test del chi quadrato fu proposto nel 1900 da Karl Pearson. Il suo notevole lavoro è considerato il fondamento della moderna statistica matematica.

Nel nostro caso, il test utilizzando il criterio del chi quadrato ci consentirà di scoprire quanto il vero RNG è vicino Norma RNG, cioè se soddisfa o meno il requisito della distribuzione uniforme.

Diagramma di frequenza riferimento L'RNG è mostrato in Fig. 22.10. Poiché la legge di distribuzione del RNG di riferimento è uniforme, allora la probabilità (teorica). P io inserire i numeri io th intervallo (tutti questi intervalli K) è uguale a P io = 1/K . E così, in ciascuno di K gli intervalli colpiranno liscio Di P io · N numeri ( N numero totale di numeri generati).

Un vero RNG produrrà numeri distribuiti (e non necessariamente in modo uniforme!) K intervalli e ogni intervallo conterrà N io numeri (in totale N 1 + N 2 + + N K = N ). Come possiamo determinare quanto è buono l'RNG testato e quanto è vicino a quello di riferimento? È abbastanza logico considerare le differenze al quadrato tra il numero di numeri risultante N io e "riferimento" P io · N . Sommiamoli e il risultato è:

χ2 esp. = ( N 1 P 1 · N) 2 + (N 2 P 2 · N) 2 + + ( N K – P K · N) 2 .

Da questa formula ne consegue che minore è la differenza in ciascuno dei termini (e quindi il meno valoreχ2 esp. ), quanto più forte è la legge di distribuzione dei numeri casuali generati da un RNG reale, tende ad essere uniforme.

Nell'espressione precedente a ciascuno dei termini viene assegnato lo stesso peso (pari a 1), il che di fatto potrebbe non essere vero; pertanto, per le statistiche chi-quadrato, è necessario normalizzarli ciascuno io termine, dividendolo per P io · N :

Infine, scriviamo l’espressione risultante in modo più compatto e semplifichiamola:

Abbiamo ottenuto il valore del test chi quadrato per sperimentale dati.

Nella tabella 22.2 sono dati teorico valori del chi-quadrato (χ 2 teorico), dove ν = N 1 è il numero di gradi di libertà, P questo è un livello di confidenza specificato dall'utente che indica in che misura l'RNG dovrebbe soddisfare i requisiti di una distribuzione uniforme, oppure P — è la probabilità che il valore sperimentale di χ 2 exp. sarà inferiore al χ 2 teorico tabulato (teorico). o uguale ad esso.

Considerato accettabile P dal 10% al 90%.

Se χ 2 esp. molto più della teoria del χ2. (questo è Pè grande), quindi il generatore non soddisfa il requisito della distribuzione uniforme, a partire dai valori osservati N io andare troppo lontano dal teorico P io · N e non può essere considerato casuale. In altre parole, è installato così grande intervallo di confidenza, che le restrizioni sui numeri diventano molto allentate, i requisiti sui numeri diventano deboli. In questo caso, si osserverà un errore assoluto molto grande.

Anche D. Knuth nel suo libro “The Art of Programming” ha notato che avendo χ 2 exp. per i piccoli, in generale, non va bene nemmeno, anche se questo sembra, a prima vista, meraviglioso dal punto di vista dell'uniformità. Infatti, prendiamo una serie di numeri 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, sono ideali dal punto di vista dell'uniformità, e χ 2 esp. saranno praticamente zero, ma difficilmente li riconoscerete come casuali.

Se χ 2 esp. molto meno della teoria del χ2. (questo è P piccolo), quindi il generatore non soddisfa il requisito di una distribuzione casuale uniforme, a partire dai valori osservati N io troppo vicino al teorico P io · N e non può essere considerato casuale.

Ma se χ 2 esp. si trova in un certo intervallo tra due valori di χ 2 o. , che corrispondono, ad esempio, P= 25% e P= 50%, allora possiamo supporre che i valori dei numeri casuali generati dal sensore siano completamente casuali.

Inoltre, va tenuto presente che tutti i valori P io · N deve essere abbastanza grande, ad esempio più di 5 (trovato empiricamente). Solo allora (con un campione statistico sufficientemente ampio) le condizioni sperimentali potranno essere considerate soddisfacenti.

Pertanto, la procedura di verifica è la seguente.

Test di indipendenza statistica

1) Controllo della frequenza di occorrenza dei numeri nella sequenza

Diamo un'occhiata a un esempio. Il numero casuale 0.2463389991 è composto dalle cifre 2463389991, mentre il numero 0.5467766618 è composto dalle cifre 5467766618. Collegando le sequenze di cifre, abbiamo: 24633899915467766618.

È chiaro che la probabilità teorica P io perdita io L'esima cifra (da 0 a 9) è pari a 0,1.

2) Controllare l'aspetto di serie di numeri identici

Indichiamo con N l numero di serie di cifre identiche in una riga di lunghezza l. Tutto deve essere controllato l da 1 a M, Dove M questo è un numero specificato dall'utente: il numero massimo di cifre identiche presenti in una serie.

Nell’esempio “24633899915467766618” sono state trovate 2 serie di lunghezza 2 (33 e 77), ovvero N 2 = 2 e 2 serie di lunghezza 3 (999 e 666), cioè N 3 = 2 .

La probabilità che si verifichi una serie di lunghezza lè uguale a: P l= 9 10 l (teorico). Cioè, la probabilità che si verifichi una serie lunga un carattere è uguale a: P 1 = 0,9 (teorico). La probabilità che appaia una serie di due caratteri è: P 2 = 0,09 (teorico). La probabilità che appaia una serie di tre caratteri è: P 3 = 0,009 (teorico).

Ad esempio, la probabilità che si verifichi una serie lunga un carattere è P l= 0,9, poiché può esserci un solo simbolo su 10 e ci sono 9 simboli in totale (lo zero non conta). E la probabilità che due simboli identici “XX” appaiano in fila è 0,1 · 0,1 · 9, cioè la probabilità di 0,1 che il simbolo “X” appaia in prima posizione è moltiplicata per la probabilità di 0,1 che il simbolo “X” appaia in prima posizione lo stesso simbolo apparirà nella seconda posizione “X” e moltiplicato per il numero di tali combinazioni 9.

La frequenza di occorrenza delle serie viene calcolata utilizzando la formula del chi quadrato di cui abbiamo discusso in precedenza utilizzando i valori P l .

Nota: il generatore può essere testato più volte, ma i test non sono completi e non garantiscono che il generatore produca numeri casuali. Ad esempio, un generatore che produce la sequenza 12345678912345 sarà considerato ideale durante i test, il che ovviamente non è del tutto vero.

In conclusione, notiamo che il terzo capitolo del libro di Donald E. Knuth The Art of Programming (Volume 2) è interamente dedicato allo studio dei numeri casuali. Studia vari metodi generazione di numeri casuali, test statistici di casualità e conversione di numeri casuali distribuiti uniformemente in altri tipi variabili casuali. Più di duecento pagine sono dedicate alla presentazione di questo materiale.