De software van bijna alle computers heeft een ingebouwde functie voor het genereren van een reeks pseudo-willekeurige quasi-uniform verdeelde getallen. Voor statistische modellering worden echter hogere eisen gesteld aan het genereren van willekeurige getallen. De kwaliteit van de resultaten van dergelijke modellering hangt rechtstreeks af van de kwaliteit van de generator van uniform verdeelde willekeurige getallen, omdat deze getallen zijn ook bronnen (begingegevens) voor het verkrijgen van andere willekeurige variabelen met een bepaalde verdelingswet.
Helaas bestaan er geen ideale generatoren en wordt de lijst met hun bekende eigenschappen aangevuld met een lijst met nadelen. Dit leidt tot het risico dat u een slechte generator gebruikt in een computerexperiment. Daarom is het, voordat een computerexperiment wordt uitgevoerd, noodzakelijk om ofwel de kwaliteit van de in de computer ingebouwde functie voor het genereren van willekeurige getallen te evalueren, ofwel een geschikt algoritme voor het genereren van willekeurige getallen te selecteren.
Om in de computationele fysica te kunnen worden gebruikt, moet de generator de volgende eigenschappen hebben:
De rekenefficiëntie is de kortst mogelijke rekentijd voor de volgende cyclus en de hoeveelheid geheugen voor het laten draaien van de generator.
Grote lengte L willekeurige reeks getallen. Deze periode moet ten minste de reeks willekeurige getallen omvatten die nodig zijn voor een statistisch experiment. Bovendien vormt zelfs het naderen van het einde van L een gevaar, wat kan leiden tot onjuiste resultaten van een statistisch experiment.
Het criterium voor een voldoende lengte van een pseudowillekeurige reeks wordt gekozen uit de volgende overwegingen. De Monte Carlo-methode bestaat uit herhaalde berekeningen van de uitvoerparameters van een gesimuleerd systeem onder invloed van invoerparameters die fluctueren met gegeven distributiewetten. De basis voor het implementeren van de methode is het genereren van willekeurige getallen met uniform verdeling in het interval waaruit willekeurige getallen met bepaalde verdelingswetten worden gevormd. Vervolgens wordt de waarschijnlijkheid van de gesimuleerde gebeurtenis berekend als de verhouding van het aantal herhalingen van modelexperimenten met een succesvol resultaat tot het aantal totale herhalingen van experimenten onder gegeven initiële omstandigheden (parameters) van het model.
Voor een betrouwbare, in statistische zin, berekening van deze waarschijnlijkheid kan het aantal herhalingen van het experiment worden geschat met behulp van de formule:
Waar 
- functie, omgekeerde functie normale verdeling, 
- betrouwbaarheid kans op fouten 
Waarschijnlijkheidsmetingen.
Daarom, zodat de fout niet verder gaat dan het betrouwbaarheidsinterval met bijvoorbeeld de be =0,95 is het noodzakelijk dat het aantal herhalingen van het experiment niet minder is dan:
(2.2)
Voor een fout van 10% (
=0,1) krijgen we 
, en voor een fout van 3% (
=0,03) krijgen we al 
.
Voor andere beginvoorwaarden van het model moet een nieuwe reeks herhalingen van experimenten worden uitgevoerd op een andere pseudo-willekeurige reeks. Daarom moet de functie voor het genereren van pseudo-willekeurige reeksen een parameter hebben die deze wijzigt (bijvoorbeeld R 0 ), of de lengte moet minimaal zijn:
Waar K - aantal beginvoorwaarden (punten op de curve bepaald door de Monte Carlo-methode), N - aantal herhalingen van het modelexperiment onder gegeven beginvoorwaarden, L - lengte van de pseudowillekeurige reeks.
Vervolgens elke serie van N herhalingen van elk experiment zullen worden uitgevoerd op zijn eigen segment van de pseudo-willekeurige reeks.
Reproduceerbaarheid. Zoals hierboven vermeld is het wenselijk om een parameter te hebben die de generatie van pseudo-willekeurige getallen verandert. Meestal is dit R 0 . Daarom is het erg belangrijk dat de verandering 0 heeft de kwaliteit (dat wil zeggen statistische parameters) van de generator voor willekeurige getallen niet aangetast.
Goede statistische eigenschappen. Dit is de belangrijkste indicator voor de kwaliteit van een willekeurige nummergenerator. Het kan echter niet door één enkel criterium of test worden beoordeeld, omdat Er zijn geen noodzakelijke en voldoende criteria voor de willekeur van een eindige reeks getallen. Het meeste dat over een pseudowillekeurige reeks getallen kan worden gezegd, is dat deze er willekeurig ‘lijkt’. Geen enkele statistische test is een betrouwbare indicator voor de nauwkeurigheid. Het is op zijn minst noodzakelijk om meerdere tests te gebruiken die de belangrijkste aspecten van de kwaliteit van de generator voor willekeurige getallen weerspiegelen, d.w.z. de mate waarin het een ideale generator benadert.
Daarom is het, naast het testen van de generator, uiterst belangrijk om deze te testen met behulp van standaardproblemen die een onafhankelijke beoordeling van de resultaten met analytische of numerieke methoden mogelijk maken.
Er kan worden gezegd dat het idee van de betrouwbaarheid van pseudo-willekeurige getallen ontstaat tijdens het gebruik ervan, waarbij de resultaten waar mogelijk zorgvuldig worden gecontroleerd.
Merk op dat idealiter de verdelingsdichtheidscurve van willekeurige getallen eruit zou zien zoals weergegeven in figuur 1. 22.3. Dat wil zeggen dat elk interval idealiter hetzelfde aantal punten bevat: N i = N/k , Waar N totaal aantal punten, k aantal intervallen, i= 1, , k .
theoretisch gegenereerd door een ideale generator
Houd er rekening mee dat het genereren van een willekeurig willekeurig getal uit twee fasen bestaat:
- het genereren van een genormaliseerd willekeurig getal (dat wil zeggen uniform verdeeld van 0 tot 1);
- genormaliseerde conversie van willekeurige getallen R i naar willekeurige getallen X i, die worden gedistribueerd volgens het door de gebruiker vereiste (willekeurige) distributierecht of in het vereiste interval.
Willekeurige nummergeneratoren volgens de methode voor het verkrijgen van getallen zijn onderverdeeld in:
- fysiek;
- tabelvormig;
- algoritmisch.
Fysieke RNG
Een voorbeeld van een fysieke RNG kan zijn: een munt (“kop” 1, “munt” 0); Dobbelsteen; een trommel met een pijl verdeeld in sectoren met cijfers; hardwareruisgenerator (HN), die gebruik maakt van een luidruchtige thermisch apparaat, bijvoorbeeld een transistor (Fig. 22.422.5).
| Taak “Willekeurige getallen genereren met behulp van een munt” | |
|
Genereer een willekeurig getal van drie cijfers, uniform verdeeld in het bereik van 0 tot 1, met behulp van een munt. Nauwkeurigheid drie decimalen. |
|
De eerste manier om het probleem op te lossen
Teken een interval van 0 tot 1. Lees de getallen in volgorde van links naar rechts, deel het interval in tweeën en kies elke keer een van de delen van het volgende interval (als je een 0 krijgt, dan de linker, als je een interval krijgt) een 1, dan de juiste). U kunt dus elk punt in het interval bereiken, zo nauwkeurig als u wilt. Dus, 1 : het interval wordt in tweeën gedeeld en , de rechterhelft is geselecteerd, het interval wordt versmald: . Volgend nummer 0 : het interval wordt in tweeën gedeeld en , de linkerhelft is geselecteerd, het interval wordt versmald: . Volgend nummer 0 : het interval wordt in tweeën gedeeld en , de linkerhelft is geselecteerd, het interval wordt versmald: . Volgend nummer 1 : het interval wordt in tweeën gedeeld en , de rechterhelft is geselecteerd, het interval wordt versmald: . Afhankelijk van de nauwkeurigheidsvoorwaarde van het probleem is er een oplossing gevonden: het is een willekeurig getal uit het interval, bijvoorbeeld 0,625. Als we strikt te werk gaan, moet de verdeling van de intervallen in principe worden voortgezet totdat de linker- en rechtergrenzen van het gevonden interval SAMENSTELLEN met een nauwkeurigheid van drie decimalen. Dat wil zeggen, vanuit het oogpunt van nauwkeurigheid zal het gegenereerde getal niet langer te onderscheiden zijn van enig getal uit het interval waarin het zich bevindt.
De tweede manier om het probleem op te lossen
|
RNG in tabelvorm
RNG's in tabelvorm gebruiken speciaal samengestelde tabellen met geverifieerde, niet-gecorreleerde, dat wil zeggen op geen enkele manier afhankelijk van elkaar, getallen als bron van willekeurige getallen. In tafel Figuur 22.1 toont een klein fragment van zo'n tabel. Door de tabel van links naar rechts van boven naar beneden te doorlopen, kunt u willekeurige getallen verkrijgen, gelijkmatig verdeeld van 0 tot 1, met het vereiste aantal decimalen (in ons voorbeeld gebruiken we drie decimalen voor elk getal). Omdat de getallen in de tabel niet van elkaar afhankelijk zijn, kan de tabel worden doorlopen verschillende manieren bijvoorbeeld van boven naar beneden of van rechts naar links, of u kunt bijvoorbeeld getallen selecteren die op even posities staan.
| Tabel 22.1. Willekeurige nummers. Gelijkmatig willekeurige getallen verdeeld van 0 tot 1 |
||||||||||||||||||||||||||||||||||||||||||||
| Willekeurige nummers | Gelijk verdeeld 0 tot 1 willekeurige getallen |
|||||||
| 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 |
Waardigheid deze methode is dat het echt willekeurige getallen produceert, omdat de tabel geverifieerde, niet-gecorreleerde getallen bevat. Nadelen van de methode: voor opslag grote hoeveelheid getallen vereisen veel geheugen; Er zijn grote problemen bij het genereren en controleren van dit soort tabellen; herhalingen bij het gebruik van een tabel garanderen niet langer de willekeur van de numerieke reeks, en dus de betrouwbaarheid van het resultaat.
Er is een tabel met 500 absoluut willekeurige geverifieerde getallen (ontleend aan het boek van I.G. Venetsky, V.I. Venetskaya "Basis wiskundige en statistische concepten en formules in economische analyse").
Algoritmische RNG
De door deze RNG's gegenereerde getallen zijn altijd pseudo-willekeurig (of quasi-willekeurig), dat wil zeggen dat elk volgend gegenereerd getal afhankelijk is van het vorige:
R i + 1 = F(R i) .
Reeksen die uit dergelijke getallen bestaan, vormen lussen, dat wil zeggen dat er noodzakelijkerwijs een cyclus is die zich een oneindig aantal keren herhaalt. Herhalende cycli worden perioden genoemd.
Het voordeel van deze RNG's is hun snelheid; generatoren vereisen vrijwel geen geheugenbronnen en zijn compact. Nadelen: de getallen kunnen niet volledig willekeurig worden genoemd, omdat er een afhankelijkheid tussen hen bestaat, evenals de aanwezigheid van punten in de reeks quasi-willekeurige getallen.
Laten we verschillende algoritmische methoden bekijken voor het verkrijgen van RNG:
- methode van mediaanvierkanten;
- methode van middenproducten;
- roermethode;
- lineaire congruente methode.
Midsquare-methode
Er is een nummer van vier cijfers R 0 . Dit getal wordt gekwadrateerd en ingevoerd R 1. Volgende van R 1 neemt het middelste (vier middelste cijfers) nieuwe willekeurige getal en schrijft dit in R 0 . Vervolgens wordt de procedure herhaald (zie Fig. 22.6). Houd er rekening mee dat u in feite geen willekeurig getal hoeft te nemen ghij, A 0.ghij met links een nul en een decimaalpunt toegevoegd. Dit feit wordt weerspiegeld zoals in Fig. 22.6, en in daaropvolgende soortgelijke figuren.
 |
