Generator av slumptal baserat på kommentarer. Generator av slumptal
Observera att densitetskurvan för fördelningen av slumptal helst skulle se ut som den som visas i fig. 22.3. Det vill säga, i det ideala fallet innehåller varje intervall samma antal punkter: N i = N/k , var N- det totala antalet poäng, k- antalet intervaller, i= 1,…, k .
genereras av en idealgenerator teoretiskt
Man bör komma ihåg att generering av ett godtyckligt slumptal består av två steg:
- generering av ett normaliserat slumptal (det vill säga jämnt fördelat från 0 till 1);
- konvertera normaliserade slumptal r i till slumpmässiga siffror x i, som distribueras enligt den erforderliga användarlagen (godtycklig) distribution eller i det erforderliga intervallet.
Slumptalsgeneratorer är indelade i:
- fysisk;
- tabellform;
- algoritmisk.
Fysisk RNG
Ett exempel på en fysisk RNG är: ett mynt (huvuden - 1, svansar - 0); tärningar; en trumma med en pil uppdelad i sektorer med siffror; hårdvarubrusgenerator (HS), som används som en bullrig termisk enhet, till exempel en transistor (Fig. 22.4-22.5).
| Uppgiften "Generera slumptal med hjälp av ett mynt" | |
|
Använd ett mynt för att generera ett slumpmässigt 3-siffrigt nummer jämnt fördelat från 0 till 1. Precisionen är tre decimaler. |
|
Det första sättet att lösa problemet
Rita ett intervall från 0 till 1. Läs siffrorna i följd från vänster till höger, dela intervallet på mitten och välj varje gång en av delarna av nästa intervall (om det tappade 0, sedan det vänstra, om det tappade 1, sedan den högra). Således kan du komma till vilken punkt som helst i intervallet, så exakt du vill. Så, 1 : intervallet halveras - och, - höger halva väljs, intervallet minskas:. Nästa nummer, 0 : intervallet halveras - och, - vänster halva är vald, intervallet minskas:. Nästa nummer, 0 : intervallet halveras - och, - vänster halva är vald, intervallet minskas:. Nästa nummer, 1 : intervallet halveras - och, - höger halva väljs, intervallet minskas:. Genom villkoret för problemets noggrannhet har lösningen hittats: det är vilket tal som helst från intervallet, till exempel 0,625. I princip, om du närmar dig strikt, måste uppdelningen av intervallen fortsätta tills de vänstra och högra gränserna för det hittade intervallet SAMMANstämmer varandra med en noggrannhet på den tredje decimalen. Det vill säga, ur noggrannhetssynpunkt kommer det genererade numret inte längre att kunna särskiljas från vilket nummer som helst från det intervall i vilket det är beläget.
Det andra sättet att lösa problemet
|
RNG i tabellform
Tabellformade RNG:er använder speciellt sammanställda tabeller som innehåller verifierade okorrelerade, det vill säga oberoende av varandra, tal som en källa till slumpmässiga tal. Tabell 22.1 visar ett litet fragment av en sådan tabell. Genom att gå igenom tabellen från vänster till höger uppifrån och ned kan du få slumptal jämnt fördelade från 0 till 1 med det antal decimaler som krävs (i vårt exempel använder vi tre decimaler för varje nummer). Eftersom siffrorna i tabellen inte är beroende av varandra kan tabellen passeras på olika sätt, till exempel uppifrån och ned, eller från höger till vänster, eller säg att du kan välja nummer som är i jämna positioner.
| Tabell 22.1. Slumpmässiga siffror. Jämnt fördelade från 0 till 1 slumptal |
||||||||||||||||||||||||||||||||||||||||||||
| Slumpmässiga siffror | Jämnt fördelat från 0 till 1 slumptal |
|||||||
| 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 |
Fördelen med denna metod är att den ger verkligt slumpmässiga tal, eftersom tabellen innehåller verifierade okorrelerade tal. Nackdelar med metoden: det krävs mycket minne för att lagra ett stort antal siffror; stora svårigheter med att generera och kontrollera sådana tabeller, upprepningar när du använder en tabell garanterar inte längre slumpmässigheten i den numeriska sekvensen och därför tillförlitligheten av resultatet.
Det finns en tabell som innehåller 500 absolut slumpmässiga verifierade siffror (hämtad från boken av I. G. Venetsky, V. I. Venetskaya "Grundläggande matematiska och statistiska begrepp och formler i ekonomisk analys").
Algoritmisk RNG
Siffrorna som genereras med dessa RNG:er är alltid pseudoslumpmässiga (eller kvasi-slumpmässiga), det vill säga varje efterföljande genererat nummer beror på det föregående:
r i + 1 = f(r i) .
Sekvenser som består av sådana siffror bildar loopar, det vill säga det finns nödvändigtvis en cykel som upprepas ett oändligt antal gånger. De upprepade cyklerna kallas perioder.
Fördelen med RNG-data är hastighet; generatorer kräver praktiskt taget inga minnesresurser, de är kompakta. Nackdelar: talen kan inte helt kallas slumpmässiga, eftersom det finns ett beroende mellan dem, liksom närvaron av perioder i sekvensen av kvasi-slumpmässiga tal.
Överväg flera algoritmiska metoder för att erhålla en RNG:
- mellersta kvadratmetoden;
- metod för mellanprodukter;
- blandningsmetod;
- linjär kongruent metod.
Mean square metod
Det finns ett fyrsiffrigt nummer R 0. Denna siffra kvadreras och skrivs in R 1 . Längre ifrån R 1 tas den mellersta (fyra mittersta siffror) - ett nytt slumptal - och skrivs in R 0. Därefter upprepas proceduren (se fig. 22.6). Observera att det faktiskt inte är nödvändigt att ta som ett slumptal ghij, a 0.ghij- med en nolla och en decimalkomma tilldelad till vänster. Detta faktum återspeglas som i fig. 22.6 och i efterföljande liknande figurer.
 |
