Software-ul aproape tuturor calculatoarelor are o funcție încorporată pentru generarea unei secvențe de numere pseudoaleatoare cvasi-uniform distribuite. Cu toate acestea, pentru modelarea statistică, se impun cerințe sporite pentru generarea de numere aleatorii. Calitatea rezultatelor unei astfel de modelări depinde direct de calitatea generatorului de numere aleatoare distribuite uniform, deoarece aceste numere sunt și surse (date inițiale) pentru obținerea altor variabile aleatoare cu o lege de distribuție dată.
Din păcate, generatoarele ideale nu există, iar lista proprietăților lor cunoscute este completată cu o listă de dezavantaje. Acest lucru duce la riscul de a utiliza un generator prost într-un experiment pe computer. Prin urmare, înainte de a efectua un experiment pe computer, este necesar fie să se evalueze calitatea funcției de generare a numerelor aleatoare încorporată în computer, fie să se selecteze un algoritm adecvat de generare a numerelor aleatoare.
Pentru a fi utilizat în fizica computațională, generatorul trebuie să aibă următoarele proprietăți:
Eficiența de calcul este cel mai scurt timp posibil de calcul pentru următorul ciclu și cantitatea de memorie pentru rularea generatorului.
Lungime mare L secvență aleatorie de numere. Această perioadă trebuie să includă cel puțin setul de numere aleatorii necesare unui experiment statistic. În plus, chiar și apropierea de sfârșitul lui L reprezintă un pericol, care poate duce la rezultate incorecte ale unui experiment statistic.
Criteriul pentru o lungime suficientă a unei secvențe pseudoaleatoare este ales dintre următoarele considerații. Metoda Monte Carlo constă în calcule repetate ale parametrilor de ieșire ai unui sistem simulat sub influența parametrilor de intrare care fluctuează cu legile de distribuție date. Baza implementării metodei este generarea de numere aleatorii cu uniformă distribuție în intervalul din care se formează numere aleatoare cu legi date de distribuție. În continuare, probabilitatea evenimentului simulat este calculată ca raportul dintre numărul de repetări ale experimentelor model cu un rezultat de succes și numărul total de repetări ale experimentelor în condiții inițiale (parametrii) date ale modelului.
Pentru un calcul fiabil, în sens statistic, al acestei probabilități, numărul de repetări ale experimentului poate fi estimat folosind formula:
Unde 
-functie, funcție inversă distributie normala, 
- probabilitatea de eroare de încredere 
Măsurători de probabilitate.
Prin urmare, pentru ca eroarea să nu depășească intervalul de încredere cu probabilitatea de încredere, de exemplu =0,95 este necesar ca numărul de repetări ale experimentului să nu fie mai mic decât:
(2.2)
De exemplu, pentru o eroare de 10% (
=0,1) obținem 
și pentru o eroare de 3% (
=0,03) obținem deja 
.
Pentru ceilalti condiții inițiale model, o nouă serie de repetări de experimente ar trebui efectuată pe o secvență pseudo-aleatorie diferită. Prin urmare, fie funcția de generare a secvenței pseudoaleatoare trebuie să aibă un parametru care o modifică (de exemplu, R 0 ), sau lungimea sa trebuie să fie de cel puțin:
Unde K - numărul de condiții inițiale (puncte de pe curbă determinate prin metoda Monte Carlo), N - numărul de repetări ale experimentului model în condiții inițiale date, L - lungimea secvenței pseudoaleatoare.
Apoi fiecare serie de N repetările fiecărui experiment vor fi efectuate pe propriul segment al secvenței pseudoaleatoare.
Reproductibilitatea. După cum sa menționat mai sus, este de dorit să existe un parametru care modifică generarea numerelor pseudoaleatoare. De obicei, acesta este R 0 . Prin urmare, este foarte important ca schimbarea 0 nu a stricat calitatea (adică parametrii statistici) generatorului de numere aleatorii.
Proprietăți statistice bune. Acesta este cel mai important indicator al calității unui generator de numere aleatorii. Cu toate acestea, nu poate fi evaluată prin niciun criteriu sau test, deoarece Nu există criterii necesare și suficiente pentru caracterul aleatoriu al unei secvențe finite de numere. Cel mai mult care se poate spune despre o secvență pseudo-aleatoare de numere este că „pare” aleatoriu. Nici un singur test statistic nu este un indicator de încredere al acurateței. Cel puțin, este necesar să se utilizeze mai multe teste care reflectă cele mai importante aspecte ale calității generatorului de numere aleatorii, adică. gradul de aproximare a acestuia la un generator ideal.
Prin urmare, pe lângă testarea generatorului, este extrem de important să îl testați folosind probleme standard care permit evaluarea independentă a rezultatelor prin metode analitice sau numerice.
Se poate spune că ideea fiabilității numerelor pseudoaleatoare este creată în procesul de utilizare a acestora, verificând cu atenție rezultatele ori de câte ori este posibil.
Primul algoritm pentru obținerea numerelor pseudoaleatoare a fost propus de J. Neumann. Se numește metoda mijlocului pătratelor.
Să fie dat un număr R din 4 cifre 0 =0,9876. Să-l pătram. Să obținem un număr R din 8 cifre 0 2 =0,97535376. Să alegem cele 4 cifre din mijloc din acest număr și să punem R 1 =0,5353. Apoi îl pătram din nou și extragem cele 4 cifre din mijloc din el. Primim R 2 etc. Acest algoritm nu s-a dovedit. S-au dovedit a fi mai mult decât necesare valori mici ale lui R i .
Cu toate acestea, este interesant să se investigheze calitatea acestui generator cu grupul de selecție a cifrelor R deplasat la dreapta i 2 :
unde a este valoarea maximă a fracției pentru un computer dat (de exemplu, a = 8).
b-numărul de zecimale din numărul R i(de exemplu, 5).
INT(A)- întreaga parte numere.
Pentru a=8,b=5,R 0 =0,51111111 pe PC ZX-Spectrum, rezultă aproximativ 1200 de numere care nu se repetă.
Exercițiu: Studiul ar trebui efectuat prin variarea a, b, R 0 . Aflați la ce valori a, b, R 0 cea mai mare lungime L a unei secvențe de numere care nu se repetă se obține cu parametri stocastici „buni”. Determinați dacă valoarea R influențează 0 asupra calitatii senzorului. Dacă da, atunci determinați intervalul de valori „acceptabile” ale parametrului R 0 . Prezentați rezultatele testării variantei optime a valorilor a, b, R 0 .
Algoritmi multiplicativi. Senzorul #2: Lehmer 1951 Generator Linear Congruent.
unde U i,M,Cip – numere întregi.
AmodB este restul din întreaga diviziune a lui A în B,
A mod B =A-B*INT (A/B)
Secvența generată are un ciclu repetat care nu depășește p numere.
Perioada maximă se obține la C0, dar un astfel de generator dă rezultate stocastice slabe.
Când C=0 generatoarele se numesc multiplicative. Au parametri stocastici mai buni. Formulele de utilizare a acestora se mai numesc si metoda deducerilor.
Cea mai populară metodă pentru obținerea numerelor pseudoaleatoare este metoda deducerilor folosind următoarea formulă:
unde U i,M,p-întregi, 0
Dacă selectați U 0 și M astfel încât pentru R 0 =U 0 /p s-a dovedit a fi o fracție ireductibilă și ia p și M ca fiind primi reciproc, apoi totul R i vor fi fracții ireductibile de forma: R i=U i/p.
Să obținem lungimea cea mai mare (dar nu mai mare de p) a unei secvențe de numere care nu se repetă. valorile U 0 ,pM este convenabil să alegeți dintre numere prime.
Exercițiu: Investigați la ce U 0 ,pM, lungimea secvenței de numere care nu se repetă va fi de cel puțin 10000 cu parametri stocastici „buni”. Determinați dacă valoarea lui R 0 când Mip = const pe caracteristicile statistice ale senzorului. Dacă da, atunci determinați intervalul de valori permise U 0 . Prezentați rezultatele testării generatorului pentru valorile optime ale p, Mi și U 0 .
Senzorul nr. 3: modificarea Korobov.
unde p este un număr prim mare, de exemplu 2027, 5087, ...
M este un număr întreg care îndeplinește condițiile:
n este un număr întreg. Acestea. alegeți M apropiat de p/2 din mulțimea numerelor M = p – 3 n .
De exemplu, pentru p=5087 luăm n=7. Pentru că 3 7 =2187 și 3 8 =6561 va fi deja mai mare. Deci: M=5087-2187=2900.
Obținem numerele U iîn intervalul = și numerele R iîn intervalul (0,1).
Exercițiu: Selectați Mp pentru care se obțin cei mai buni parametri statistici ai senzorului și cea mai mare lungime L. Aflați dacă valoarea lui R 0 asupra caracteristicilor stocastice ale senzorului și, dacă este afectat, apoi determinați intervalul de valori permise R 0 . Prezentați rezultatele testării senzorilor pentru valorile optime ale M, p și R 0 .
PRNG-uri deterministe
Niciun algoritm determinist nu poate genera numere complet aleatoare, ci poate doar aproxima unele proprietăți ale numerelor aleatoare. După cum spunea John von Neumann, „ oricine are o slăbiciune pentru metodele aritmetice de obținere a numerelor aleatorii este păcătos dincolo de orice îndoială».
Orice PRNG cu resurse limitate, mai devreme sau mai târziu, trece în cicluri - începe să repete aceeași secvență de numere. Lungimea ciclurilor PRNG depinde de generatorul în sine și are o medie de aproximativ 2n/2, unde n este dimensiunea stării interne în biți, deși generatoarele liniare congruente și LFSR au cicluri maxime de ordinul a 2n. Dacă un PRNG poate converge către cicluri prea scurte, PRNG devine previzibil și inutilizabil.
Majoritatea generatoarelor aritmetice simple, deși foarte rapide, suferă de multe dezavantaje serioase:
- Perioada/perioadele sunt prea scurte.
- Valorile consecutive nu sunt independente.
- Unele biți sunt „mai puțin aleatorii” decât altele.
- Distribuție unidimensională neuniformă.
- Reversibilitate.
În special, algoritmul mainframe s-a dovedit a fi foarte slab, ceea ce a ridicat îndoieli cu privire la validitatea rezultatelor multor studii care au folosit acest algoritm.
PRNG cu sursă de entropie sau RNG
Așa cum este nevoie de a genera secvențe de numere aleatoare ușor de repetat, există și nevoia de a genera numere complet imprevizibile sau pur și simplu complet aleatorii. Se numesc astfel de generatoare generatoare de numere aleatorii(RNG - engleză) generator de numere aleatorii, RNG). Deoarece astfel de generatoare sunt cel mai adesea folosite pentru a genera chei unice simetrice și asimetrice pentru criptare, ele sunt cel mai adesea construite dintr-o combinație de PRNG criptografic puternic și o sursă externă de entropie (și tocmai această combinație este acum înțeleasă ca un RNG).
Aproape toți marii producători de cipuri furnizează RNG-uri hardware cu diverse surse de entropie, folosind diverse metode pentru a le curăța de predictibilitatea inevitabilă. Cu toate acestea, în acest moment, viteza cu care sunt colectate numere aleatoare de către toate microcipurile existente (câteva mii de biți pe secundă) nu corespunde cu viteza procesoarelor moderne.
În calculatoarele personale, autorii de software RNG folosesc surse mult mai rapide de entropie, cum ar fi zgomotul plăcii de sunet sau contorul ciclului de ceas al procesorului. Înainte să devină posibilă citirea valorilor contorului ceasului, colectarea entropiei era punctul cel mai vulnerabil al RNG. Această problemă încă nu este pe deplin rezolvată în multe dispozitive (de exemplu, smart carduri), care rămân astfel vulnerabile. Multe RNG-uri încă folosesc metode tradiționale (învechite) de colectare a entropiei, cum ar fi măsurarea reacțiilor utilizatorilor (mișcarea mouse-ului etc.), ca, de exemplu, sau interacțiunea dintre fire, ca în Java secure random.
Exemple de surse RNG și entropie
Câteva exemple de RNG-uri cu sursele și generatorii lor de entropie:
| Sursa de entropie | PRNG | Avantaje | Defecte | |
|---|---|---|---|---|
| /dev/random pe Linux | Contor de ceas CPU, totuși colectat numai în timpul întreruperilor hardware | LFSR, cu hash de ieșire prin | Se „încălzește” pentru o perioadă foarte lungă de timp, se poate „bloca” pentru o lungă perioadă de timp sau funcționează ca un PRNG ( /dev/urandom) | |
| Sorile de Bruce Schneier | Metode tradiționale (învechite). | AES-256 și | Design flexibil criptorezistent | Este nevoie de mult timp pentru a se „încălzi”, stare internă foarte mică, depinde prea mult de puterea criptografică a algoritmilor selectați, lent, aplicabil exclusiv pentru generarea cheilor |
| Generator de Leonid Yuryev | Zgomotul plăcii de sunet | ? | Cel mai probabil o sursă bună și rapidă de entropie | Niciun PRNG cripto-puternic independent, cunoscut, disponibil exclusiv ca Windows |
| Microsoft | Încorporat în Windows, nu se blochează | Stare internă mică, ușor de prezis | ||
| Comunicarea între fire | Nu există încă o altă opțiune în Java, există o stare internă mare | Colectare lentă a entropiei | ||
| Haos de Ruptor | Contor ceas al procesorului, colectat continuu | Hashing starea internă de 4096 de biți bazată pe o variantă neliniară a generatorului Marsaglia | Până când cel mai rapid dintre toate, marea stare internă, se „blochează” | |
| RRAND de la Ruptor | Contor de cicluri CPU | Criptarea stării interne cu un cod de flux | Foarte rapid, stare internă de dimensiune arbitrară din care să alegeți, fără „blocat” |
PRNG în criptografie
Un tip de PRNG sunt PRBG-uri - generatoare de biți pseudo-aleatorii, precum și diverse cifruri de flux. PRNG-urile, cum ar fi cifrurile de flux, constau într-o stare internă (de obicei variind în dimensiune de la 16 biți la câțiva megaocteți), o funcție de inițializare a stării interne cu o cheie sau sămânță(Engleză) sămânță), funcții interne de actualizare a stării și funcții de ieșire. PRNG-urile sunt împărțite în aritmetică simplă, criptografic rupt și puternic criptografic. Scopul lor general este de a genera secvențe de numere care nu pot fi distinse de aleatorii prin metode de calcul.
Deși multe PRNG-uri puternice sau cifruri de flux oferă numere mult mai „aleatoare”, astfel de generatoare sunt mult mai lente decât generatoarele aritmetice convenționale și pot să nu fie potrivite pentru orice fel de cercetare care necesită ca procesorul să fie liber pentru calcule mai utile.
În scopuri militare și în condiții de teren, sunt utilizate doar PRNG-uri puternice criptografice sincrone secrete (cifre de flux); cifrurile bloc nu sunt utilizate. Exemple de PRNG-uri cripto-puternice cunoscute sunt ISAAC, SEAL, Snow, algoritmul teoretic foarte lent al Bloom, Bloom și Shub, precum și contoare cu funcții hash criptografice sau cifruri bloc puternice în loc de o funcție de ieșire.
Hardware PRNG
În afară de moștenirea, binecunoscutele generatoare LFSR care au fost utilizate pe scară largă ca PRNG-uri hardware în secolul al XX-lea, din păcate, se cunosc foarte puține despre PRNG-urile hardware moderne (cifruri de flux), deoarece majoritatea dintre ele au fost dezvoltate în scopuri militare și sunt ținute secrete. . Aproape toate PRNG-urile hardware comerciale existente sunt brevetate și, de asemenea, păstrate secrete. PRNG-urile hardware sunt limitate de cerințe stricte pentru memoria consumabilă (cel mai adesea utilizarea memoriei este interzisă), viteza (1-2 cicluri de ceas) și suprafață (câteva sute de FPGA - sau
Din cauza lipsei unor PRNG-uri hardware bune, producătorii sunt forțați să folosească cifrurile bloc mult mai lente, dar binecunoscute, disponibile la îndemână (Computer Review No. 29 (2003)
Obținerea și conversia numerelor aleatorii.
Există două modalități principale de a obține numere aleatorii:
1) Numerele aleatoare sunt generate de un atașament electronic special (senzor de numere aleatoare) instalat pe computer. Implementarea acestei metode nu necesită aproape nicio operațiune suplimentară, în afară de accesarea senzorului de numere aleatorii.
2) Metoda algoritmică - bazată pe generarea de numere aleatoare în mașină în sine printr-un program special. Dezavantajul acestei metode este consumul suplimentar de timp de calculator, deoarece în acest caz mașina realizează operațiunile set-top box-ului electronic.
Un program pentru generarea de numere aleatoare folosind o lege de distribuție dată poate fi greoi. Prin urmare, numerele aleatoare cu o anumită lege de distribuție sunt de obicei obținute nu direct, ci prin transformarea numerelor aleatoare care au o distribuție standard. Adesea, această distribuție standard este distribuția uniformă (ușor de obținut și ușor de convertit la alte legi).
Cel mai avantajos este să obțineți numere aleatorii cu o lege uniformă folosind un set-top box electronic, care eliberează computerul de costurile suplimentare ale timpului de calculator. Obținerea unei distribuții pur uniforme pe un computer este imposibilă din cauza naturii limitate a grilei de biți. Prin urmare, în loc de un set continuu de numere pe intervalul (0, 1), este folosit un set discret de numere 2n numere, unde n– adâncimea de biți a cuvântului mașină.
Legea distribuției unei astfel de populații se numește cvasi-uniformă . La n³20, diferențele dintre legile uniforme și cvasi-uniforme devin nesemnificative.
Pentru a obține numere aleatoare cvasi-uniforme, se folosesc două metode:
1) generarea de numere aleatorii folosind un set-top box electronic prin modelarea unor procese aleatorii;
2) obținerea de numere pseudoaleatoare folosind algoritmi speciali.
Pentru obtinerea n-cifra număr aleator binar, prima metodă simulează o succesiune de variabile aleatoare independente z i, luând valoarea 0 sau 1. Secvența rezultată este 0 și 1, dacă o considerăm ca număr fracțional, și reprezintă o variabilă aleatorie de distribuție cvasi-uniformă pe intervalul (0, 1). Metodele hardware pentru obținerea acestor numere diferă doar prin modul în care obțin implementarea z i.
Una dintre metode se bazează pe numărarea numărului de particule radioactive pe o anumită perioadă de timp Dt, dacă numărul de particule este peste Dt chiar si atunci z i=1 , iar dacă este ciudat, atunci z i=0 .
O altă metodă utilizează efectul de zgomot al unui tub cu vid. Prin înregistrarea valorii tensiunii de zgomot în anumite momente în timp t i, obținem valorile variabilelor aleatoare independente U(t i), adică tensiune (volți).
Magnitudinea z i stabilit de lege:
Unde A– o anumită valoare a tensiunii de prag.
Magnitudinea A de obicei selectat din condiția:
Dezavantajul metodei hardware este că nu permite utilizarea metodei duble rulări pentru a controla funcționarea algoritmului pentru rezolvarea oricărei probleme, deoarece rulările repetate nu pot obține aceleași numere aleatorii.
Pseudoradom Ei apelează numerele generate pe un computer folosind programe speciale într-o manieră recurentă: fiecare număr aleator este obținut din cel anterior folosind transformări speciale.
Cea mai simplă dintre aceste transformări este următoarea. Să fie câteva n– număr binar de biți din interval nО (0, 1). Haideți-l și obținem 2n număr digital. Să evidențiem mediile n evacuări. Obținut în acest fel n– numărul cifrelor va fi noua valoare a numărului aleatoriu. O pătram din nou etc. Această secvență este pseudoaleatoare, deoarece din punct de vedere teoretic, nu este întâmplător.
Dezavantajul algoritmilor recurenți este că secvențele de numere aleatoare pot degenera (de exemplu, vom primi doar o secvență de zerouri sau o secvență de unu, sau poate apărea periodicitatea).
Rețineți că, în mod ideal, curba densității distribuției numerelor aleatoare ar arăta așa cum se arată în Fig. 22.3. Adică, în mod ideal, fiecare interval conține același număr de puncte: N i = N/k , Unde N numărul total de puncte, k numărul de intervale, i= 1, , k .
generat teoretic de un generator ideal
Trebuie amintit că generarea unui număr arbitrar aleatoriu constă în două etape:
- generarea unui număr aleator normalizat (adică distribuit uniform de la 0 la 1);
- conversie normalizată a numerelor aleatoare r i la numere aleatorii X i, care sunt distribuite conform legii de distribuție (arbitrară) cerută de utilizator sau în intervalul cerut.
Generatoarele de numere aleatorii conform metodei de obținere a numerelor sunt împărțite în:
- fizic;
- tabular;
- algoritmic.
RNG fizic
Un exemplu de RNG fizic poate fi: o monedă („capete” 1, „cozi” 0); zaruri; o tobă cu o săgeată împărțită în sectoare cu numere; generator de zgomot hardware (HS), care utilizează un dispozitiv termic zgomotos, de exemplu, un tranzistor (Fig. 22.422.5).
| Sarcina „Generarea numerelor aleatorii folosind o monedă” | |
|
Generați un număr aleatoriu de trei cifre, distribuit uniform în intervalul de la 0 la 1, folosind o monedă. Precizie trei zecimale. |
|
Prima modalitate de a rezolva problema
Desenați un interval de la 0 la 1. Citind numerele în succesiune de la stânga la dreapta, împărțiți intervalul în jumătate și alegeți de fiecare dată una dintre părțile intervalului următor (dacă obțineți 0, atunci cea din stânga, dacă obțineți un 1, apoi cel potrivit). Astfel, puteți ajunge în orice moment al intervalului, cu cât de precis doriți. Asa de, 1 : intervalul se împarte în jumătate și , se selectează jumătatea dreaptă, se îngustează intervalul: . Următorul număr 0 : intervalul se împarte în jumătate și , se selectează jumătatea stângă, se îngustează intervalul: . Următorul număr 0 : intervalul se împarte în jumătate și , se selectează jumătatea stângă, se îngustează intervalul: . Următorul număr 1 : intervalul se împarte în jumătate și , se selectează jumătatea dreaptă, se îngustează intervalul: . În funcție de condiția de acuratețe a problemei, s-a găsit o soluție: este orice număr din interval, de exemplu, 0,625. În principiu, dacă adoptăm o abordare strictă, atunci împărțirea intervalelor trebuie continuată până când limitele din stânga și dreapta ale intervalului găsit COINCIDEAZĂ cu o precizie a zecimalei a treia. Adică din punct de vedere al acurateței, numărul generat nu va mai fi distins de niciun număr din intervalul în care se află.
A doua modalitate de a rezolva problema
|
RNG tabelar
RNG-urile tabelare folosesc tabele special compilate care conțin numere verificate necorelate, adică în niciun fel dependente unele de altele, ca sursă de numere aleatorii. În tabel Figura 22.1 prezintă un mic fragment dintr-un astfel de tabel. Parcurgând tabelul de la stânga la dreapta de sus în jos, puteți obține numere aleatorii distribuite uniform de la 0 la 1 cu numărul necesar de zecimale (în exemplul nostru, folosim trei zecimale pentru fiecare număr). Deoarece numerele din tabel nu depind unele de altele, tabelul poate fi parcurs în diferite moduri, de exemplu, de sus în jos sau de la dreapta la stânga sau, să zicem, puteți selecta numere care sunt în poziții pare.
| Tabelul 22.1. Numere aleatorii. În mod egal numere aleatorii distribuite de la 0 la 1 |
||||||||||||||||||||||||||||||||||||||||||||
| Numere aleatorii | Distribuit uniform 0 la 1 numere aleatorii |
|||||||
| 9 | 2 | 9 | 2 | 0 | 4 | 2 | 6 | 0.929 |
| 9 | 5 | 7 | 3 | 4 | 9 | 0 | 3 | 0.204 |
| 5 | 9 | 1 | 6 | 6 | 5 | 7 | 6 | 0.269 |
Avantajul acestei metode este că produce numere cu adevărat aleatorii, deoarece tabelul conține numere necorelate verificate. Dezavantajele metodei: stocarea unui număr mare de cifre necesită multă memorie; Există mari dificultăți în generarea și verificarea acestui tip de tabele; repetările la utilizarea unui tabel nu mai garantează caracterul aleatoriu al secvenței numerice și, prin urmare, fiabilitatea rezultatului.
Există un tabel care conține 500 de numere verificate absolut aleatoare (preluate din cartea lui I. G. Venetsky, V. I. Venetskaya „Concepte și formule matematice și statistice de bază în analiza economică”).
RNG algoritmic
Numerele generate de aceste RNG-uri sunt întotdeauna pseudoaleatoare (sau cvasi-aleatoare), adică fiecare număr generat ulterior depinde de cel anterior:
r i + 1 = f(r i) .
Secvențele formate din astfel de numere formează bucle, adică există în mod necesar un ciclu care se repetă de un număr infinit de ori. Ciclurile repetate se numesc perioade.
Avantajul acestor RNG-uri este viteza lor; generatoarele nu necesită practic resurse de memorie și sunt compacte. Dezavantaje: numerele nu pot fi numite pe deplin aleatoare, deoarece există o dependență între ele, precum și prezența unor perioade în succesiunea numerelor cvasialeatoare.
Să luăm în considerare câteva metode algoritmice pentru obținerea RNG:
- metoda pătratelor mediane;
- metoda produselor de mijloc;
- metoda de agitare;
- metoda liniară congruentă.
Metoda mijlocului pătratului
Există un număr din patru cifre R 0 . Acest număr este pătrat și introdus în R 1 . În continuare de la R 1 ia noul număr aleatoriu din mijloc (patru cifre din mijloc) și îl scrie R 0 . Apoi procedura se repetă (vezi Fig. 22.6). Rețineți că, de fapt, ca număr aleatoriu, trebuie să luați nu ghij, A 0.ghij cu un zero și un punct zecimal adăugat la stânga. Acest fapt este reflectat ca în fig. 22.6, și în cifre similare ulterioare.
 |
