Generator de numere aleatorii pentru o anumită sumă. Generator de numere aleatorii online
Foarte des, atunci când se dezvoltă programe, este nevoie de consecvență numere aleatorii. În jocuri, o secvență de numere aleatoare poate fi folosită într-o varietate de situații: crearea de monștri, generarea de teritoriu, comportamentul inteligenței artificiale.
Multe lucruri se pot face fără un generator de numere aleatorii. De exemplu, o astfel de succesiune de numere nu poate fi considerată aleatorie: (0, 1, 2, 3, 4, 5, 6, 7). Aici, cunoscând numărul precedent, este foarte ușor să-l ghiciți pe următorul. Există și alte secvențe. De exemplu: (0, 1, 3, 2, 6, 7, 5, 4). Aici, a ghici următorul număr este mult mai dificil. Astfel de secvențe sunt uneori convenabile de utilizat în programe. Această secvență determinat de codul Gray. La prima inspecție, se pare că aici sunt prezentate numere aleatorii.
În loc să folosiți secvențe de numere în programe care respectă o anumită lege, în multe cazuri este mai bine să folosiți cele generate aleatoriu.
Generaţie numere pseudoaleatoare
Generarea numerelor pseudoaleatoare este folosită în mod obișnuit. Acestea. Numerele nu sunt în întregime aleatorii. Ne-am uitat deja la funcția rand(). Dacă scrieți un program care folosește această funcție, apoi de fiecare dată când rulați programul, rand() va genera aceeași secvență de numere. Secvența generată de rand() este determinată de sămânță. Mai întâi se stabilește numărul de pornire, apoi, conform o anumită formulă Toate celelalte numere din succesiune sunt calculate. Cunoscând numărul de început și formula prin care se calculează numerele, puteți calcula următorul număr.
Astfel de algoritmi sunt numiți determiniști (predeterminați). Acestea. în ele, se creează o secvență de numere pe baza datelor inițiale. În acest caz, succesiunea de numere este pseudo-aleatorie: i.e. Cunoscând numărul de început, le puteți afla pe toate următoarele. Dar este puțin probabil ca utilizatorul să le recunoască, numerele vor părea aleatorii.
Unul dintre algoritmii predefiniti (determiniști) pentru generarea numerelor aleatoare este congruent liniar.
Setarea valorii inițiale (pentru funcția rand() pe care am folosit-o până acum) arată cam așa:
cod C++ int i; cin >> i; srnd(i); // stabilirea valorii inițiale rand();
Funcția srnd stabilește valoarea inițială a lui i.
Metoda de generare a numerelor aleatoare congruențiale liniare
Există multe metode pentru a genera numere aleatorii. Liniar congruent este doar unul dintre ele. Metoda este destul de veche - anii 1950. A fost proiectat de Derrick Lemaire.
Pentru a implementa algoritmul, trebuie să setați patru parametri:
Interval de valori m, cu m > 0.
Multiplicatorul a (0<= a <= m).
Creșterea valorii c (0<= c <= m).
Valoarea inițială X0 (0<= X0 < m).
După ce ați determinat acești parametri, puteți utiliza formula:
Xi+1 = (aXi + c) % m (unde i este mai mare sau egal cu 0)
i este numărul elementului din succesiune.
m - numărul de valori din care se formează secvența.
Permiteți-mi să vă reamintesc că % este restul diviziunii.
Să ne uităm la un exemplu de secvență mică. Luați o bucată de hârtie, un creion și calculați toate valorile:
imax = 5; // formează o succesiune de 5 elemente
m = 10; // valorile din secvența variază de la zero la 9
a = 2;
c = 3;
X0 = 6; // valoarea inițială (sămânță)
Xi+1 = (2*Xi + 3) % 10 (unde i este mai mare sau egal cu 0)
X1 = 15% 10 = 5
X2 = 13% 10 = 3
X3 = 9% 10 = 9
X4 = 21% 10 = 1
X5 = 5% 10 = 5
Dacă creștem secvența, valorile vor începe să se repete. Astfel, mai multe valori care nu se repetă într-o secvență formează o perioadă. Perioada din acest exemplu este ( 5, 3, 9, 1 ).
Deci, folosind metoda liniară congruentă, am obținut o succesiune de numere aleatorii de cinci elemente.
Pentru a prezice valorile elementelor dintr-o secvență, puteți utiliza formula:
Xi+k = (a*k*Xi + (a*k-1)*c/b) % m (unde k și i sunt mai mari sau egali cu 0)
Aici b = a - 1. Mai mult, a >= 2, b >= 1.
Să calculăm al șaselea element folosind această formulă (pe al cincilea îl știm deja):
X5+1 = (a*1*X5 + (a*1-1)*c/b) % m = (2*1*5 + (2*1-1)*3/1) % 10 = 13 % 10 = 3
Totul crește, nu?
O secvență creată folosind metoda congruentă liniară și definită de parametrii întregi m, a, c și X0 are o perioadă egală cu numărul m atunci când sunt îndeplinite următoarele condiții:
1. Cel mai mare divizor comun al lui c și m este 1.
2.b este un multiplu al oricărui număr prim care este divizor al lui m.
3. Dacă m este un multiplu al lui 4, atunci b este, de asemenea, un multiplu al lui 4.
Alegere m
Perioada nu poate fi mai mare decât numărul m. Prin urmare, m trebuie să fie destul de mare.
Cel mai bine ar fi dacă m ar fi egal cu elementul maxim din secvența imax+1 (adăugăm unul, deoarece i se numără de la zero). O altă alegere populară este puterea a doi 2n. Cu condiția ca n să fie lungimea cuvântului mașină în biți, puteți scăpa de operația rămasă. Dacă m este o putere de doi, atunci operațiunea rămasă poate fi înlocuită cu operația mai rapidă AND pe biți (deși acest lucru nu este relevant pentru computerele moderne):
x % 2n == x & (2n - 1)
Exemple (x este un număr întreg):
x % 2 == x & 1;
x % 4 == x & 3;
x % 8 == x & 7;
Foarte des se alege unul dintre primii Mersenne pentru m. Adesea, numărul 231 - 1 este folosit atunci când calculele sunt efectuate cu date pe 32 de biți.
Multiplicator a
Multiplicatorul trebuie ales astfel încât perioada să fie cât mai lungă. Există o problemă serioasă cu acest coeficient: pentru valori mici ale lui a, dacă elementul curent al secvenței este suficient de mic, este probabil ca și următorul element să fie mic.
Creștere c
Acest parametru poate fi ales destul de arbitrar. Foarte des este setat la zero, dar aceasta reduce lungimea perioadei și X0 != 0.
Valoarea inițială (sămânță)
Deci, am aflat că există o perioadă în secvență. În exemplul nostru, perioada este egală cu doar patru elemente. În alte cazuri, perioada poate fi foarte lungă, dar este mereu acolo! Adică, atunci când generăm numere aleatoare folosind metoda congruentă liniară, dacă avem nevoie de o secvență foarte mare, atunci valorile din aceasta se vor repeta cu o anumită periodicitate.
Pur si simplu! Generarea de numere consecutive este o adevărată păcăleală!
Acestea. Să presupunem că avem un generator de numere aleatorii. Îl folosim pentru diferite programe. Întotdeauna, întotdeauna acest generator creează aceeași succesiune de numere (cu aceleași valori inițiale). Putem seta doar valoarea inițială.
În general, folosind metode aritmetice este imposibil să construiești o secvență de numere cu adevărat aleatorie. Cât de trist a glumit prietenul nostru John Von Neumann:
„Oricine folosește metode aritmetice pentru a produce numere aleatorii este într-o stare de păcat”. (C) John Von Neumann.
Totul este trist. Așa trăiești și trăiești. Fiind într-o stare de ignoranță, te gândești: „Dar ar fi grozav să creezi un generator de numere aleatorii bazat pe metoda liniară conștientă!” Dar se dovedește că o secvență cu adevărat aleatorie nu poate fi creată în acest fel. Prăbușirea speranțelor! Depresie și acum ești deja în pragul primei etape a alcoolismului. Această povară a incapacității de a-ți realiza dorințele te va apăsa pentru tot restul vieții... M-am distras. Hai sa continuăm.
Implementarea generării numerelor aleatoare
Acum că ne-am uitat la problemele teoretice referitoare la generatoarele de numere aleatoare, să ne uităm la implementare, mai ales că este destul de simplă.
Pentru secvența discutată mai sus, generatorul va arăta astfel:
cod în limbajul C++ int rnd() ( int m = 10, a = 2, c = 3; static int x = x0; // x este declarată ca o variabilă statică x = ((a * x) + c) % m; // formulă x0 = x ;
X0 este declarat ca o variabilă globală:
int x0 = 6;
Aceasta este cea mai primitivă versiune a generatorului. În realitate, un astfel de monstru nu poate fi folosit! Dar o vom face!
În această implementare, nu monitorizăm în niciun fel posibilitatea de depășire variabilă. În loc de tipul int, utilizați tipul _int64 - acesta este un tip întreg de opt octeți.
numere prime
Numerele prime sunt numere care pot fi împărțite fără rest doar la unul și numărul însuși. De exemplu: 11, 3, 7.
Cod gri
Codul gri este o succesiune de numere în care următorul număr diferă de cel precedent cu un bit. Acestea. pentru a ghici secvența, trebuie să te uiți nu la numerele zecimale, ci la echivalentele lor binare.
Iată o succesiune crescătoare de numere de la 0 la 7 în cod binar:
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7
Folosind codul lui Gray, obținem următoarea secvență:
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
numere prime de Mersenne
În acest moment, este cunoscut al 44-lea număr Mersenne. Din nume este clar că aceste numere sunt prime, adică. sunt divizibile doar între unul și ei înșiși. În plus, aceste numere trebuie să respecte următoarea formulă:
Unde n este de asemenea un număr prim. Pentru primele nouă numere prime Mersenne, n sunt: (2, 3, 5, 7, 13, 17, 19, 31, 61).
Operații logice pe biți
Ne-am uitat deja la operatorii logici && (ȘI) și || (SAU). Există, de asemenea, operatori logici pe biți & (ȘI pe biți) și | (SAU pe biți). Lucrați operația după cum urmează:
5 && 3; // && returnează întotdeauna zero sau unu (aici 1)
5&3; // & returnează un număr
101
011
=
001 // rezultatul este unul
Adică, în această operație se compară pozițiile corespunzătoare a două numere și dacă sunt egale, atunci se scrie 1 în numărul rezultat în această poziție, în caz contrar zero.
5 | 3; // | returnează un număr
101
011
=
111 // rezultând 7
Gradul de
Pentru a ridica un număr la orice putere, puteți folosi funcția pow(x,y). În acest caz veți primi xy. Funcția este supraîncărcată, deci poate fi folosită cu diferite tipuri. Pentru a utiliza funcția pow(), trebuie să includeți fișierul antet math.h.
Alți generatori de numere aleatorii
Pe lângă generatorul liniar congruent, există multe altele. De exemplu, Vortexul Mersenne, inventat de doi oameni de știință japonezi (nu-mi amintesc numele lor) în 1997. Are o perioadă foarte lungă (foarte lungă, pentru a spune ușor). Apropo, vortexul Mersenne folosește un generator liniar congruent pentru a seta sămânța.
Generatoarele de numere aleatorii sunt utilizate în criptare. Dar aici se folosesc generatoare speciale - generatoare de numere pseudoaleatoare securizate criptografic. De exemplu, un cifr de bloc, un cifr de flux, care a fost dezvoltat pe baza cifrului Vernam.
Exerciții:
Implementați generatoare de numere aleatorii bazate pe metoda cogruentă liniară. Utilizați următorii parametri:
m = 232; a = 1664525; c = 1013904223. Acești parametri au fost utilizați în exemplul de implementare a generatorului într-o carte veche Fortran.
m = 232; a = 214013; c = 2531011; Acești parametri sunt utilizați în implementarea metodei în Visual C++. În acest caz, sunt luați cei mai semnificativi biți 30..16. Sunt biți de sus care sunt luate, pentru că în metoda liniară congruentă, biții inferiori sunt mult mai puțin aleatori. Deoarece nu știm încă cum să luăm anumite biți, puteți folosi întregul număr.
Pentru m, alegeți unul dintre numerele Mersenne. Începeți mic (23-1.25-1). Încercați să înlocuiți 231-1 și 261-1.
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ă apare 0, atunci cea din stânga, dacă este 1). apare, apoi cea 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. uniform 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 atunci când se folosește un 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 cvasialeatoare), 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 midsquare
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 cifre numerice 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 numerelor pseudoaleatoare se va repeta în 2 4 = 16 pași. Rețineți că repetarea secvenței poate apărea 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 nou număr 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 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ă, în concluzie, să ne uităm la 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 aleatorie 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 aleatoare 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, un test folosind criteriul chi-pătrat ne va permite să aflăm cât am creat 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 (totalul acestor 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 cu cât valoarea lui χ 2 exp. mai mică), cu atât legea distribuției numerelor aleatoare generate de un RNG real tinde să fie 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 χ 2 teoretic tabelat (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 merge 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. În general, nici pentru cei mici nu este bine, deși la prima vedere acest lucru pare 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, acestea 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, deoarece 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 numerelor aleatoare 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 este de un caracter p L= 0,9, deoarece poate exista doar un simbol din 10 și există 9 simboluri în total (zero nu contează). Și probabilitatea ca două simboluri identice „XX” să apară într-un rând este de 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 aleatoare, 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.
Vă rugăm să ajutați serviciul cu un singur clic: Spune-le prietenilor tăi despre generator!
Generator de numere online cu 1 clic
Generatorul de numere aleatorii, care este prezentat pe site-ul nostru web, este foarte convenabil. De exemplu, poate fi folosit la loterie și la loterie pentru a determina câștigătorul. Câștigătorii sunt determinați în acest fel: programul produce unul sau mai multe numere în orice interval specificat de dvs. Rezultatele frauduloase pot fi imediat excluse. Și datorită acestui fapt, câștigătorul este determinat de o alegere sinceră.
Uneori este necesar să obțineți un anumit număr de numere aleatorii deodată. De exemplu, doriți să completați un bilet de loterie „4 din 35”, având încredere în voia întâmplării. Puteți verifica: dacă aruncați o monedă de 32 de ori, care este probabilitatea ca 10 reversuri să apară la rând (capetelor/cozii pot fi atribuite foarte bine numerele 0 și 1)?
Instrucțiuni video online cu numere aleatorii - randomizare
Generatorul nostru de numere este foarte ușor de utilizat. Nu necesită descărcarea unui program pe computer - poate fi folosit online. Pentru a obține numărul de care aveți nevoie, trebuie să setați intervalul de numere aleatorii, cantitatea și, dacă doriți, separatorul de numere și să eliminați repetările.
Pentru a genera numere aleatorii într-un interval de frecvență specific:
- Selectați un interval;
- Specificați numărul de numere aleatoare;
- Funcția „Separator de numere” servește pentru frumusețea și comoditatea afișajului lor;
- Dacă este necesar, activați/dezactivați repetările folosind caseta de selectare;
- Faceți clic pe butonul „Generați”.
Ca rezultat, veți primi numere aleatorii într-un interval dat. Rezultatul generatorului de numere poate fi copiat sau trimis prin e-mail. Cel mai bine ar fi să faceți o captură de ecran sau un videoclip al acestui proces de generare. Randomizorul nostru vă va rezolva orice problemă!
Generatorul de numere aleatoare online prezentat funcționează pe baza unui generator de numere pseudo-aleatoare cu o distribuție uniformă încorporată în JavaScript. Sunt generate numere întregi. În mod implicit, sunt afișate 10 numere aleatorii în intervalul 100...999, numere separate prin spații.
Setări de bază ale generatorului de numere aleatorii:
- Cantitatea de numere
- Interval de numere
- Tip separator
- Activați/dezactivați funcția de eliminare a repetărilor (duplicate de numere)
Numărul total este limitat oficial la 1000, cu maximum 1 miliard. Opțiuni de delimitare: spațiu, virgulă, punct și virgulă.
Acum știți exact unde și cum să obțineți o secvență gratuită de numere aleatorii într-un interval dat de pe Internet.
Opțiuni de aplicație pentru un generator de numere aleatorii
Un generator de numere aleatorii (RNG în JS cu distribuție uniformă) va fi util pentru specialiștii SMM și proprietarii de grupuri și comunități de pe rețelele sociale Instagram, Facebook, VKontakte, Odnoklassniki pentru a determina câștigătorii loteriei, competițiilor și extragerii cu premii.
Un generator de numere aleatorii vă permite să trageți premii între un număr arbitrar de participanți cu un anumit număr de câștigători. Concursurile pot fi organizate fără repostări și comentarii - dvs. setați singur numărul de participanți și intervalul de generare a numerelor aleatorii. Puteți obține un set de numere aleatorii online și gratuit pe acest site și nu este nevoie să instalați nicio aplicație pe smartphone sau program de pe computer.
De asemenea, un generator de numere aleatoare online poate fi folosit pentru a simula aruncarea unei monede sau a zarurilor. Cu toate acestea, avem servicii specializate separate pentru aceste cazuri.
