Ingezonden door onlinegenerator willekeurige nummers werkt op basis van een pseudo-random number generator met een uniforme verdeling ingebouwd in JavaScript. Er worden gehele getallen gegenereerd. Standaard worden er 10 willekeurige getallen uitgevoerd in het bereik 100...999, waarbij de getallen worden gescheiden door spaties.
Basisinstellingen van de generator voor willekeurige getallen:
- Aantal cijfers
- Nummerbereik
- Type scheidingsteken
- Schakel de functie voor het verwijderen van herhalingen (duplicaten van getallen) in/uit
De totale hoeveelheid is formeel beperkt tot 1000, Maximaal nummer- 1 miljard. Opties voor scheidingstekens: spatie, komma, puntkomma.
Nu weet u precies waar en hoe u een gratis reeks willekeurige getallen in een bepaald bereik op internet kunt krijgen.
Toepassingsmogelijkheden voor een willekeurige nummergenerator
Een generator voor willekeurige getallen (RNG in JS met uniforme distributie) zal nuttig zijn voor SMM-specialisten en eigenaren van groepen en gemeenschappen in in sociale netwerken Instagram, Facebook, VKontakte, Odnoklassniki om de winnaars van loterijen, wedstrijden en prijstrekkingen te bepalen.
Met een generator voor willekeurige getallen kunt u prijzen trekken onder een willekeurig aantal deelnemers met een bepaald aantal winnaars. Wedstrijden kunnen worden gehouden zonder reposts en reacties - u bepaalt zelf het aantal deelnemers en het interval voor het genereren van willekeurige getallen. U kunt op deze site gratis online een reeks willekeurige getallen verkrijgen en u hoeft geen enkele applicatie op uw smartphone of programma op uw computer te installeren.
Er kan ook een online generator voor willekeurige getallen worden gebruikt om het gooien van een munt of dobbelsteen te simuleren. Voor deze gevallen hebben wij echter aparte gespecialiseerde diensten.
Help de service met één klik: Vertel je vrienden over de generator!
Online nummergenerator in 1 klik
De willekeurige nummergenerator, die op onze website wordt gepresenteerd, is erg handig. Het kan bijvoorbeeld worden gebruikt bij sweepstakes en loterijen om de winnaar te bepalen. De winnaars worden op deze manier bepaald: het programma produceert een of meer getallen in elk door u aangegeven bereik. Frauduleuze resultaten kunnen onmiddellijk worden uitgesloten. En dankzij dit wordt de winnaar bepaald door een eerlijke keuze.
Soms is het nodig om in één keer een bepaald aantal willekeurige getallen te verkrijgen. U wilt bijvoorbeeld een loterijticket "4 uit 35" invullen, vertrouwend op het toeval. U kunt het volgende controleren: als u 32 keer een munt opgooit, wat is dan de kans dat er 10 tegenslagen achter elkaar verschijnen (kop/munt kan heel goed de cijfers 0 en 1 krijgen)?
Willekeurig nummer online video-instructie - randomizer
Onze nummergenerator is zeer eenvoudig te gebruiken. U hoeft geen programma naar uw computer te downloaden; u kunt het online gebruiken. Om het gewenste getal te krijgen, moet u het bereik van willekeurige getallen, het aantal en, indien gewenst, het scheidingsteken voor getallen instellen en herhalingen elimineren.
Om willekeurige getallen te genereren in bepaald bereik frequenties:
- Selecteer een bereik;
- Geef het aantal willekeurige getallen op;
- De functie “Nummerscheidingsteken” dient voor de schoonheid en het gemak van hun weergave;
- Schakel indien nodig herhalingen in/uit met behulp van het selectievakje;
- Klik op de knop "Genereren".
Als gevolg hiervan ontvangt u willekeurige getallen in een bepaald bereik. Het resultaat van de nummergenerator kan worden gekopieerd of per e-mail worden verzonden. Het beste is om een screenshot of video te maken dit proces generatie. Onze randomizer zal al uw problemen oplossen!
Merk op dat idealiter de verdelingsdichtheidscurve van willekeurige getallen eruit zou zien zoals weergegeven in figuur 1. 22.3. Dat wil zeggen dat in het ideale geval elk interval omvat het zelfde nummer punten: 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 verdeeld naar de gewenste gebruiker(willekeurig) 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 (HS), die gebruik maakt van een luidruchtig 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 het derde decimaal. 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 herhaalt oneindig getal eenmaal. 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 er een paar bekijken algoritmische methoden RNG verkrijgen:
- 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 een nul toegewezen aan de linkerkant en decimale punt. 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 zal worden gelijk 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 stapt in in het gunstigste geval), Waar N nummer cijfer R 0 , M basis van het getallensysteem.
Bijvoorbeeld in afb. 22.6: als het nummer R 0 zal worden gepresenteerd binair systeem getal, dan wordt de reeks pseudo-willekeurige getallen 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, omdat in dit geval het vinden van de rest van de deling binnen de computer wordt gereduceerd tot binair logische werking"EN". 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 de periode te bereiken maximale lengte voor specifieke waarden 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 moet de door de RNG gegenereerde willekeurige reeks 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 dichtbij moeten produceren volgende waarden statistische parameters 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 RNG is dichtbij RNG-standaard, dat wil zeggen of het voldoet aan de eis van uniforme distributie 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 aantal 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 ontdekt). 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 gebruiker gedefinieerde 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 typen willekeurige variabelen. Meer dan tweehonderd pagina's zijn gewijd aan de presentatie van dit materiaal.
Bij het ontwikkelen van programma's is er heel vaak behoefte aan een reeks willekeurige getallen. In games kan een reeks willekeurige getallen in verschillende situaties worden gebruikt: het creëren van monsters, het genereren van territorium, het gedrag van kunstmatige intelligentie.
Er zijn veel dingen mogelijk zonder een willekeurige nummergenerator. Een dergelijke reeks getallen kan bijvoorbeeld niet als willekeurig worden beschouwd: (0, 1, 2, 3, 4, 5, 6, 7). Hier, als je het vorige nummer kent, is het heel gemakkelijk om het volgende te raden. Er zijn andere reeksen. Bijvoorbeeld: (0, 1, 3, 2, 6, 7, 5, 4). Hier is het raden van het volgende getal veel moeilijker. Dergelijke reeksen zijn soms handig om in programma's te gebruiken. Deze volgorde wordt bepaald door de Gray-code. Bij de eerste inspectie lijkt het erop dat hier willekeurige getallen zijn.
In plaats van reeksen getallen te gebruiken in programma's die aan bepaalde wetten voldoen, is het in veel gevallen beter om willekeurig gegenereerde getallen te gebruiken.
Het genereren van pseudo-willekeurige getallen
Het genereren van pseudo-willekeurige getallen wordt vaak gebruikt. Die. De cijfers zijn niet geheel willekeurig. We hebben al naar de functie rand() gekeken. Als u een programma schrijft met deze functie, dan zal rand() elke keer dat het programma wordt uitgevoerd, dezelfde reeks getallen genereren. De door rand() gegenereerde reeks wordt bepaald door het zaad. Eerst wordt het initiële getal gespecificeerd en vervolgens worden met behulp van een bepaalde formule alle andere getallen in de reeks berekend. Als u het startgetal kent en de formule waarmee de getallen worden berekend, kunt u het volgende getal berekenen.
Dergelijke algoritmen worden deterministisch (vooraf bepaald) genoemd. Die. daarin wordt een reeks getallen gemaakt op basis van initiële gegevens. In dit geval is de reeks getallen pseudo-willekeurig: d.w.z. Als u het startnummer kent, kunt u alle volgende achterhalen. Maar het is onwaarschijnlijk dat de gebruiker ze herkent; de cijfers lijken willekeurig.
Een van de vooraf gedefinieerde (deterministische) algoritmen voor het genereren van willekeurige getallen is lineair congruent.
Het instellen van de beginwaarde (voor de functie rand() die we tot nu toe hebben gebruikt) ziet er ongeveer zo uit:
code in c++-taal int ik; cin >> ik; srnd(i); // instellen van de initiële waarde rand();
De srnd-functie stelt de initiële waarde van i in.
Lineaire congruentiële methode voor het genereren van willekeurige getallen
Er zijn veel methoden om willekeurige getallen te genereren. Lineair congruent is er slechts één van. De methode is vrij oud - jaren vijftig. Het is ontworpen door Derrick Lemaire.
Om het algoritme te implementeren, moet u vier parameters instellen:
Waardenbereik m, met m > 0.
Vermenigvuldiger a (0<= a <= m).
Oplopende waarde c (0<= c <= m).
Initiële waarde X0 (0<= X0 < m).
Nadat u deze parameters hebt bepaald, kunt u de formule gebruiken:
Xi+1 = (aXi + c) % m (waarbij i groter is dan of gelijk is aan 0)
i is het nummer van het element in de reeks.
m - het aantal waarden waaruit de reeks is gevormd.
Laat me je eraan herinneren dat % de rest van de deling is.
Laten we eens kijken naar een voorbeeld van een kleine reeks. Neem een stuk papier en een potlood en bereken alle waarden:
imax = 5; // vormen een reeks van 5 elementen
m = 10; // waarden in het reeksbereik van nul tot 9
een = 2;
c = 3;
X0 = 6; // initiële waarde (zaad)
Xi+1 = (2*Xi + 3) % 10 (waarbij i groter is dan of gelijk is aan 0)
X1 = 15% 10 = 5
X2 = 13% 10 = 3
X3 = 9% 10 = 9
X4 = 21% 10 = 1
X5 = 5% 10 = 5
Als we de reeks verhogen, beginnen de waarden zich te herhalen. Verschillende niet-herhalende waarden in een reeks vormen dus een punt. De periode in dit voorbeeld is ( 5, 3, 9, 1 ).
Met behulp van de lineaire congruente methode hebben we dus een reeks willekeurige getallen van vijf elementen verkregen.
Om de waarden van elementen in een reeks te voorspellen, kunt u de formule gebruiken:
Xi+k = (a*k*Xi + (a*k-1)*c/b) % m (waarbij k en i groter zijn dan of gelijk zijn aan 0)
Hier b = a - 1. Bovendien geldt a >= 2, b >= 1.
Laten we het zesde element berekenen met behulp van deze formule (we kennen het vijfde al):
X5+1 = (a*1*X5 + (a*1-1)*c/b) % m = (2*1*5 + (2*1-1)*3/1) % 10 = 13 % 10 = 3
Alles groeit, toch?
Een reeks gemaakt met behulp van de lineaire congruente methode en gedefinieerd door gehele parameters m, a, c en X0 heeft een periode gelijk aan het getal m wanneer aan de volgende voorwaarden wordt voldaan:
1. De grootste gemene deler van c en m is 1.
2.b is een veelvoud van elk priemgetal dat een deler is van m.
3. Als m een veelvoud van 4 is, dan is b ook een veelvoud van 4.
Keuze m
De periode kan niet groter zijn dan het getal m. Daarom moet m behoorlijk groot zijn.
Het zou het beste zijn als m gelijk zou zijn aan het maximale element in de reeks imax+1 (we voegen er één toe, aangezien i vanaf nul wordt geteld). Een andere populaire keuze is de kracht van twee 2n. Op voorwaarde dat n de lengte van het machinewoord in bits is, kunt u de restbewerking achterwege laten. Als m een macht van twee is, kan de restbewerking worden vervangen door de snellere bitsgewijze AND-bewerking (hoewel dit niet relevant is voor moderne computers):
x % 2n == x & (2n - 1)
Voorbeelden (x is een geheel getal):
x % 2 == x & 1;
x % 4 == x & 3;
x % 8 == x & 7;
Heel vaak wordt voor m één van de Mersenne-priemgetallen gekozen. Vaak wordt het getal 231 - 1 gebruikt wanneer berekeningen worden uitgevoerd met 32-bits gegevens.
Vermenigvuldiger a
De vermenigvuldiger moet zo worden gekozen dat de periode zo lang mogelijk is. Er is een ernstig probleem met deze coëfficiënt: voor kleine waarden van a geldt dat als het huidige element van de reeks klein genoeg is, het volgende element waarschijnlijk ook klein zal zijn.
Verhogen c
Deze parameter kan vrij willekeurig worden gekozen. Heel vaak wordt deze op nul gezet, maar dit verkort de lengte van de periode en X0 != 0.
Initiële waarde (zaad)
We kwamen er dus achter dat er een punt in de reeks zit. In ons voorbeeld is de periode gelijk aan slechts vier elementen. In andere gevallen kan de periode erg lang zijn, maar hij is er altijd! Dat wil zeggen, als we bij het genereren van willekeurige getallen met behulp van de lineaire congruente methode een zeer grote reeks nodig hebben, dan zullen de waarden daarin met een bepaalde periodiciteit worden herhaald.
Gewoon zo! Het genereren van opeenvolgende nummers is een echte hoax!
Die. Laten we zeggen dat we een generator voor willekeurige getallen hebben. Wij gebruiken het voor verschillende programma's. Altijd, altijd creëert deze generator dezelfde reeks getallen (met dezelfde beginwaarden). We kunnen alleen de beginwaarde instellen.
Over het algemeen is het met rekenkundige methoden onmogelijk om een werkelijk willekeurige reeks getallen te construeren. Hoe treurig grapte onze vriend John Von Neumann:
"Iedereen die rekenkundige methoden gebruikt om willekeurige getallen te produceren, verkeert in een staat van zonde." (C) John Von Neumann.
Het is allemaal triest. Dit is hoe je leeft en leeft. Omdat je in een staat van onwetendheid verkeert, denk je: “Maar het zou cool zijn om een generator voor willekeurige getallen te creëren, gebaseerd op de lineaire cognitieve methode!” Maar het blijkt dat op deze manier geen echt willekeurige reeks kan worden gecreëerd. Instorting van de hoop! Depressie en nu sta je al op de drempel van de eerste fase van alcoholisme. Deze last van het onvermogen om je verlangens te verwezenlijken zal de rest van je leven op je blijven drukken... Ik raakte afgeleid. Laten we doorgaan.
Implementatie van het genereren van willekeurige getallen
Nu we de theoretische kwesties met betrekking tot generatoren van willekeurige getallen hebben bekeken, gaan we eens kijken naar de implementatie, vooral omdat deze vrij eenvoudig is.
Voor de hierboven besproken reeks ziet de generator er als volgt uit:
code in C++-taal int rnd() ( int m = 10, a = 2, c = 3; statische int x = x0; // x wordt gedeclareerd als een statische variabele x = ((a * x) + c) % m; // formule x0 = x; retourneer x; )
X0 wordt gedeclareerd als een globale variabele:
int x0 = 6;
Dit is de meest primitieve versie van de generator. In werkelijkheid kan zo'n monster niet worden gebruikt! Maar wij gaan het doen!
Bij deze implementatie houden we op geen enkele manier toezicht op de mogelijkheid van variabele overflow. Gebruik in plaats van het int-type het _int64-type - dit is een integer-type van acht bytes.
priemgetallen
Priemgetallen zijn getallen die zonder rest alleen door één en het getal zelf kunnen worden gedeeld. Bijvoorbeeld: 11, 3, 7.
Grijze code
Grijze code is een reeks cijfers waarbij het volgende nummer één bit verschilt van het vorige. Die. om de reeks te raden, moet je niet naar de decimale getallen kijken, maar naar hun binaire equivalenten.
Hier is een oplopende reeks getallen van 0 tot 7 in binaire code:
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7
Met behulp van de code van Gray krijgen we de volgende reeks:
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Mersenne-priemgetallen
Het 44e Mersennegetal is momenteel bekend. Uit de naam blijkt duidelijk dat deze getallen priemgetallen zijn, d.w.z. zijn alleen deelbaar door één en zichzelf. Bovendien moeten deze getallen aan de volgende formule voldoen:
Waarbij n ook een priemgetal is. Voor de eerste negen Mersenne-priemgetallen zijn de n: (2, 3, 5, 7, 13, 17, 19, 31, 61).
Bitsgewijze logische bewerkingen
We hebben al gekeken naar de logische operatoren && (AND) en || (OF). Er zijn ook bitsgewijze logische operatoren & (bitsgewijze AND) en | (bitsgewijs OF). Werk de bewerking als volgt uit:
5 && 3; // && retourneert altijd nul of één (hier 1)
5&3; // & retourneert een getal
101
011
=
001 // het resultaat is één
Dat wil zeggen dat bij deze bewerking de overeenkomstige posities van twee getallen worden vergeleken en als ze gelijk zijn, wordt 1 in het resulterende getal op deze positie geschreven, anders nul.
5 | 3; // | geeft een getal terug
101
011
=
111 // resulterend in 7
Graad van
Om een getal tot een macht te verheffen, kun je de functie pow(x,y) gebruiken. In dit geval ontvangt u xy. De functie is overbelast, waardoor deze met verschillende typen kan worden gebruikt. Als u de functie pow() wilt gebruiken, moet u het headerbestand math.h opnemen.
Andere generatoren voor willekeurige getallen
Naast de lineaire congruente generator zijn er nog vele andere. Bijvoorbeeld de Mersenne Vortex, uitgevonden door twee Japanse wetenschappers (ik herinner me hun namen niet) in 1997. Het heeft een zeer lange (heel lange, op zijn zachtst gezegd) periode. Trouwens, de Mersenne-vortex gebruikt een lineaire congruente generator om het zaad te plaatsen.
Bij het versleutelen worden willekeurige nummergeneratoren gebruikt. Maar hier worden speciale generatoren gebruikt: cryptografisch beveiligde pseudo-willekeurige getalgeneratoren. Bijvoorbeeld een blokcijfer, een stroomcijfer, dat is ontwikkeld op basis van het Vernam-cijfer.
Opdrachten:
Implementeer willekeurige nummergeneratoren op basis van de lineaire cogruente methode. Gebruik de volgende parameters:
m = 232; a = 1664525; c = 1013904223. Deze parameters werden gebruikt in het generatorimplementatievoorbeeld in een oud Fortran-boek.
m = 232; a= 214013; c = 2531011; Deze parameters worden gebruikt bij de implementatie van de methode in Visual C++. In dit geval worden de meest significante bits 30..16 genomen. Het zijn de bovenste delen die worden genomen, omdat bij de lineaire congruente methode zijn de lagere bits veel minder willekeurig. Omdat we nog niet weten hoe we specifieke bits moeten nemen, kun je het hele nummer gebruiken.
Kies voor m een van de Mersenne-getallen. Begin klein (23-1.25-1). Probeer 231-1 en 261-1 te vervangen.