Dezavantajele metodei: 1) dacă la o iterație numărul R 0 devine egal cu zero, apoi generatorul degenerează, deci alegerea corectă a valorii inițiale este importantă R 0; 2) generatorul va repeta secvența prin M n pași (în cel mai bun caz), unde n cifra numerică R 0 , M baza sistemului numeric.
De exemplu în Fig. 22.6: dacă numărul R 0 va fi reprezentat în sistemul de numere binar, apoi succesiunea de numere pseudoaleatoare se va repeta în 2 4 = 16 pași. Rețineți că repetarea secvenței poate avea loc mai devreme dacă numărul de pornire este ales prost.
Metoda descrisă mai sus a fost propusă de John von Neumann și datează din 1946. Deoarece această metodă s-a dovedit a fi nesigură, a fost rapid abandonată.
Metoda produsului mediu
Număr R 0 înmulțit cu R 1, din rezultatul obținut R 2 se extrage mijlocul R 2 * (acesta este un alt număr aleatoriu) și înmulțit cu R 1 . Toate numerele aleatoare ulterioare sunt calculate folosind această schemă (vezi Fig. 22.7).
 |
Metoda de agitare
Metoda shuffle folosește operații pentru a muta ciclic conținutul unei celule la stânga și la dreapta. Ideea metodei este următoarea. Lăsați celula să stocheze numărul inițial R 0 . Deplasând ciclic conținutul celulei la stânga cu 1/4 din lungimea celulei, obținem un număr nou R 0 * . În același mod, ciclând conținutul celulei R 0 la dreapta cu 1/4 din lungimea celulei, obținem al doilea număr R 0**. Suma numerelor R 0* și R 0** oferă un nou număr aleatoriu R 1 . Mai departe R 1 este introdus în R 0 și se repetă întreaga secvență de operații (vezi Fig. 22.8).
 |