Nadelen van de methode: 1) als het aantal bij een bepaalde iteratie toeneemt R 0 gelijk wordt aan nul, dan degenereert de generator, dus de juiste keuze van de beginwaarde is belangrijk R 0; 2) de generator herhaalt de reeks M N stappen (in het beste geval), waar N nummer cijfer R 0 , M basis van het getallenstelsel.
Bijvoorbeeld in afb. 22.6: als het nummer R In het binaire getalsysteem wordt 0 weergegeven, waarna de reeks pseudo-willekeurige getallen wordt herhaald in 2 4 = 16 stappen. Houd er rekening mee dat de herhaling van de reeks eerder kan plaatsvinden als het startnummer slecht is gekozen.
De hierboven beschreven methode werd voorgesteld door John von Neumann en dateert uit 1946. Omdat deze methode onbetrouwbaar bleek te zijn, werd deze snel verlaten.
Middelproductmethode
Nummer R 0 vermenigvuldigd met R 1, uit het verkregen resultaat R 2 het midden wordt eruit gehaald R 2 * (dit is weer een willekeurig getal) en vermenigvuldigd met R 1. Alle volgende willekeurige getallen worden met dit schema berekend (zie figuur 22.7).
 |
Roermethode
De shuffle-methode gebruikt bewerkingen om de inhoud van een cel cyclisch naar links en rechts te verschuiven. Het idee van de methode is als volgt. Laat de cel het beginnummer opslaan R 0 . Door de inhoud van de cel cyclisch met 1/4 van de cellengte naar links te verschuiven, verkrijgen we een nieuw getal R 0 * . Op dezelfde manier circuleert de inhoud van de cel R 0 naar rechts met 1/4 van de cellengte, we krijgen het tweede getal R 0**. Som van getallen R 0* en R 0** geeft een nieuw willekeurig getal R 1. Verder R Er wordt 1 ingevoerd R 0, en de volledige reeks bewerkingen wordt herhaald (zie figuur 22.8).
 |