Nackdelar med metoden: 1) om vid någon iteration numret R 0 blir lika med noll, sedan urartar generatorn, så det är viktigt med rätt val av initialvärde R 0; 2) generatorn kommer att upprepa sekvensen igenom M n steg (i bästa fall), var n- sifferkapacitet R 0 , M- talsystemets bas.
Till exempel, i fig. 22,6: om nummer R 0 kommer att representeras i binär notation, sekvensen av pseudoslumptal kommer att upprepas i 2 4 = 16 steg. Observera att upprepning av sekvensen kan ske tidigare om det initiala numret inte är väl valt.
Metoden som beskrivs ovan föreslogs av John von Neumann och går tillbaka till 1946. Eftersom denna metod visade sig vara opålitlig, övergavs den snabbt.
Metod för mellanprodukter
siffra R 0 multipliceras med R 1, från det erhållna resultatet R 2 extrahera mitten R 2 * (detta är ett annat slumptal) och multiplicerat med R 1 . Alla efterföljande slumptal beräknas med detta schema (se fig. 22.7).
 |
Omrörningsmetod
Blandningsmetoden använder operationer för att cykliskt flytta innehållet i en cell till vänster och höger. Tanken med metoden är följande. Låt cellen lagra fröet R 0. Om vi cykliskt förskjuter cellens innehåll åt vänster med 1/4 av cellens längd får vi ett nytt nummer R 0 *. Likaså cykliskt skifta innehållet i en cell R 0 till höger med 1/4 av celllängden får vi det andra talet R 0 **. Summan av siffror R 0 * och R 0 ** ger ett nytt slumptal R 1 . Ytterligare R 1 är inskrivet R 0, och hela operationssekvensen upprepas (se figur 22.8).
 |