Vă rugăm să rețineți că numărul rezultat din însumare R 0* și R 0 ** , este posibil să nu se încadreze complet în celulă R 1 . În acest caz, cifrele suplimentare trebuie eliminate din numărul rezultat. Să explicăm acest lucru în fig. 22.8, unde toate celulele sunt reprezentate de opt cifre binare. Lăsa R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Apoi R 0 * + R 0 ** = 100110010 2 = 306 10 . După cum puteți vedea, numărul 306 ocupă 9 cifre (în sistemul de numere binar), iar celula R 1 (la fel ca R 0) poate conține maximum 8 biți. Prin urmare, înainte de a introduce valoarea în R 1, este necesar să eliminați un bit „în plus”, cel mai din stânga din numărul 306, rezultând R 1 nu va mai merge la 306, ci la 00110010 2 = 50 10 . De asemenea, rețineți că în limbi precum Pascal, „tuierea” biților suplimentari atunci când o celulă depășește este efectuată automat, în conformitate cu tipul specificat de variabilă.
Metoda liniară congruentă
Metoda liniară congruentă este una dintre cele mai simple și mai frecvent utilizate proceduri care simulează în prezent numere aleatoare. Această metodă folosește modul( X, y) , care returnează restul când primul argument este împărțit la al doilea. Fiecare număr aleatoriu ulterior este calculat pe baza numărului aleatoriu anterior folosind următoarea formulă:
r i+ 1 = mod( k · r i + b, M) .
Se numește șirul numerelor aleatoare obținute folosind această formulă succesiune liniară congruentă. Mulți autori numesc o secvență liniară congruentă când b = 0 metoda multiplicativă congruentă, și atunci când b ≠ 0 metoda mixta congruenta.
Pentru un generator de înaltă calitate, este necesar să selectați coeficienți potriviți. Este necesar ca numărul M a fost destul de mare, deoarece perioada nu poate avea mai mult M elemente. Pe de altă parte, împărțirea folosită în această metodă este o operație destul de lentă, deci pentru un computer binar alegerea logică ar fi M = 2 N, deoarece în acest caz, găsirea restului diviziunii este redusă în interiorul computerului la operația logică binară „ȘI”. Alegerea celui mai mare număr prim este de asemenea comună M, mai puțin de 2 N: în literatura de specialitate este dovedit că în acest caz cifrele de ordin inferior ale numărului aleator rezultat r i+ 1 se comportă la fel de aleatoriu ca și cei mai vechi, ceea ce are un efect pozitiv asupra întregii secvențe de numere aleatoare în ansamblu. De exemplu, unul dintre numerele Mersenne, egal cu 2 31 1 și astfel, M= 2 31 1 .
Una dintre cerințele pentru secvențele liniare congruente este ca lungimea perioadei să fie cât mai lungă posibil. Durata perioadei depinde de valori M , kȘi b. Teorema pe care o prezentăm mai jos ne permite să determinăm dacă este posibil să realizăm o perioadă de lungime maximă pentru anumite valori M , kȘi b .
Teorema. Secvență liniară congruentă definită prin numere M , k , bȘi r 0, are o perioadă de lungime M dacă și numai dacă:
- numere bȘi M relativ simplu;
- k de 1 ori p pentru fiecare prim p, care este un divizor M ;
- k 1 este un multiplu al lui 4, dacă M multiplu de 4.
În cele din urmă, să încheiem cu câteva exemple de utilizare a metodei congruente liniare pentru a genera numere aleatorii.
S-a stabilit că o serie de numere pseudoaleatoare generate pe baza datelor din exemplul 1 vor fi repetate la fiecare M/4 numere. Număr q este setat arbitrar înainte de începerea calculelor, totuși, trebuie avut în vedere că seria dă impresia că este aleatorie în general k(prin urmare q). Rezultatul poate fi îmbunătățit oarecum dacă b ciudat și k= 1 + 4 · q în acest caz rândul se va repeta la fiecare M numere. După o lungă căutare k cercetătorii s-au stabilit pe valori de 69069 și 71365.
Un generator de numere aleatorii care utilizează datele din Exemplul 2 va produce numere aleatorii, nerepetate, cu o perioadă de 7 milioane.
Metoda multiplicativă pentru generarea numerelor pseudoaleatoare a fost propusă de D. H. Lehmer în 1949.
Verificarea calitatii generatorului
Calitatea întregului sistem și acuratețea rezultatelor depind de calitatea RNG. Prin urmare, secvența aleatoare generată de RNG trebuie să îndeplinească o serie de criterii.
Verificările efectuate sunt de două tipuri:
- verificări pentru uniformitatea distribuției;
- teste pentru independența statistică.
Verificări pentru uniformitatea distribuției
1) RNG ar trebui să producă aproape următoarele valori ale parametrilor statistici caracteristici unei legi aleatorii uniforme:
2) Test de frecventa
Un test de frecvență vă permite să aflați câte numere se încadrează într-un interval (m r σ r ; m r + σ r) , adică (0,5 0,2887; 0,5 + 0,2887) sau, în cele din urmă, (0,2113; 0,7887). Deoarece 0,7887 0,2113 = 0,5774, ajungem la concluzia că într-un RNG bun, aproximativ 57,7% din toate numerele aleatorii extrase ar trebui să se încadreze în acest interval (vezi Fig. 22.9).
în cazul verificării acestuia pentru testul de frecvență
De asemenea, este necesar să se țină seama de faptul că numărul de numere care se încadrează în interval (0; 0,5) ar trebui să fie aproximativ egal cu numărul de numere care se încadrează în interval (0,5; 1).
3) Testul chi-pătrat
Testul chi-pătrat (testul χ 2) este unul dintre cele mai cunoscute teste statistice; este metoda principală folosită în combinaţie cu alte criterii. Testul chi-pătrat a fost propus în 1900 de Karl Pearson. Lucrarea sa remarcabilă este considerată ca fundament al statisticii matematice moderne.
Pentru cazul nostru, testarea folosind criteriul chi-pătrat ne va permite să aflăm cât de mult este real RNG-ul este aproape de benchmark-ul RNG, adică dacă îndeplinește sau nu cerințele de distribuție uniformă.
Diagrama de frecventa referinţă RNG este prezentat în Fig. 22.10. Deoarece legea de distribuție a RNG de referință este uniformă, atunci probabilitatea (teoretică). p i introducerea numerelor în i al-lea interval (toate aceste intervale k) este egal cu p i = 1/k . Și astfel, în fiecare dintre k intervalele vor lovi neted De p i · N numere ( N numărul total de numere generate).
Un RNG real va produce numere distribuite (și nu neapărat uniform!) peste tot k intervale și fiecare interval va conține n i numere (în total n 1 + n 2 + + n k = N ). Cum putem determina cât de bun este RNG-ul testat și cât de aproape este de cel de referință? Este destul de logic să luăm în considerare diferențele pătrate dintre numărul rezultat de numere n iși „referință” p i · N . Să le adunăm și rezultatul este:
χ 2 exp. = ( n 1 p 1 · N) 2 + (n 2 p 2 · N) 2 + + ( n k p k · N) 2 .
Din această formulă rezultă că, cu cât diferența dintre fiecare dintre termeni este mai mică (și deci valoarea lui χ 2 exp. mai mică), cu atât legea distribuției numerelor aleatoare generate de un RNG real tinde să fie uniformă mai puternică.
În expresia anterioară, fiecăruia dintre termeni i se atribuie aceeași pondere (egal cu 1), ceea ce de fapt poate să nu fie adevărat; prin urmare, pentru statisticile chi-pătrat, este necesar să se normalizeze fiecare i al-lea termen, împărțindu-l la p i · N :
În cele din urmă, să scriem expresia rezultată mai compact și să o simplificăm:
Am obținut valoarea testului chi-pătrat pentru experimental date.
În tabel 22.2 sunt date teoretic valori chi-pătrat (χ 2 teoretic), unde ν = N 1 este numărul de grade de libertate, p acesta este un nivel de încredere specificat de utilizator care indică cât de mult ar trebui să satisfacă RNG cerințele unei distribuții uniforme sau p este probabilitatea ca valoarea experimentală a lui χ 2 exp. va fi mai mică decât cea tabulată (teoretică) χ 2 teoretică. sau egal cu acesta.
| Tabelul 22.2. Câteva puncte procentuale ale distribuției χ 2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| p = 1% | p = 5% | p = 25% | p = 50% | p = 75% | p = 95% | p = 99% | |
| ν = 1 | 0.00016 | 0.00393 | 0.1015 | 0.4549 | 1.323 | 3.841 | 6.635 |
| ν = 2 | 0.02010 | 0.1026 | 0.5754 | 1.386 | 2.773 | 5.991 | 9.210 |
| ν = 3 | 0.1148 | 0.3518 | 1.213 | 2.366 | 4.108 | 7.815 | 11.34 |
| ν = 4 | 0.2971 | 0.7107 | 1.923 | 3.357 | 5.385 | 9.488 | 13.28 |
| ν = 5 | 0.5543 | 1.1455 | 2.675 | 4.351 | 6.626 | 11.07 | 15.09 |
| ν = 6 | 0.8721 | 1.635 | 3.455 | 5.348 | 7.841 | 12.59 | 16.81 |
| ν = 7 | 1.239 | 2.167 | 4.255 | 6.346 | 9.037 | 14.07 | 18.48 |
| ν = 8 | 1.646 | 2.733 | 5.071 | 7.344 | 10.22 | 15.51 | 20.09 |
| ν = 9 | 2.088 | 3.325 | 5.899 | 8.343 | 11.39 | 16.92 | 21.67 |
| ν = 10 | 2.558 | 3.940 | 6.737 | 9.342 | 12.55 | 18.31 | 23.21 |
| ν = 11 | 3.053 | 4.575 | 7.584 | 10.34 | 13.70 | 19.68 | 24.72 |
| ν = 12 | 3.571 | 5.226 | 8.438 | 11.34 | 14.85 | 21.03 | 26.22 |
| ν = 15 | 5.229 | 7.261 | 11.04 | 14.34 | 18.25 | 25.00 | 30.58 |
| ν = 20 | 8.260 | 10.85 | 15.45 | 19.34 | 23.83 | 31.41 | 37.57 |
| ν = 30 | 14.95 | 18.49 | 24.48 | 29.34 | 34.80 | 43.77 | 50.89 |
| ν = 50 | 29.71 | 34.76 | 42.94 | 49.33 | 56.33 | 67.50 | 76.15 |
| ν > 30 | ν + sqrt(2 ν ) · X p+ 2/3 · X 2 p 2/3 + O(1/sqrt( ν )) | ||||||
| X p = | 2.33 | 1,64 | 0,674 | 0.00 | 0.674 | 1.64 | 2.33 |
Considerat acceptabil p de la 10% la 90%.
Dacă χ 2 exp. mult mai mult decât teoria χ 2. (acesta este p este mare), apoi generatorul nu satisface cerința distribuției uniforme, deoarece valorile observate n i mergi prea departe de teoretic p i · N și nu poate fi considerată aleatorie. Cu alte cuvinte, se stabilește un interval de încredere atât de mare încât restricțiile asupra numerelor devin foarte laxe, cerințele privind numerele devin slabe. În acest caz, se va observa o eroare absolută foarte mare.
Chiar și D. Knuth în cartea sa „The Art of Programming” a remarcat că având χ 2 exp. pentru cei mici, în general, nici nu este bine, deși acest lucru pare, la prima vedere, a fi minunat din punct de vedere al uniformității. Într-adevăr, luați o serie de numere 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, sunt ideale din punct de vedere al uniformității și χ 2 exp. va fi practic zero, dar este puțin probabil să le recunoașteți ca aleatoare.
Dacă χ 2 exp. mult mai mică decât teoria χ 2. (acesta este p mic), apoi generatorul nu satisface cerința unei distribuții uniforme aleatorii, din moment ce valorile observate n i prea aproape de teoretic p i · N și nu poate fi considerată aleatorie.
Dar dacă χ 2 exp. se află într-un anumit interval între două valori ale χ 2 teor. , care corespund, de exemplu, p= 25% și p= 50%, atunci putem presupune că valorile numărului aleator generate de senzor sunt complet aleatorii.
În plus, trebuie avut în vedere faptul că toate valorile p i · N trebuie să fie suficient de mare, de exemplu mai mult de 5 (aflat empiric). Abia atunci (cu un eșantion statistic suficient de mare) condițiile experimentale pot fi considerate satisfăcătoare.
Deci, procedura de verificare este următoarea.
Teste pentru independența statistică
1) Verificarea frecvenței de apariție a numerelor în succesiune
Să ne uităm la un exemplu. Numărul aleatoriu 0,2463389991 este format din cifrele 2463389991, iar numărul 0,5467766618 este format din cifrele 5467766618. Conectând secvențele de cifre, avem: 24633889991646.
Este clar că probabilitatea teoretică p i pierderi i A treia cifră (de la 0 la 9) este egală cu 0,1.
2) Verificarea aspectului serii de numere identice
Să notăm prin n L numărul de serii de cifre identice într-un rând de lungime L. Totul trebuie verificat L de la 1 la m, Unde m acesta este un număr specificat de utilizator: numărul maxim de cifre identice care apar într-o serie.
În exemplul „24633899915467766618” au fost găsite 2 serii de lungime 2 (33 și 77), adică n 2 = 2 și 2 serii de lungime 3 (999 și 666), adică n 3 = 2 .
Probabilitatea de apariție a unei serii de lungime L este egal cu: p L= 9 10 L (teoretic). Adică, probabilitatea de apariție a unei serii cu lungimea de un caracter este egală cu: p 1 = 0,9 (teoretic). Probabilitatea ca o serie de două personaje să apară este: p 2 = 0,09 (teoretic). Probabilitatea ca o serie de trei personaje să apară este: p 3 = 0,009 (teoretic).
De exemplu, probabilitatea de apariție a unei serii cu lungimea de un caracter este p L= 0,9, deoarece poate exista un singur simbol din 10 și există 9 simboluri în total (zero nu contează). Și probabilitatea ca două simboluri identice „XX” să apară pe rând este 0,1 · 0,1 · 9, adică probabilitatea de 0,1 ca simbolul „X” să apară în prima poziție este înmulțită cu probabilitatea de 0,1 ca același simbol va apărea în a doua poziție „X” și înmulțit cu numărul de astfel de combinații 9.
Frecvența de apariție a seriei este calculată folosind formula chi-pătrat pe care am discutat anterior folosind valorile p L .
Notă: Generatorul poate fi testat de mai multe ori, dar testele nu sunt complete și nu garantează că generatorul produce numere aleatorii. De exemplu, un generator care produce secvența 12345678912345 va fi considerat ideal în timpul testelor, ceea ce, evident, nu este în întregime adevărat.
În concluzie, observăm că al treilea capitol al cărții lui Donald E. Knuth The Art of Programming (Volumul 2) este în întregime dedicat studiului numerelor aleatoare. Acesta examinează diferite metode de generare a numerelor aleatorii, teste statistice de aleatorie și conversia numerelor aleatoare distribuite uniform în alte tipuri de variabile aleatoare. Peste două sute de pagini sunt dedicate prezentării acestui material.