Houd er rekening mee dat het getal het resultaat is van de sommatie R 0* en R 0 **, past mogelijk niet volledig in de cel R 1. In dit geval moeten de extra cijfers uit het resulterende getal worden verwijderd. Laten we dit uitleggen in Fig. 22.8, waar alle cellen worden weergegeven door acht binaire cijfers. Laten R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Dan R 0 * + R 0 ** = 100110010 2 = 306 10 . Zoals u kunt zien, bestaat het getal 306 uit 9 cijfers (in het binaire getalsysteem) en de cel R 1 (hetzelfde als R 0) kan maximaal 8 bits bevatten. Daarom, voordat u de waarde invoert R 1 is het noodzakelijk om één “extra”, meest linkse bit van het getal 306 te verwijderen, wat resulteert in R 1 gaat niet meer naar 306, maar naar 00110010 2 = 50 10 . Merk ook op dat in talen als Pascal het “trimmen” van extra bits wanneer een cel overloopt automatisch wordt uitgevoerd in overeenstemming met het opgegeven type variabele.
Lineaire congruente methode
De lineaire congruente methode is een van de eenvoudigste en meest gebruikte procedures die momenteel willekeurige getallen simuleren. Deze methode gebruikt de mod( X, j), die de rest retourneert wanneer het eerste argument wordt gedeeld door het tweede. Elk volgend willekeurig getal wordt berekend op basis van het vorige willekeurige getal met behulp van de volgende formule:
R i+ 1 = aangepast( k · R i + B, M) .
De reeks willekeurige getallen die met deze formule wordt verkregen, wordt genoemd lineaire congruente reeks. Veel auteurs noemen een lineaire congruente rij wanneer B = 0 multiplicatieve congruente methode, en wanneer B ≠ 0 gemengde congruente methode.
Voor een hoogwaardige generator is het noodzakelijk om geschikte coëfficiënten te selecteren. Het is noodzakelijk dat het nummer M was behoorlijk groot, aangezien de periode niet meer kan hebben M elementen. Aan de andere kant is de verdeling die bij deze methode wordt gebruikt nogal langzaam, dus voor een binaire computer zou de logische keuze zijn M = 2 N, aangezien in dit geval het vinden van de rest van de deling binnen de computer wordt gereduceerd tot de binaire logische bewerking "AND". Het kiezen van het grootste priemgetal is ook gebruikelijk M, minder dan 2 N: in de gespecialiseerde literatuur is bewezen dat in dit geval de cijfers van lage orde het resulterende willekeurige getal zijn R i+ 1 gedragen zich net zo willekeurig als de oudere, wat een positief effect heeft op de hele reeks willekeurige getallen als geheel. Als voorbeeld: een van de Mersenne-nummers, gelijk aan 2 31 1, en dus, M= 2 31 1 .
Een van de vereisten voor lineaire congruente reeksen is dat de periodelengte zo lang mogelijk is. De lengte van de periode is afhankelijk van de waarden M , k En B. Met de stelling die we hieronder presenteren, kunnen we bepalen of het mogelijk is om voor specifieke waarden een periode van maximale lengte te bereiken M , k En B .
Stelling. Lineaire congruente reeks gedefinieerd door getallen M , k , B En R 0, heeft een lengteperiode M als en alleen als:
- cijfers B En M relatief simpel;
- k 1 maal P voor elke primeur P, wat een deler is M ;
- k 1 is een veelvoud van 4, als M veelvoud van 4.
Laten we tot slot afsluiten met een paar voorbeelden van het gebruik van de lineaire congruente methode om willekeurige getallen te genereren.
Er werd bepaald dat een reeks pseudo-willekeurige getallen, gegenereerd op basis van de gegevens uit voorbeeld 1, elke keer herhaald zou worden M/4 cijfers. Nummer Q wordt willekeurig vastgesteld vóór het begin van de berekeningen, maar er moet rekening mee worden gehouden dat de reeks de indruk wekt in het algemeen willekeurig te zijn k(en daarom Q). Het resultaat kan enigszins worden verbeterd als B vreemd en k= 1 + 4 · Q in dit geval wordt de rij elke keer herhaald M cijfers. Na lang zoeken k de onderzoekers kwamen uit op waarden van 69069 en 71365.
Een generator voor willekeurige getallen die de gegevens uit voorbeeld 2 gebruikt, produceert willekeurige, niet-herhalende getallen met een periode van 7 miljoen.
De multiplicatieve methode voor het genereren van pseudowillekeurige getallen werd in 1949 voorgesteld door DH Lehmer.
Controle van de kwaliteit van de generator
De kwaliteit van het gehele systeem en de nauwkeurigheid van de resultaten zijn afhankelijk van de kwaliteit van de RNG. Daarom willekeurige volgorde, gegenereerd door de RNG, moet aan een aantal criteria voldoen.
De uitgevoerde controles zijn van twee soorten:
- controles op uniformiteit van distributie;
- tests voor statistische onafhankelijkheid.
Controle op uniformiteit van distributie
1) De RNG zou dicht bij de volgende waarden van statistische parameters moeten produceren die kenmerkend zijn voor een uniforme willekeurige wet:
2) Frequentietest
Met een frequentietest kunt u erachter komen hoeveel getallen er binnen een interval vallen (M R σ R ; M R + σ R) , dat wil zeggen (0,5 0,2887; 0,5 + 0,2887) of uiteindelijk (0,2113; 0,7887). Aangezien 0,7887 0,2113 = 0,5774 concluderen we dat in een goede RNG ongeveer 57,7% van alle getrokken willekeurige getallen in dit interval zou moeten vallen (zie figuur 22.9).
in het geval van controle op frequentietest
Het is ook noodzakelijk om er rekening mee te houden dat het aantal getallen dat in het interval valt (0; 0,5) ongeveer gelijk moet zijn aan het aantal getallen dat in het interval valt (0,5; 1).
3) Chi-kwadraattoets
De chikwadraattoets (χ 2 toets) is een van de bekendste statistische toetsen; het is de belangrijkste methode die wordt gebruikt in combinatie met andere criteria. De chikwadraattoets werd in 1900 voorgesteld door Karl Pearson. Zijn opmerkelijke werk wordt beschouwd als de basis van de moderne wiskundige statistiek.
In ons geval zullen tests met behulp van het chi-kwadraatcriterium ons in staat stellen erachter te komen hoeveel de echt De RNG ligt dicht bij de RNG-benchmark, dat wil zeggen of deze nu voldoet aan de uniforme distributievereiste of niet.
Frequentiediagram referentie De RNG wordt getoond in Fig. 22.10. Omdat de verdelingswet van de referentie-RNG uniform is, geldt ook de (theoretische) waarschijnlijkheid P i cijfers erin krijgen i e interval (al deze intervallen k) is gelijk aan P i = 1/k . En dus in elk van k intervallen zullen toeslaan zacht Door P i · N cijfers ( N totaal gegenereerde nummers).
Een echte RNG zal getallen produceren die verdeeld (en niet noodzakelijkerwijs gelijkmatig!) Over de hele wereld zijn verdeeld k intervallen en elk interval zal bevatten N i aantallen (in totaal N 1 + N 2 + + N k = N ). Hoe kunnen we bepalen hoe goed de geteste RNG is en hoe dicht deze bij de referentie ligt? Het is heel logisch om rekening te houden met de kwadratische verschillen tussen het resulterende aantal getallen N i en "referentie" P i · N . Laten we ze bij elkaar optellen en het resultaat is:
χ 2 exp. = ( N 1 P 1 · N) 2 + (N 2 P 2 · N) 2 + + ( N k P k · N) 2 .
Uit deze formule volgt dat hoe kleiner het verschil in elk van de termen (en dus de minder waardeχ 2 exp. ), hoe sterker de wet van de verdeling van willekeurige getallen die door een echte RNG wordt gegenereerd, doorgaans uniform is.
In de vorige uitdrukking wordt aan elk van de termen hetzelfde gewicht toegekend (gelijk aan 1), wat in feite misschien niet waar is; daarom is het voor chikwadraatstatistieken noodzakelijk om ze allemaal te normaliseren i e term, gedeeld door P i · N :
Laten we tot slot de resulterende uitdrukking compacter schrijven en vereenvoudigen:
We hebben de chikwadraattestwaarde verkregen voor experimenteel gegevens.
In tafel 22.2 worden gegeven theoretisch chi-kwadraatwaarden (χ 2 theoretisch), waarbij ν = N 1 is het aantal vrijheidsgraden, P dit is een door de gebruiker gespecificeerd betrouwbaarheidsniveau dat aangeeft in hoeverre de RNG moet voldoen aan de eisen van een uniforme verdeling, of P is de waarschijnlijkheid dat de experimentele waarde van χ 2 exp. zal kleiner zijn dan de tabel (theoretische) χ 2 theoretisch. of gelijk daaraan.
| Tabel 22.2. Enkele procentpunten van de χ 2-verdeling |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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/vierkante( ν )) | ||||||
| X P = | 2.33 | 1,64 | 0,674 | 0.00 | 0.674 | 1.64 | 2.33 |
Aanvaardbaar geacht P van 10% tot 90%.
Als χ 2 exp. veel meer dan de χ 2-theorie. (dat is P groot is), dan de generator bevredigt niet de eis van een uniforme verdeling, aangezien de waargenomen waarden N i gaan te ver van de theorie P i · N en kan niet als willekeurig worden beschouwd. Met andere woorden, er wordt zo'n groot betrouwbaarheidsinterval vastgesteld dat de beperkingen op de cijfers zeer soepel worden en de eisen aan de cijfers zwak worden. In dit geval zal een zeer grote absolute fout worden waargenomen.
Zelfs D. Knuth merkte in zijn boek “The Art of Programming” op dat het hebben van χ 2 exp. voor kleintjes is het over het algemeen ook niet goed, hoewel dit op het eerste gezicht prachtig lijkt vanuit het oogpunt van uniformiteit. Neem inderdaad een reeks getallen 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, deze zijn ideaal vanuit het oogpunt van uniformiteit, en χ 2 exp. zullen praktisch nul zijn, maar het is onwaarschijnlijk dat u ze als willekeurig zult herkennen.
Als χ 2 exp. veel minder dan de χ 2-theorie. (dat is P klein), dan de generator bevredigt niet de eis van een willekeurige uniforme verdeling, aangezien de waargenomen waarden N i te dicht bij de theorie P i · N en kan niet als willekeurig worden beschouwd.
Maar als χ 2 exp. ligt in een bepaald bereik tussen twee waarden van χ 2-theorie. , die overeenkomen met bijvoorbeeld P= 25% en P= 50%, dan kunnen we ervan uitgaan dat de door de sensor gegenereerde willekeurige getalswaarden volledig willekeurig zijn.
Bovendien moet in gedachten worden gehouden dat alle waarden P i · N moet groot genoeg zijn, bijvoorbeeld meer dan 5 (empirisch gevonden). Alleen dan (met een voldoende grote statistische steekproef) kunnen de experimentele omstandigheden als bevredigend worden beschouwd.
De verificatieprocedure is dus als volgt.
Tests voor statistische onafhankelijkheid
1) Controleren op de frequentie waarmee getallen in de reeks voorkomen
Laten we eens kijken naar een voorbeeld. Het willekeurige getal 0,2463389991 bestaat uit de cijfers 2463389991, en het getal 0,5467766618 bestaat uit de cijfers 5467766618. Door de reeksen cijfers met elkaar te verbinden, krijgen we: 24633899915467766618.
Het is duidelijk dat de theoretische waarschijnlijkheid P i verlies i Het e-cijfer (van 0 tot 9) is gelijk aan 0,1.
2) Controle van het uiterlijk van reeksen identieke cijfers
Laten we aanduiden met N L aantal reeksen identieke cijfers in een rij van lengte L. Alles moet worden gecontroleerd L van 1 tot M, Waar M dit is een door de gebruiker opgegeven getal: het maximaal voorkomende aantal identieke cijfers in een reeks.
In het voorbeeld “24633899915467766618” zijn 2 series met lengte 2 (33 en 77) gevonden, dat wil zeggen N 2 = 2 en 2 series met lengte 3 (999 en 666) dus N 3 = 2 .
De waarschijnlijkheid dat een reeks van lengte voorkomt L is gelijk aan: P L= 9 10 L (theoretisch). Dat wil zeggen, de kans op het voorkomen van een reeks van één teken lang is gelijk aan: P 1 = 0,9 (theoretisch). De kans dat een reeks van twee karakters verschijnt is: P 2 = 0,09 (theoretisch). De kans dat een reeks van drie karakters verschijnt is: P 3 = 0,009 (theoretisch).
De kans op het voorkomen van een reeks is bijvoorbeeld één teken lang P L= 0,9, aangezien er maar één symbool op 10 kan zijn, en er in totaal 9 symbolen zijn (nul telt niet). En de kans dat twee identieke symbolen “XX” op een rij verschijnen is 0,1 · 0,1 · 9, dat wil zeggen dat de kans van 0,1 dat het symbool “X” op de eerste positie verschijnt, wordt vermenigvuldigd met de kans van 0,1 dat de hetzelfde symbool verschijnt op de tweede positie “X” en vermenigvuldigd met het aantal van dergelijke combinaties 9.
De frequentie waarmee reeksen voorkomen, wordt berekend met behulp van de chikwadraatformule die we eerder hebben besproken met behulp van de waarden P L .
Let op: De generator kan meerdere keren worden getest, maar de tests zijn niet compleet en garanderen niet dat de generator willekeurige getallen produceert. Een generator die bijvoorbeeld de reeks 12345678912345 produceert, zal tijdens tests als ideaal worden beschouwd, wat uiteraard niet helemaal waar is.
Concluderend merken we op dat het derde hoofdstuk van Donald E. Knuths boek The Art of Programming (Deel 2) geheel gewijd is aan de studie van willekeurige getallen. Het studeert verschillende methoden het genereren van willekeurige getallen, statistische tests van willekeur en het omzetten van uniform verdeelde willekeurige getallen naar andere soorten willekeurige variabelen. Meer dan tweehonderd pagina's zijn gewijd aan de presentatie van dit materiaal.
Deterministische PRNG's
Geen enkel deterministisch algoritme kan volledig willekeurige getallen genereren; het kan slechts enkele eigenschappen van willekeurige getallen benaderen. Zoals John von Neumann zei: " iedereen die een zwak heeft voor rekenkundige methoden om willekeurige getallen te verkrijgen, is zonder enige twijfel zondig».
Elke PRNG met beperkte middelen gaat vroeg of laat in cycli: het begint dezelfde reeks getallen te herhalen. De lengte van PRNG-cycli hangt af van de generator zelf en is gemiddeld ongeveer 2 n/2, waarbij n de grootte is interne staat in bits, hoewel lineaire congruente en LFSR-generatoren maximale cycli in de orde van 2n hebben. Als een PRNG kan convergeren naar te korte cycli, wordt de PRNG voorspelbaar en onbruikbaar.
De meeste eenvoudige rekenkundige generatoren hebben, hoewel ze erg snel zijn, veel ernstige nadelen:
- De periode(s) is/zijn te kort.
- Opeenvolgende waarden zijn niet onafhankelijk.
- Sommige bits zijn "minder willekeurig" dan andere.
- Ongelijke eendimensionale verdeling.
- Omkeerbaarheid.
Met name het mainframe-algoritme bleek erg slecht te zijn, wat twijfels deed rijzen over de validiteit van de resultaten van veel onderzoeken waarin dit algoritme werd gebruikt.
PRNG met entropiebron of RNG
Net zoals er behoefte is aan het genereren van gemakkelijk herhaalbare reeksen willekeurige getallen, is er ook behoefte aan het genereren van volledig onvoorspelbare of eenvoudigweg volledig willekeurige getallen. Dergelijke generatoren worden genoemd generatoren van willekeurige getallen(RNG - Engels) willekeurige nummergenerator, RNG). Omdat dergelijke generatoren het vaakst worden gebruikt om unieke symmetrische en asymmetrische sleutels voor encryptie te genereren, zijn ze meestal opgebouwd uit een combinatie van een cryptografisch sterke PRNG en een externe bron van entropie (en het is precies deze combinatie die nu algemeen wordt opgevat als een RNG).
Bijna alle grote fabrikanten microchips worden geleverd door hardware-RNG's verschillende bronnen entropie, waarbij verschillende methoden worden gebruikt om ze van onvermijdelijke voorspelbaarheid te ontdoen. Echter, op dit moment de snelheid waarmee willekeurige getallen door alle bestaande microchips worden verzameld (enkele duizenden bits per seconde) komt niet overeen met de snelheid van moderne processors.
Op personal computers gebruiken software-RNG-auteurs veel snellere bronnen van entropie, zoals geluidskaartruis of processorklokcyclusteller. Voordat het mogelijk werd om kloktellerwaarden af te lezen, was entropieverzameling het meest kwetsbare punt van de RNG. Bij veel apparaten (bijvoorbeeld smartcards), die dus kwetsbaar blijven, is dit probleem nog steeds niet volledig opgelost. Veel RNG's gebruiken nog steeds traditionele (verouderde) methoden voor het verzamelen van entropie, zoals het meten van gebruikersreacties (muisbewegingen, enz.), zoals bijvoorbeeld, of interactie tussen threads, zoals in Java Secure Random.
Voorbeelden van RNG- en entropiebronnen
Een paar voorbeelden van RNG's met hun entropiebronnen en generatoren:
| Bron van entropie | PRNG | Voordelen | Gebreken | |
|---|---|---|---|---|
| /dev/random op Linux | CPU-klokteller, wordt echter alleen verzameld tijdens hardware-interrupts | LFSR, met uitvoer gehasht via | Het “warmt” heel lang op, kan lange tijd “vastlopen” of werkt als een PRNG ( /dev/urandom) | |
| Duizendblad van Bruce Schneier | Traditionele (verouderde) methoden | AES-256 en | Flexibel cryptobestendig ontwerp | Het duurt lang om op te warmen, zeer kleine interne toestand, hangt te veel af van de cryptografische sterkte van de geselecteerde algoritmen, traag, uitsluitend toepasbaar voor het genereren van sleutels |
| Generator door Leonid Yuryev | Geluidskaart geluid | ? | Hoogstwaarschijnlijk een goede en snelle bron van entropie | Geen onafhankelijke, bekende crypto-sterke PRNG, exclusief beschikbaar als Windows |
| Microsoft | Ingebouwd in Windows, loopt niet vast | Kleine interne toestand, gemakkelijk te voorspellen | ||
| Communicatie tussen threads | Er is nog geen andere keuze op Java, er is een grote interne staat | Langzame entropieverzameling | ||
| Chaos van Ruptor | Processorklokteller, continu verzameld | Hashing van 4096-bit interne status gebaseerd op een niet-lineaire variant van de Marsaglia-generator | Totdat de snelste van allemaal, de grote interne staat, “vastloopt” | |
| RAND van Ruptor | Processorklokteller | Interne status coderen met een stroomcodering | Zeer snelle, interne staat van willekeurige grootte om uit te kiezen, geen “vastlopen” |
PRNG in cryptografie
Een type PRNG zijn PRBG's - generatoren van pseudo-willekeurige bits, evenals verschillende stroomcijfers. PRNG's bestaan, net als stroomcijfers, uit een interne toestand (meestal variërend in grootte van 16 bits tot enkele megabytes), een functie om de interne toestand te initialiseren met een sleutel of zaad(Engels) zaad), interne statusupdatefuncties en uitvoerfuncties. PRNG's zijn onderverdeeld in eenvoudig rekenkundig, gebroken cryptografisch en cryptografisch sterk. Hun algemene doel is het genereren van reeksen getallen die door computermethoden niet van willekeurig kunnen worden onderscheiden.
Hoewel veel sterke PRNG's of stroomcijfers veel meer "willekeurige" getallen bieden, zijn dergelijke generatoren veel langzamer dan conventionele rekenkundige generatoren en zijn ze mogelijk niet geschikt voor enig soort onderzoek waarbij de processor vrij moet zijn voor nuttiger berekeningen.
Voor militaire doeleinden en veldomstandigheden Er worden alleen geheime synchrone cryptografische sterke PRNG's (stream ciphers) gebruikt; blokcijfers worden niet gebruikt. Voorbeelden van bekende crypto-sterke PRNG’s zijn ISAAC, SEAL, Snow, het zeer trage theoretische algoritme van Bloom, Bloom en Shub, maar ook tellers met cryptografische hashfuncties of sterke blokcijfers in plaats van een uitvoerfunctie.
Hardware-PRNG
Afgezien van de oude, bekende LFSR-generatoren die in de 20e eeuw op grote schaal werden gebruikt als hardware-PRNG's, is er helaas heel weinig bekend over moderne hardware-PRNG's (stream ciphers), aangezien de meeste daarvan voor militaire doeleinden zijn ontwikkeld en geheim worden gehouden. . Bijna alle bestaande commerciële hardware-PRNG's zijn gepatenteerd en ook geheim gehouden. Hardware PRNG's worden beperkt door strikte eisen voor verbruiksgeheugen (meestal is het gebruik van geheugen verboden), snelheid (1-2 klokcycli) en oppervlakte (enkele honderden FPGA - of
Vanwege het gebrek aan goede hardware-PRNG's zijn fabrikanten gedwongen de veel langzamere, maar bekende blokcoderingen te gebruiken die beschikbaar zijn (Computer Review nr. 29 (2003)
Les 15. Kans is de ziel van het spel
Je hebt de schildpad al veel geleerd. Maar ze heeft ook andere, verborgen mogelijkheden. Kan een schildpad uit zichzelf iets doen dat je zal verrassen?
Het blijkt ja! Er staan schildpadden in de lijst met sensoren willekeurige getalsensor:
willekeurig
Willekeurige getallen komen we vaak tegen: bij het gooien Dobbelsteen in een kinderspel, luisterend naar een waarzeggende koekoek in het bos of gewoon ‘een willekeurig getal raden’. De sensor voor willekeurige getallen in LogoWorlds kan de waarde aannemen van elk positief geheel getal van 0 tot de waardelimiet die als parameter is opgegeven.
Het getal zelf, gespecificeerd als parameter van de sensor voor willekeurige getallen, verschijnt nooit.
Een willekeurige sensor 20 kan bijvoorbeeld elk geheel getal zijn van 0 tot 19, inclusief 19, en een willekeurige sensor 1000 kan elk geheel getal zijn van 0 tot 999, inclusief 999.
Je vraagt je misschien af waar het spel is: alleen maar cijfers. Maar vergeet niet dat je in LogoWorlds cijfers kunt gebruiken om de vorm van de schildpad, de dikte van de schrijfpen, de grootte, kleur en nog veel meer in te stellen. Het belangrijkste is om de juiste grenswaarden te kiezen. De grenzen van verandering in de basisparameters van de schildpad worden weergegeven in de tabel.
De generator voor willekeurige getallen kan bijvoorbeeld als parameter voor elk commando worden gebruikt vooruit, rechts enzovoort.
Taak 24. Met behulp van de willekeurige getalsensor
Organiseer een van de hieronder voorgestelde spellen met behulp van de sensor voor willekeurige getallen en start de schildpad.
Spel 1: Kleurrijk scherm
1. Plaats de schildpad in het midden van het scherm.
2. Voer opdrachten in de Backpack in en stel de modus in Vele keren:
new_color willekeurig 140 verf wachten 10
Team verf voert dezelfde acties uit als het gereedschap Opvullen in de grafische editor.
3. Verwoord de plot.
Spel 2: “De vrolijke schilder” 1. Pas spel #1 aan door lijnen op het scherm te tekenen in willekeurige gebieden met doorlopende grenzen:
2. Voltooi de instructies in de Turtle Backpack met willekeurige beurten en bewegingen:
rechts willekeurig 360
vooruit willekeurig 150
Zet instructies in de rugzak om de schildpad te verplaatsen ( vooruit 60) met een 60 dikke punt in willekeurige kleur (0-139) die onder een kleine hoek is neergelaten ( nieuwe_cursus 10).Spel 4: "Jagen"
Ontwikkel een plot waarin een rode schildpad op een zwarte jaagt. De zwarte schildpad beweegt langs een willekeurig traject en de bewegingsrichting van de rode schildpad wordt bepaald door een schuifregelaar.
Vragen voor zelfbeheersing
1. Wat is een willekeurige nummergenerator?
2. Wat is de parameter van de willekeurige getalsensor?
3. Wat betekent de waardegrens?
4. Komt het als parameter opgegeven getal ooit voor?
Het eerste algoritme voor het verkrijgen van pseudowillekeurige getallen werd voorgesteld door J. Neumann. Het wordt de methode van het midden van vierkanten genoemd.
Laat een 4-cijferig getal R gegeven worden 0 =0,9876. Laten we het kwadrateren. Laten we een 8-cijferig getal R nemen 0 2 =0,97535376. Laten we de 4 middelste cijfers van dit getal kiezen en R invoeren 1 =0,5353. Dan kwadrateren we het opnieuw en extraheren we de 4 middelste cijfers eruit. Wij krijgen R 2 enz. Dit algoritme heeft zichzelf niet bewezen. Het bleken meer dan noodzakelijke kleine waarden van R te zijn i .
Het is echter interessant om de kwaliteit van deze generator te onderzoeken met de cijferselectiegroep van R naar rechts verschoven i 2 :
waarbij a de maximale waarde van de breuk is voor een bepaalde computer (bijvoorbeeld a = 8).
b-aantal decimalen in het getal R i(bijvoorbeeld 5).
INT(A) is het gehele deel van het getal.
Voor a=8,b=5,R 0 =0,51111111 op de PC ZX-Spectrum resulteert dit in ongeveer 1200 niet-herhalende getallen.
Oefening: Het onderzoek moet worden uitgevoerd door a, b, R te variëren 0 . Zoek bij welke waarden a, b, R 0 de grootste lengte L van een reeks niet-herhalende getallen wordt verkregen met “goede” stochastische parameters. Bepaal of de waarde R van invloed is 0 over de kwaliteit van de sensor. Als dit het geval is, bepaal dan het bereik van “aanvaardbare” waarden van parameter R 0 . Presenteer de resultaten van het testen van de optimale variant van waarden a, b, R 0 .
Multiplicatieve algoritmen. Sensor #2: Lehmer 1951 lineaire congruente generator.
waar jij i,M,Cip – gehele getallen.
AmodB is het restant van de gehele verdeling van A in B,
A mod B =A-B*INT (A/B)
De gegenereerde reeks heeft een zich herhalende cyclus die niet groter is dan p-nummers.
De maximale periode wordt verkregen bij C0, maar een dergelijke generator geeft slechte stochastische resultaten.
Wanneer C=0 worden de generatoren multiplicatief genoemd. Ze hebben betere stochastische parameters. De formules voor het gebruik ervan worden ook wel de aftrekmethode genoemd.
De meest populaire methode voor het verkrijgen van pseudowillekeurige getallen is de aftrekmethode met behulp van de volgende formule:
waar jij i,M,p-gehele getallen, 0
Als u U selecteert 0 en M zodanig dat voor R 0 =U 0 /p bleek een irreducibele breuk te zijn en stel dat p en M onderling priem zijn, dan is alles R i zullen onherleidbare fracties zijn van de vorm: R i=U i/P.
Laten we de grootste (maar niet meer dan p) lengte van een niet-herhalende reeks getallen nemen. U-waarden 0 ,pM Het is handig om uit priemgetallen te kiezen.
Oefening: Onderzoek naar wat U 0 ,pM zal de lengte van de reeks niet-herhalende getallen minimaal 10.000 zijn met “goede” stochastische parameters. Bepaal of de waarde van R 0 wanneer Mip = const op de statistische kenmerken van de sensor. Als dit het geval is, bepaal dan het bereik van de toegestane waardenU 0 . Presenteer de resultaten van generatortests voor optimale waarden van p, Mi en U 0 .
Sensor nr. 3: Korobov-modificatie.
waarbij p een groot priemgetal is, bijvoorbeeld 2027, 5087, ...
M is een geheel getal dat aan de voorwaarden voldoet:
n is een geheel getal. Die. kies M dichtbij p/2 uit de reeks getallen M = p – 3 n .
Voor p=5087 nemen we bijvoorbeeld n=7. Omdat 3 7 =2187, en 3 8 =6561 zal al groter zijn. Dus: M=5087-2187=2900.
We krijgen de cijfers U i in het interval = en getallen R i in het interval (0,1).
Oefening: Selecteer Mp waarvoor de beste statistische parameters van de sensor en de langste lengte L worden verkregen. Ontdek of de waarde van R 0 over de stochastische kenmerken van de sensor en, indien beïnvloed, bepaal vervolgens het bereik van toegestane waarden R 0 . Presenteer sensortestresultaten voor optimale waarden van M, p en R 0 .