Observera att antalet som härrör från summeringen R 0 * och R 0 **, kanske inte passar helt i cellen R 1 . I detta fall ska extra siffror kasseras från det mottagna numret. Låt oss förklara detta för fig. 22.8, där alla celler representeras av åtta binära siffror. Låt vara R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , då R 0 * + R 0 ** = 100110010 2 = 306 10 ... Som du kan se upptar talet 306 9 siffror (i det binära talsystemet), och cellen R 1 (gilla R 0) kan innehålla maximalt 8 bitar. Därför innan du anger värdet i R 1 är det nödvändigt att ta bort en "extra", biten längst till vänster från talet 306, som ett resultat av vilket i R 1 blir inte 306, utan 00110010 2 = 50 10. Observera också att i språk som Pascal, "trunkering" av extra bitar när en cell svämmar över sker automatiskt i enlighet med den specificerade typen av variabel.
Linjär kongruent metod
Den linjära kongruenta metoden är en av de enklaste och mest använda procedurerna för att simulera slumptal. Denna metod använder moden ( x, y), som returnerar resten av det första argumentet dividerat med det andra. Varje efterföljande slumptal beräknas baserat på föregående slumptal med hjälp av följande formel:
r i+ 1 = mod ( k · r i + b, M) .
En sekvens av slumptal som erhålls med denna formel kallas linjär kongruent sekvens... Många författare kallar en linjär kongruent sekvens för b = 0 multiplikativ kongruent metod, och kl b ≠ 0 blandad kongruent metod.
För en högkvalitativ generator måste du välja lämpliga koefficienter. Det är nödvändigt att antalet M var ganska stor, eftersom perioden inte kan ha fler M element. Å andra sidan är uppdelningen som används i denna metod en ganska långsam operation, så det skulle vara logiskt för en binär dator att välja M = 2 N, eftersom att hitta resten av divisionen i detta fall reduceras inuti datorn till en binär logisk operation "AND". Det är också vanligt att välja det största primtalet M mindre än 2 N: i speciallitteraturen är det bevisat att i detta fall de minst signifikanta bitarna av det resulterande slumptalet r i+ 1 beter sig lika slumpmässigt som de äldre, vilket har en positiv effekt på hela sekvensen av slumptal som helhet. Ett exempel är ett av Mersenne-nummer lika med 2 31 - 1, och därmed M= 2 31 - 1.
Ett av kraven för linjära kongruenta sekvenser är största möjliga periodlängd. Periodens längd beror på värdena M , k och b... Teoremet som vi presenterar nedan låter oss avgöra om det är möjligt att uppnå en period med maximal längd för specifika värden M , k och b .
Sats... Linjär kongruent sekvens definierad av siffror M , k , b och r 0, har en längdperiod M om och endast om:
- siffrorna b och Mömsesidigt enkelt;
- k- 1 multipel sid för varje enkelt sid som är en divisor M ;
- k- 1 multipel av 4 om M multipel av 4.
Låt oss slutligen avsluta med ett par exempel på hur man använder den linjära kongruentialmetoden för att generera slumptal.
Det visade sig att en serie pseudoslumptal genererade från data från exempel 1 kommer att upprepas varje M/ 4 nummer. siffra q ställs in godtyckligt innan beräkningarna påbörjas, men man bör komma ihåg att serien ger intryck av att vara slumpmässig för stora k(vilket innebär att q). Resultatet kan förbättras något om b udda och k= 1 + 4 q - i det här fallet kommer raden att upprepas varje M tal. Efter ett långt letande k forskarna bestämde sig för värdena 69069 och 71365.
En slumptalsgenerator som använder data från exempel 2 kommer att producera slumpmässiga icke-repeterande tal med en period på 7 miljoner.
Den multiplikativa metoden för att generera pseudo-slumpmässiga tal föreslogs av D. H. Lehmer 1949.
Kontrollera kvaliteten på generatorn
Kvaliteten på hela systemet och noggrannheten i resultaten beror på kvaliteten på RNG. Därför måste den slumpmässiga sekvensen som genereras av RNG:n uppfylla ett antal kriterier.
De kontroller som utförs är av två typer:
- kontroller för enhetlig distribution;
- kontrollerar statistiskt oberoende.
Kontroller av enhetlighet i distributionen
1) RNG bör producera nära följande värden av statistiska parametrar som är karakteristiska för en enhetlig slumpmässig lag:
2) Frekvenstest
Frekvenstestet låter dig ta reda på hur många nummer som faller in i intervallet (m r σ r ; m r + σ r) det vill säga (0,5 - 0,2887; 0,5 + 0,2887) eller slutligen (0,2113; 0,7887). Eftersom 0,7887 - 0,2113 = 0,5774 drar vi slutsatsen att i en bra RNG bör cirka 57,7% av alla tappade slumptal falla in i detta intervall (se fig. 22.9).
vid kontroll av det för ett frekvenstest
Det är också nödvändigt att ta hänsyn till att antalet siffror som faller in i intervallet (0; 0,5) bör vara ungefär lika med antalet siffror som faller in i intervallet (0,5; 1).
3) Chi-kvadrattest
Chi-kvadrattest (χ 2 test) är ett av de mest kända statistiska testerna; det är den huvudsakliga metoden som används i kombination med andra kriterier. Chi-kvadrattestet föreslogs 1900 av Karl Pearson. Hans anmärkningsvärda arbete anses vara grunden för modern matematisk statistik.
För vårt fall kommer chi-kvadrattestet att tillåta oss att ta reda på hur mycket verklig RNG:n ligger nära RNG-standarden, det vill säga om den uppfyller kravet på enhetlig distribution eller inte.
Frekvensdiagram referens RNG visas i fig. 22.10. Eftersom distributionslagen för referens-RNG är enhetlig, är den (teoretiska) sannolikheten sid i slå in siffror i intervallet (alla dessa intervaller k) är lika med sid i = 1/k ... Och därmed i var och en av k intervaller kommer att falla slät på sid i · N tal ( NÄr det totala antalet genererade nummer).
En riktig RNG kommer att producera siffror fördelade (och inte nödvändigtvis jämnt!) k intervaller och varje intervall kommer att innehålla n i siffror (i summan n 1 + n 2 + ... + n k = N ). Hur kan vi avgöra hur bra den testade RNG är och hur nära referensen? Det är ganska logiskt att överväga kvadraterna av skillnaderna mellan det mottagna antalet siffror. n i och "referens" sid i · N ... Låt oss lägga till dem, och som ett resultat får vi:
χ 2 exp. = ( n 1 - sid 1 · N) 2 + (n 2 - sid 2 N) 2 + ... + ( n k sid k · N) 2 .
Det följer av denna formel att ju mindre skillnaden är i var och en av termerna (och därmed ju mindre värdet på χ 2 exp.), desto starkare fördelningen av slumptal som genereras av den verkliga RNG tenderar att vara enhetlig.
I det föregående uttrycket tilldelas var och en av termerna samma vikt (lika med 1), vilket i själva verket kanske inte motsvarar verkligheten; därför, för chi-kvadratstatistiken, är det nödvändigt att normalisera var och en i-th term genom att dividera den med sid i · N :
Slutligen skriver vi det resulterande uttrycket mer kompakt och förenklar det:
Vi har fått fram värdet av chi-kvadrattestet för experimentell data.
Tabell 22.2 ges teoretisk chi-kvadratvärden (χ 2 teori), där ν = N- 1 är antalet frihetsgrader, sidÄr den användardefinierade konfidensnivån som anger hur mycket RNG ska uppfylla kraven för enhetlig distribution, eller sid detta är sannolikheten att experimentvärdet för χ 2 exp. kommer att vara mindre än den tabellerade (teoretiska) χ 2-teorin. eller lika med honom.
| Tabell 22.2. Några procentenheter av χ 2-fördelningen |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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 sid+ 2/3 x 2 sid- 2/3 + O(1 / sqrt ( ν )) | ||||||
| x sid = | –2.33 | –1,64 | –0,674 | 0.00 | 0.674 | 1.64 | 2.33 |
Anses acceptabelt sid från 10 % till 90 %.
Om χ 2 exp. mycket mer än χ 2 teorin. (det är sid- bra), sedan generatorn inte tillfredsställer enhetlig fördelningskrav, eftersom de observerade värdena n i gå för långt ifrån teoretiska sid i · N och kan inte betraktas som slumpmässigt. Med andra ord är konfidensintervallet så stort att begränsningarna på siffrorna blir mycket lösa, kraven på siffrorna är svaga. I detta fall kommer ett mycket stort absolut fel att observeras.
Även D. Knut noterade i sin bok "Konsten att programmera" att ha χ 2 exp. liten är också i allmänhet inte bra, även om det vid första anblicken verkar underbart ur enhetlighetssynpunkt. Ta faktiskt en serie siffror 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, ... - de är idealiska ur synvinkel enhetlighet och χ 2 exp. kommer att vara praktiskt taget noll, men det är osannolikt att du känner igen dem som slumpmässiga.
Om χ 2 exp. mycket mindre än χ 2 teorin. (det är sid- lite), sedan generatorn inte tillfredsställer kravet på en slumpmässig enhetlig fördelning, eftersom de observerade värdena n i för nära teoretiskt sid i · N och kan inte betraktas som slumpmässigt.
Men om χ 2 exp. ligger i ett visst intervall, mellan två värden på χ 2 teor. som motsvarar t.ex. sid= 25 % och sid= 50%, då kan vi anta att värdena för slumptal som genereras av sensorn är helt slumpmässiga.
Dessutom bör man komma ihåg att alla värderingar sid i · N måste vara tillräckligt stor, till exempel fler än 5 (får ut empiriskt). Först då (med ett tillräckligt stort statistiskt urval) kan de experimentella förhållandena anses vara tillfredsställande.
Så verifieringsproceduren är som följer.
Statistiska oberoende tester
1) Kontrollera frekvensen av förekomsten av en siffra i en sekvens
Låt oss titta på ett exempel. Det slumpmässiga talet 0,2463389991 består av siffrorna 2463389991 och talet 0,5467766618 består av siffrorna 5467766618. Kombinerar vi siffrornas sekvenser, har vi: 246338697966418.
Det är klart att den teoretiska sannolikheten sid i nedfall i-te siffran (från 0 till 9) är 0,1.
2) Kontrollera utseendet på serier med identiska nummer
Låt oss beteckna med n L antal serier av på varandra följande siffror av längd L... Allt måste kontrolleras L från 1 till m, var mÄr ett användarspecificerat nummer: det maximala antalet identiska siffror i en serie.
I exemplet "24633899915467766618" hittades 2 serier av längden 2 (33 och 77), dvs. n 2 = 2 och 2 serie 3 lång (999 och 666), det vill säga n 3 = 2 .
Sannolikheten för förekomsten av en serie med en längd på Lär lika med: sid L= 9 10 - L (teoretisk). Det vill säga, sannolikheten för en serie med ett tecken lång är: sid 1 = 0,9 (teoretiskt). Sannolikheten för en serie med två tecken långa är: sid 2 = 0,09 (teoretiskt). Sannolikheten för en rad med tre tecken lång är: sid 3 = 0,009 (teoretiskt).
Till exempel är sannolikheten för en serie på ett tecken lång sid L= 0,9, eftersom det bara kan finnas ett tecken av 10, och det finns 9 tecken totalt (noll räknas inte). Och sannolikheten för att två identiska symboler "XX" kommer att förekomma i en rad är 0,1 · 0,1 · 9, det vill säga sannolikheten för 0,1 att symbolen "X" kommer att dyka upp i den första positionen multipliceras med sannolikheten 0,1 att samma symbolen kommer att visas i den andra positionen "X" och multiplicerad med antalet sådana kombinationer 9.
Frekvensen för seriens utseende beräknas enligt den tidigare analyserade "chi-kvadrat"-formeln med hjälp av värdena sid L .
Notera: generatorn kan kontrolleras många gånger, men kontrollerna är inte kompletta och garanterar inte att generatorn producerar slumpmässiga siffror. Till exempel kommer en generator som utfärdar sekvensen 12345678912345 ... att anses vara idealisk under kontroller, vilket uppenbarligen inte är helt sant.
Avslutningsvis noterar vi att det tredje kapitlet i Donald E. Knuths bok "Konsten att programmera" (volym 2) är helt ägnat åt studiet av slumptal. Den utforskar olika metoder för att generera slumptal, statistiska kriterier för slumpmässighet och konvertering av enhetligt fördelade slumptal till andra typer av slumpvariabler. Mer än tvåhundra sidor har ägnats åt presentationen av detta material.
Nummer följer med oss överallt - hus- och lägenhetsnummer, telefon, bil, pass, plastkort, datum, e-postlösenord. Vi väljer några kombinationer av siffror själva, men vi får de flesta av dem slumpmässigt. Utan att inse detta använder vi slumpmässigt genererade siffror varje dag. Om vi kommer med PIN-koder, så genereras unika koder för ett kredit- eller lönekort av pålitliga system som utesluter tillgång till lösenord. Slumptalsgeneratorer ger skydd inom områden som kräver bearbetningshastighet, säkerhet och oberoende bearbetning.
Processen att generera pseudoslumptal är föremål för vissa lagar och har använts under lång tid, till exempel vid lotterier. På senare tid genomfördes dragningar med hjälp av lotteritrummor eller lottdragningar. Nu i många länder bestäms de vinnande numren för statliga lotterier exakt av en uppsättning genererade slumptal.
Metodfördelar
Så en slumptalsgenerator är en oberoende modern mekanism för att slumpmässigt bestämma kombinationer av tal. Det unika och perfekta med denna metod ligger i omöjligheten av extern inblandning i processen. Generatorn är en uppsättning program byggda till exempel på brusdioder. Enheten genererar en ström av slumpmässiga ljud, vars nuvarande värden omvandlas till siffror och formkombinationer.
Att generera siffror ger omedelbara resultat - det tar några sekunder att slutföra kombinationen. Om vi pratar om lotterier kan deltagarna direkt ta reda på om lottnumret sammanfaller med det vinnande. Detta gör att dragningar kan hållas så ofta som deltagarna vill. Men den största fördelen med metoden är dess oförutsägbarhet och omöjlighet att beräkna algoritmen för att välja tal.
Hur pseudoslumptal genereras
Faktum är att de slumpmässiga talen inte är slumpmässiga - serien börjar med ett givet tal och genereras av en algoritm. En pseudoslumptalsgenerator (PRNG eller PRNG - pseudoslumptalsgenerator) är en algoritm som genererar en sekvens av till synes orelaterade tal som vanligtvis är likformigt fördelade. Inom datavetenskap används pseudo-slumptal i många applikationer: i kryptografi, simulering, Monte Carlo, etc. Kvaliteten på resultatet beror på egenskaperna hos PRNG.
Genereringskällan kan vara fysiskt brus från kosmisk strålning till brus i ett motstånd, men sådana enheter används nästan aldrig av nätverkssäkerhetsapplikationer. Kryptografiska applikationer använder speciella algoritmer som genererar sekvenser som inte kan vara statistiskt slumpmässiga. En väl vald algoritm låter dig dock få talserier som klarar de flesta slumpmässighetstester. Upprepningsperioden i sådana sekvenser är större än arbetsintervallet från vilket siffrorna tas.
Många moderna processorer innehåller en PRNG, till exempel RdRand. Alternativt skapas uppsättningar av slumpmässiga nummer och publiceras i en engångsblock (ordbok). Källan till siffrorna i det här fallet är begränsad och ger inte fullständig nätverkssäkerhet.
PRNG historia
Brädspelet Senet, som var utbrett i det antika Egypten 3500 f.Kr., kan betraktas som prototypen för slumptalsgeneratorn. Enligt förutsättningarna deltog två spelare, dragen bestämdes genom att kasta fyra platta svartvita pinnar - de liknade dåtidens PRNG. Pinnarna kastades samtidigt, och poängen räknades: om en ramlade med den vita sidan, 1 poäng och ett extra drag, två vita - två poäng, och så vidare. Den maximala poängen på fem poäng erhölls av spelaren som kastade ut fyra pinnar med den svarta sidan.
ERNIE-generatorn har använts i lotteri i Storbritannien i många år idag. Det finns två huvudsakliga metoder för att generera vinnande nummer: linjärt kongruent och additivt kongruent. Dessa och andra metoder är baserade på principen om slumpmässigt val och tillhandahålls av programvara som oändligt producerar tal, vars sekvens är omöjlig att gissa.
PRNG fungerar kontinuerligt, till exempel i spelautomater. Enligt amerikansk lag är detta ett krav som alla programvaruleverantörer måste följa.
Vi har en talföljd som består av praktiskt taget oberoende element som lyder en given fördelning. Vanligtvis jämnt fördelat.
Det finns olika sätt och sätt att generera slumptal i Excel. Tänk bara på de bästa.
Slumptalsfunktion i Excel
- Funktionen RAND returnerar ett slumpmässigt, jämnt fördelat reellt tal. Det kommer att vara mindre än 1, större än eller lika med 0.
- Funktionen RANDBETWEEN returnerar ett slumpmässigt heltal.
Låt oss titta på deras användning med exempel.
Sampling av slumptal med RAND
Denna funktion kräver inga argument (RAND ()).
För att generera ett slumpmässigt reellt tal i intervallet från 1 till 5, till exempel, använder vi följande formel: = RAND () * (5-1) +1.
Det returnerade slumptalet är jämnt fördelat över intervallet.
Varje gång kalkylbladet beräknas eller ett värde ändras i någon cell i kalkylbladet, returneras ett nytt slumptal. Om du vill behålla den genererade populationen kan du ersätta formeln med dess värde.
- Vi klickar på en cell med ett slumptal.
- Välj formeln i formelfältet.
- Tryck på F9. OCH ENTER.
Låt oss kontrollera enhetligheten i fördelningen av slumptal från det första urvalet med hjälp av distributionshistogrammet.
Området för vertikala värden är frekvens. Horisontell - "fickor".
RANDBETWEEN-funktionen
Syntaxen för RANDBETWEEN-funktionen är (nedre gräns; övre gräns). Det första argumentet måste vara mindre än det andra. Annars kommer funktionen att ge ett fel. Gränserna antas vara heltal. Formeln kasserar bråkdelen.
Ett exempel på användning av funktionen:
Slumptal med precision 0,1 och 0,01:
Hur man gör en slumptalsgenerator i Excel
Låt oss skapa en slumptalsgenerator med generering av ett värde från ett visst område. Vi använder en formel av formen: = INDEX (A1: A10; INT (RAND () * 10) +1).
Låt oss skapa en slumptalsgenerator i intervallet 0 till 100 med steget 10.
Välj 2 slumpmässiga värden från listan med textvärden. Använd RAND-funktionen, jämför textvärden i intervallet A1: A7 med slumpmässiga siffror.
Låt oss använda INDEX-funktionen för att välja två slumpmässiga textvärden från den ursprungliga listan.
För att välja ett slumpmässigt värde från listan, använd följande formel: = INDEX (A1: A7; SLANDMELLAN (1; ANTAL (A1: A7))).
Normalfördelning slumptalsgenerator
Funktionerna RAND och RANDBETWEEN producerar slumptal med en enhetlig fördelning. Alla värden med samma sannolikhet kan hamna i den nedre gränsen för det begärda intervallet och i det övre. Detta resulterar i en enorm spridning från målvärdet.
Normalfördelning innebär att de flesta av de genererade siffrorna är nära målet. Låt oss korrigera formeln RANDMELLAN och skapa en datamatris med normalfördelning.
Kostnaden för varor X är 100 rubel. Hela partiet som produceras är föremål för normalfördelning. Slumpvariabeln följer också en normal sannolikhetsfördelning.
Under dessa förhållanden är medelvärdet för intervallet 100 rubel. Låt oss skapa en array och bygga en graf med normalfördelning med en standardavvikelse på 1,5 rubel.
Vi använder funktionen: = NORMINV (RAND (); 100; 1,5).
Excel beräknade vilka värden som ligger inom sannolikhetsområdet. Eftersom sannolikheten för att producera en produkt med en kostnad på 100 rubel är maximal, visar formeln värden nära 100 oftare än andra.
Låt oss gå vidare till att bygga en graf. Först måste du skapa en tabell med kategorier. För att göra detta, låt oss dela upp arrayen i punkter:
Baserat på erhållen data kommer vi att kunna bilda ett diagram med normalfördelning. Värdeaxeln är antalet variabler i intervallet, kategoriaxeln är perioderna.
Om du har organiserat har du förmodligen stött på svårigheten att utse en slumpmässig vinnare. Som regel används i sådana situationer en populär tjänst. Random.org... Du kan se motsvarande skärmdumpar med dess resultat när du tillkännager vinnarna av tävlingar som hålls på VKontakte, etc. Idag föreslår vi att vi ska överväga detta projekt lite mer i detalj, särskilt eftersom nummergeneratorn i Random är långt ifrån dess enda funktion.
Du hittar en lista över alla funktioner på huvudsidan. Det finns två typer av tjänster som kan användas för att hålla ritningar slumpmässigt: betalda och gratis. De är betecknade som GRATIS och BETALDA tjänster. I det första fallet får du bara resultatet. I den andra metoden är det dessutom möjligt att spara alla resultat + tjänsten kommer att skapa ett officiellt provtagningsprotokoll.
Många läsare kanske argumenterar hur en dator (maskin) genererar slumptal? Och faktiskt, om vi tar majoriteten, då talar vi om pseudo-slumpmässiga värden, det vill säga värdena beräknas med matematiska funktioner, det vill säga på ett förutsägbart sätt. Tricket med denna slumpmässiga tjänst är att information läses från atmosfäriskt brus, vilket gör att du kan få verkligt slumpmässiga siffror. Random.org skapades 1998 av Mads Haahr, doktor vid Dublin School of Computer Science and Statistics. Nu används projektet aktivt i lotterier, tävlingar, ansökningar, vetenskap m.m.
Gratis slumpmässigt i tjänsten
I de flesta fall räcker det fria alternativet. Det viktigaste är att ha en deltagarlista. Samtidigt kan du välja en av två kampanjer för utlottningen av priser på Random.org:
- genom en slumptalsgenerator;
- genom att välja från listor;
Med hjälp av formen för nummergeneratorn
Låt oss säga att du har en viss lista över personer som deltar i tävlingen på din dator. Till höger på huvudsidan hittar du en widget där du måste ställa in parametrar. I fältet minsta antal (Min) lägg en (1), i maximum - ange det totala antalet deltagare. Klicka sedan på knappen "Generera" för att generera det vinnande numret.
Förresten, precis nedanför på huvudsidan finns ett objekt "Integer Generator" där du kan generera en sekvens av flera slumptal på Random.org. Det finns lite fler parametrar. Detta kan vara praktiskt om du vill utse mer än en vinnare i en dragning.
Använder listgeneratorn
I den översta menyn, gå till "Listor och mer" och välj alternativet "List Randomizer" (eller hitta det på huvudsidan). Ett nytt fönster öppnas där du måste ange alla dina deltagare och klicka på knappen "Randomisera". Programmet kommer att visa en slutlig lista där de angivna personerna kommer att placeras slumpmässigt. Den första personen på listan är vinnaren.
Förutom att sortera listan kommer tjänsten Random.org att visa samplingstiden + din IP. Du kan ta en skärmdump av skärmen och visa deltagarna så att de kan se att alla fanns med på listan, och valet av vinnaren skedde vid utlovad tid.
Förutom dessa två Random.org-generatorer har projektet några fler intressanta gratismarker:
- myntkastningssimulator;
- slumpmässiga resultat av kastade tärningar;
- Generator av nummer för lotterier;
- bildandet av en sekvens av tal (inklusive icke-upprepande);
- generering av slumpmässiga teckensträngar (och lösenord);
- använda olika funktioner av slumptal;
- få godtyckliga datum, geokoordinater och mycket mer.
Betaltjänstfunktioner
Om du tänker använda stora priser, eller om det är många som deltar i det, kommer du att vara intresserad av ett betalt prov så att resultaten från Random.orgs slumptalsgenerator sparas.
Priset beror på antalet deltagare. Om deras antal är mindre än femhundra personer, kommer det att kosta $ 4,95. Om 1000 deltagare - $ 8,95. Du kan titta på skärmdumpen mer detaljerat:
Sidwidgets
Dessutom erbjuder Random-tjänsten ytterligare verktyg. För att se dem, gå till "webbverktyg" i toppmenyn. Följande alternativ kommer att vara tillgängliga här:
- Widgets för dina sidor. På den här sidan kan du skapa widgets. Systemet genererar en speciell kod som du placerar i ditt internetprojekt;
- API för automatiserade klienter. Den här sidan beskriver hur man ansluter gränssnittet till Random.org via JSON-RPC;
- HTTP API används för att visa ett slumptal i koden;
- Förbjudna värdar. Lista över förbjudna värdar.
Produktion
Så, Random.org-nummergeneratorn är ett utmärkt alternativ för att utse en vinnare i en pågående dragning eller tävling. Det kommer att generera ett slumpmässigt antal baserat på antalet deltagare, plus att du kan välja en av provtagningsmetoderna - ett numeriskt värde eller en lista. Dessutom, när du använder tjänsten, kommer ingen att tvivla på förekomsten av speciella "lurande" gnisslor som kan påverka valet av vinnare. Utöver onlineversionen finns även en slumpgeneratorapplikation med olika funktioner. I allmänhet är detta ett av kultprojekten och verkligen användbara.
Idag ska vi ta en titt på de bästa slumptalsgeneratorerna för tävlingen. Administratörer av grupper i sociala nätverk, såväl som Instagram och bloggare håller ofta tävlingar och olika lotterier, där olika priser dras till sina prenumeranter och besökare på ett visst datum. Tävlingskrav har ofta ett antal identiska villkor där deltagaren måste utföra vissa handlingar, samt gilla, prenumerera på kanalen och reposta material på sidan. Därefter ska bloggaren eller administratören slumpmässigt utse en vinnare bland de som har uppfyllt villkoren.
För att välja en vinnare på måfå finns det speciella tjänstesidor som ger denna möjlighet. Du kan göra detta direkt på dina sidor i sociala nätverk och bloggar, utan att tillgripa betald programvara eller tjänster från programmerare. Det är möjligt att utse vinnaren slumpmässigt utan kunskap om några speciella vetenskaper. De flesta av dessa slumptalsgeneratorer är gratis och har ett enkelt gränssnitt, och är även tillgängliga även för oerfarna användare.
Många slumpnummertjänster fungerar på samma princip:
- G - betyg.
- V är vikten av faktorn som påverkar vinnarens betyg.
- S är ett slumptal.
- Med den inkluderade faktorvikten blir formeln följande - S + antal likes * V.
- Generatorns arbete förändras något när du lägger till reposts - S + likes * V + reposts * V.
Principen för att beräkna generatorn förändras i närvaro av andra faktorer, det kommer inte att vara möjligt att ta hänsyn till allt.
Fanpage Karma är en av de enklare generatorerna av slumpmässiga vinnare
En mycket bekväm och tillgänglig webbplats för användare http://www.fanpagekarma.com/, som tillhandahåller deras verktyg gratis. Det finns en liten nackdel - sidan är på engelska, men detta är lätt att hantera med hjälp av tipsen som kommer att beskrivas nedan.
Du behöver bara ange en länk till sidan i det gula fältet med en pil och tjänsten kommer automatiskt att göra allt arbete för att utse vinnaren av tävlingen. Det är fantastiskt, men du behöver inte samla medlemsnamn i stora listor och tillhandahålla dem till tjänsten, som vissa kräver.
Funpage Karma slumptalsgenerator Som du kan se på bilden får vi vid utgången en detaljerad lista med fyra kategorier: gilla-markeringar och kommentarer, bara gilla-markeringar, ensamma kommentarer och kommentarer med flest gilla-markeringar. Först och främst är slumptalsgeneratorn för tävlingen bra för det sociala nätverket Facebook, den fungerar med den utan några ytterligare verktyg. Tjänsten tillhandahåller även gratis verktyg för att arbeta med rapporter och rapporter.
RandomPicker är den mest seriösa slumptalsgeneratorn
Tjänsten RandomPicker är betald, men den har alla egenskaper för att kallas det bästa verktyget i sitt slag. Om du har en stor publik med hjälp av vilken en festlig tävling (lotteri) kommer att spelas och du måste lämna in en rapport om processen att välja en kandidat till en vinnare när den är klar, då är den här tjänsten den bästa för dig , speciellt eftersom det är helt rysktalande. Gylfen i glädjen är att tjänsten är betald. Hans tjänster kostar $38 för att överskrida gratisgränsen.
Random Number Generator Random Picker RandomPicker-generatorn skapar ett speciellt samplingsprotokoll och alla resultat efter att ha fastställt vinnaren finns kvar på tjänsteservern. Detta ger ytterligare fördelar för dig, så att du kan bevisa ditt ord om mässdragningen genom att visa dina prenumeranter resultatet av slumptalsgeneratorn. Med hjälp av denna tjänst kan du skapa ett provtagningsprotokoll där deltagarna kan se att de faktiskt har tagits med i listan, samt annan information om dragningen (antal deltagare, vinnare etc.).
Hur man arbetar med RandomPicker
- För att använda tjänsten, följ länken https://www.randompicker.com/default.aspx?Culture=ru-RU och registrera dig.
- Till att börja med måste du förbereda en lista över deltagare som ska vara med i dragningen. Listan kan tillhandahållas tjänsten i olika former: Excel-tabell, CSV och handskriven lista.
- Om du har en liten tävling eller annat evenemang och deltagarlistan inte är stor, kommer RandomPicker att välja upp till 100 deltagare gratis. Om det finns fler deltagare betalas tjänsten $38. 300 tusen är det maximala antalet deltagare.
- Tjänsten är endast lämplig för att hålla rättvisa dragningar, inga manipulationer kan göras. Vinnaren utses endast en gång och ingenting kan ändras.
Random.org är en av de första nummergeneratorerna online
Tjänsten grundades 1997. Det används ofta som vinnaridentifierare för tävlingar, även om det är en enkel slumpgenerator för olika uppgifter. För att kunna använda denna tjänst är det nödvändigt att i förväg upprätta en deltagarlista. Tjänsten tillhandahåller tjänster mot en avgift och utan kostnad. I den betalda versionen kan du spara resultatet av att välja en vinnare.
Random.org tjänstens hemsida För att kunna göra ett urval av vinnaren på Random.org behöver du veta priserna för tjänsterna. Om din lista innehåller upp till 500 personer, kommer det att kosta dig i området 5 $. 1 000 deltagare kostar cirka 9 $, alla servicepriser finns på https://www.random.org/draws/pricing/.
Hur man använder tjänsten Random.org
Woobox Välj en vinnare - specialtjänst för Facebook
Detta är ett annat verktyg för att välja en slumpmässig vinnare i giveaways från det sociala nätverket Facebook. Tyvärr är generatorn endast tillgänglig för detta nätverk. För att avgöra vinnaren - logga in på ditt Facebook-konto.
Webbplatsen woobox.com - Logga nu in på denna sida - https://woobox.com/pickawinner. Du kan också registrera dig med den mest sociala. Facebook-nätverk genom att klicka på knappen med logotypen.
- Välj sedan menyn på sidan högst upp, från rullgardinsmenyn "Övriga företag" och återigen från listan välj önskad sida.
- Välj knappen "Inlägg" i den övre panelen, som öppnar en lista över dina inlägg på din Facebook-sida, välj ett inlägg med en tävling.
- Och på höger sida finns en grön "Välj en vinnare"-knapp - klicka på den.
- Du kommer till en sida med ett urval av 2 objekt - kommentarer och gilla-markeringar. Välj ett av kriterierna för att välja en vinnare och klicka igen på knappen "Välj en vinnare". Systemet kommer automatiskt att utse vinnaren slumpmässigt. Om vinnaren plötsligt valdes felaktigt eller om det finns andra skäl för att avbryta urvalsresultatet, tryck sedan på knappen "Unpicker" på höger sida för att avbryta.
Vi har granskat de bästa slumptalsgeneratorerna för onlinetävlingar med dig. Vissa kan du använda gratis, men vilken du ska välja är upp till dig.