Kaip veikia atsitiktinių skaičių generatorius? Atsitiktinių skaičių generatoriai

Ar kada nors tikrinote teiginį, kad iš 10 ruletės sukimų lyginis skaičius pasirodo 5 kartus? O gal ne kartą dalyvavote loterijose ir netgi sugebėjote laimėti? Jei pripažįstame, kad visi rezultatai yra tikrai atsitiktiniai, galime kalbėti apie konkretaus įvykio tikimybę.

Perfrazuodami paskutinį teiginį, pakartokime žmonių, kurie kelis mėnesius dalyvauja renginiuose su atsitiktiniais rezultatais, žodžius: visagalis atsitiktinumas veikia.

Taigi, kaip patikrinti, ar paskirstymo principas yra atsitiktinis? Generatorius gali susidoroti su šia užduotimi. atsitiktiniai skaičiai. Pagrindinis jo pranašumas yra tai, kad jis veikia internete, o tai reiškia, kad jis yra labai greitas ir nepriklauso nuo interneto ryšio po atsisiuntimo.

Kaip veikia atsitiktinių skaičių generatorius?

Darbui apibūdinti nereikia daug raidžių, viskas labai paprasta: reikia pasirinkti mažiausią ir didžiausią galimą skaičių, įrašyti sugeneruojamų reikšmių skaičių, jei reikia, pažymėti varnelę „Išskirti pasikartojimus“, kuri neleidžia numerių, kurie jau egzistavo, išvaizdą ir spustelėkite generavimo mygtuką. Po to kiekvienas paskesnis mygtuko paspaudimas sukurs naujas platinimo parinktis.

Kodėl to gali prireikti? Pavyzdžiui, gauti laimingi skaičiai loterijoje ar ruletėje. Be to, pseudoatsitiktinių skaičių generatorius gali imituoti loterijos statines ar monetos metimą varžyboms – galvos ir uodegos žymimos nuliu arba vienu. Bet svarbiausia, kad įkėlus puslapį nereikia interneto ryšio – kodas parašomas JavaScript ir vykdomas vartotojo pusėje, jo naršyklėje.

Šio internetinio generatoriaus veikimo patikrinimas kartais davė labai įdomių rezultatų: naudojant skaičius 0 ir 1 su 10 variantų, ne taip retai gaunamas skirstinys santykiu nuo 7 iki 3 ar net 6 identiški skaičiai sutartis.

Kam dar, be loto ir aukščiau pateiktų pavyzdžių, atsitiktinis skaičius gali būti naudingas skirstant skaičius? Bent jau spėlionių žaidimui. Tikriausiai vaikystėje žaidėte šį žaidimą: šeimininkas atspėja skaičių nuo 1 iki 100, o kiti bando atspėti. Kalbant apie šį generatorių, jūs elgiatės kaip lyderis, o kompiuteris bando atspėti, kas paslėpta.

Jūs netgi galite žaisti Jūros mūšis, iš karto gaunanti skaičių grupę nuo 0 iki 99. Šiuo atveju reikšmingiausias skaičiaus skaitmuo naudojamas kaip raidės (kurios nurodomos horizontaliai) - 0 ... 9 yra ... ir maži skaitmenys šiuo atveju pakeičia diapazoną nuo 1 iki 10, tada pridedamas tik vienas. Galbūt dabar toks požiūris neatrodo labai aiškus, bet tai yra įpročio reikalas.

Kitas įdomus būdas naudokite - patikrinkite savo intuiciją. Bandote nuspėti, kokius skaičius (po vieną ar grupėje) generatorius generuos, paspaudžiate mygtuką ir patikrinate, kiek buvote arti teisingo rezultato. Kas žino, gal po kelių bandymų pavyks tiksliai nuspėti rezultatą?

Tačiau reikia atsižvelgti į tai, kad atsitiktinių skaičių generatorius taip vadinamas ne veltui. Dabartiniai metodai negali pateikti tikrai atsitiktinės vertės – tai priklauso nuo daugelio veiksnių, tarp kurių gali būti ir ankstesnis skaičius, Dabartinis laikas, tam tikros atminties ląstelės turinį ir kitus duomenis. Tačiau buitinėms reikmėms jų funkcionalumo dažniausiai pakanka 100 proc.

Na, tikiuosi, kad generatorių rasite plačiau nei čia aprašytos galimybės. O gal net galit pasiūlyti gera idėja išplėsti esamą funkcionalumą. Galų gale tai buvo pačios neįtikėtiniausios mintys, kurios galiausiai iš neaiškios idėjos virto tikru įsikūnijimu.

Ant makroskopinių atsitiktinių procesų naudojant tokius paprasti objektai, Kaip kauliukai, ruletės ratas arba moneta, gali būti pagrįstas atsitiktinių skaičių generatoriai. Chaoso teorija ir nestabilių dinaminių sistemų teorija gali paaiškinti duomenų nenuspėjamumą, o net makroskopinės sistemos, visiškai apibrėžtos Niutono lygtimis, praktikoje dažnai turi nenuspėjamą rezultatą, nes tai priklauso nuo pradinių sąlygų mikroskopinių detalių.

Beje, mūsų svetainėje galite sugeneruoti atsitiktinį skaičių naudodami internetinį atsitiktinių skaičių generatorių.

Kas yra atsitiktinių skaičių generatorius ir kaip jis naudoja atsitiktinius fizinius procesus?

Atsitiktinių skaičių gavimo greitis, kurio pakanka taikomoms problemoms spręsti, negali užtikrinti įrenginiai, pagrįsti atsitiktiniais makroskopiniais procesais. Todėl triukšmo šaltinis, iš kurio išgaunami atsitiktiniai bitai, yra šiuolaikinių AGNG pagrindas. Yra dviejų tipų triukšmo šaltiniai: tie, kurie yra kvantinio pobūdžio, ir tie, kurie nenaudoja kvantinių reiškinių.

Kai kurie natūralus fenomenas, pavyzdžiui, radioaktyvusis atomų skilimas, yra absoliučiai atsitiktiniai ir iš principo negali būti nuspėjami (Davisson-Germer eksperimentas gali būti laikomas vienu pirmųjų eksperimentų, įrodančių kai kurių reiškinių tikimybę), šis faktas yra įstatymus Kvantinė fizika. O iš statistinės mechanikos išplaukia, kad kiekviena sistema savo parametrais turi atsitiktiniai svyravimai, jei temperatūra nėra lygi absoliučiam nuliui.

Kompleksinis atsitiktinių skaičių generatorius.

AGS atveju „auksinis standartas“ yra kai kurie kvantiniai mechaniniai procesai, nes jie yra visiškai atsitiktiniai. Naudojant in atsitiktinių skaičių generatoriai reiškiniai apima:

• Šūvio triukšmas yra triukšmas, kurį elektros grandinėse sukelia nešėjų diskretiškumas elektros krūvis ir šis terminas taip pat reiškia triukšmą, kurį sukelia optiniai įrenginiaišviesos nešiklio diskretiškumas.
• Taip pat gali būti naudojamas spontaniškas parametrinis sklaidymas atsitiktinių skaičių generatoriai.
• Radioaktyvusis skilimas – turi kiekvieno atskiro skilimo įvykio atsitiktinumą, todėl jis naudojamas kaip triukšmo šaltinis. Dėl to į imtuvą patenka skirtingas dalelių skaičius skirtingais laiko intervalais (tai gali būti Geigerio skaitiklis arba scintiliacijos skaitiklis).

Nekvantinius reiškinius aptikti daug lengviau, bet remiantis jais atsitiktinių skaičių generatoriai, tada jie stipriai priklausys nuo temperatūros (pavyzdžiui, šiluminio triukšmo kiekis bus proporcingas temperatūrai aplinką). Tarp AGNG naudojamų procesų galima išskirti šiuos procesus:

• Šiluminis triukšmas rezistoriuje, kuris po stiprinimo sukuriamas atsitiktinės įtampos generatorius. Visų pirma, šiuo reiškiniu buvo pagrįstas skaičių generatorius Ferranti Mark 1 kompiuteryje.
• Atmosferos triukšmas, matuojamas radijo imtuvu, gali apimti ir iš kosmoso į Žemę atkeliaujančių dalelių, kurias registruoja imtuvas, priėmimą, o jų skaičius bus atsitiktinis, skirtingais laiko intervalais.
• Laikrodžių greičio skirtumas yra reiškinys, reiškiantis, kad skirtingų laikrodžių dažniai visiškai nesutaps.

Gauti iš fizinio atsitiktinio proceso atsitiktinių bitų seka, tada yra keletas būdų tai padaryti. Vienas iš jų yra tai, kad gautas signalas-triukšmas sustiprinamas, tada filtruojamas ir tiekiamas į didelės spartos įtampos lygintuvo įvestį, kad būtų gautas loginis signalas. Lyginamųjų būsenų trukmė bus atsitiktinė ir tai leidžia kurti atsitiktinių skaičių seka, matuojant šias būsenas.

Antrasis metodas yra tai, kad atsitiktinis signalas yra perduodamas į analoginio-skaitmeninio keitiklio įvestį (gali būti naudojami ir specialūs įrenginiai, ir kompiuterio garso įvestis), vaizduojantis atsitiktinių skaičių seką, dėl kurios bus suskaitmenintas. signalą ir tuo pačiu metu jį galima apdoroti programine įranga .

Kas yra atsitiktinių skaičių generatorius ir kokius kitus reiškinius jis naudoja?

Naudojant fizinius atsitiktinius procesus atsitiktinių skaičių generatoriai, leidžia gauti gerus atsitiktinius skaičius, tačiau jų gamyba yra brangi ir gana sudėtinga (tai ypač pasakytina apie tuos ANGN, kurie yra pagrįsti radioaktyvusis skilimas), tačiau yra ir kitų labiau prieinamų atsitiktinumo šaltinių:

Paprastas atsitiktinių skaičių generavimas.

Veikia skaitmeninės vaizdo kameros, kurie naudoja makroskopinių reiškinių registravimą, turėtų būti priskirti prie neįprastiausių generatorių. Pavyzdžiui, atsitiktiniams skaičiams generuoti, Silicon Graphics komanda panaudojo lavos lempos vaizdo medžiagą, nes vaškas chaotiškai keičia savo formą lempoje. Srautai iš ventiliatoriaus oro sraute arba burbuliukai akvariume taip pat gali būti naudojami kaip fotografavimo objektas.

• Vertimas

Įsivaizduokite, kad dabar 1995 m., o jūs ketinate pirmą kartą pirkti internetu. Atidarote „Netscape“ naršyklę ir gurkšnojate kavą pagrindinis puslapisĮkraunama lėtai. Jūsų kelias yra Amazon.com – naujoje internetinėje parduotuvėje, apie kurią jums papasakojo draugas. Kai ateina pirkimo užbaigimo ir asmeninių duomenų įvedimo etapas, adresas naršyklėje pasikeičia iš „http“ į „https“. Tai rodo, kad kompiuteris užmezgė šifruotą ryšį su Amazon serveriu. Dabar galite perkelti kredito kortelės informaciją į serverį nebijodami sukčių, kurie nori perimti informaciją.

Deja, jūsų pirmasis pirkimas internetu buvo pažeistas nuo pat pradžių: netrukus pastebėsite, kad tariamai saugus protokolas, kurį naršyklė naudoja ryšiui užmegzti, iš tikrųjų nėra labai saugus.

Problema ta, kad slaptieji „Netscape“ raktai nebuvo pakankamai atsitiktiniai. Jų ilgis buvo tik 40 bitų, o tai reiškia apie trilijoną galimi deriniai. Atrodo didelis skaičius, tačiau įsilaužėliams pavyko sulaužyti šiuos kodus net 1990-ųjų kompiuteriuose per maždaug 30 valandų. Tariamai atsitiktinis skaičius, kurį „Netscape“ naudojo generuodamas slaptąjį raktą, buvo pagrįstas tik tris reikšmes: paros laikas, proceso ID numeris ir motininio proceso ID numeris yra nuspėjami. Dėl šios priežasties užpuolikas sugebėjo sumažinti brutalios jėgos parinkčių skaičių ir rasti norimą raktą daug anksčiau, nei tikėjosi „Netscape“.

„Netscape“ programuotojai norėtų naudoti visiškai atsitiktinius skaičius, kad sugeneruotų raktą, tačiau nežinojo, kaip juos gauti. Priežastis ta skaitmeniniai kompiuteriai visada yra tiksliai apibrėžtoje būsenoje, kuri pasikeičia tik gavus tam tikrą komandą iš programos. Geriausia, ką galite padaryti, tai imituoti atsitiktinumą generuojant vadinamuosius pseudoatsitiktinius skaičius naudojant specialią matematinę funkciją. Tokių skaičių rinkinys iš pirmo žvilgsnio atrodo visiškai atsitiktinis, tačiau kažkas kitas, naudodamas tą pačią procedūrą, gali nesunkiai sugeneruoti lygiai tokius pačius skaičius, todėl dažniausiai jie nėra šifruojami.

Tyrėjai sugebėjo išrasti pseudoatsitiktinių skaičių generatorius, kurie, kaip nustatyta, yra kriptografiškai saugūs. Bet juos reikia pradėti nuo geros atsitiktinės sėklos, kitaip jie visada generuos tą patį skaičių rinkinį. O šiai pradinei vertei jums reikia kažko, ko tikrai neįmanoma atspėti ar numatyti.

Laimei, naudojant chaotišką visatą, kuri iš visų pusių supa griežtai deterministinį kompiuterių bitų pasaulį, nėra sunku gauti tikrai nenuspėjamas vertes. Bet kaip tiksliai tai padaryti?

Per Pastaraisiais metais yra internetinis atsitiktinių skaičių šaltinis, vadinamas Lavarand. Jis buvo sukurtas 1996 m., siekiant automatiškai generuoti atsitiktines reikšmes, apdorojant dekoratyvinės lempos nuotraukas - lavos lempą, kuri kas sekundę keičia savo išvaizdą nenuspėjamai. Nuo to laiko atsitiktinės vertės iš šio šaltinio buvo panaudotos daugiau nei milijoną kartų.

Taip pat yra sudėtingesnių aparatinės įrangos atsitiktinių skaičių generatorių, kurie registruojasi kvantiniai efektai Pavyzdžiui, fotonai atsitrenkia į veidrodį. Įprastame kompiuteryje galite gauti atsitiktinius skaičius, įrašydami nenuspėjamus įvykius, pvz., tikslų laiką, kai paspaudėte klaviatūros mygtuką. Tačiau norint gauti daug tokių atsitiktinių reikšmių, reikia paspausti daug mygtukų.

Mano kolegos ir aš iš „Intel“ nusprendėme, kad turime padaryti paprastesnį būdą. Štai kodėl daugelis mūsų mikroschemų rinkinių jau daugiau nei dešimtmetį turi analoginį aparatinės įrangos atsitiktinių skaičių generatorių. Problema ta, kad jo analoginė grandinė eikvoja energiją. Be to, sunku išlaikyti šios analoginės grandinės funkcionalumą, nes lusto gamybos procesas tobulėja ir tampa miniatiūrinis. Todėl dabar sukūrėme naują ir visiškai skaitmeninę sistemą, kuri leidžia mikroprocesoriui generuoti gausų atsitiktinių reikšmių srautą be šių problemų. Šis naujas skaitmeninis atsitiktinių skaičių generatorius netrukus pasieks jus su nauju procesoriumi.

Pirmasis „Intel“ bandymas geriausias atsitiktinių skaičių generatorius įprastuose kompiuteriuose buvo sukurtas 1999 m., kai „Intel“ pristatė mikroschemų rinkinių „Firmware Hub“ komponentą. Lusto atsitiktinių skaičių generatorius (PDF) yra analoginio žiedinio generatoriaus konstrukcija, kuri jaučia rezistorių šiluminį triukšmą, jį sustiprina ir naudoja gautą signalą palyginti lėto laikrodžio generatoriaus periodui keisti. Kiekvienai nenuspėjamai šio lėto generatoriaus „erkėlei“ mikroschema nustatė antrojo greito generatoriaus virpesių dažnį, kuris reguliariai keičia savo vertę tarp dviejų dvejetainių būsenų: 0 ir 1. Rezultatas yra nenuspėjama nulių ir vienetų seka.

Bėda ta, kad žiedinis osciliatorius, atsakingas už šiluminio signalo stiprinimą, sunaudoja per daug energijos – ir veikia nuolat, nepriklausomai nuo to, ar kompiuteriui jame reikia atsitiktinių skaičių, ar ne. Šis momentas. Šie analoginiai komponentai taip pat sukelia nepatogumų, kai įmonė keičia lustų gamybos procesą. Kas kelerius metus įmonė atnaujina savo gamybos linijas, kad būtų galima gaminti mažesnio masto traškučius. Ir kiekvieną kartą šį analoginį fragmentą reikia sukalibruoti ir išbandyti nauju būdu – šis sudėtingas ir kruopštus darbas tapo tikru galvos skausmu.

Štai kodėl 2008 m. „Intel“ nusprendė sukurti atsitiktinių skaičių generatorių, kuris veiktų tik skaitmeniniu pagrindu. Įmonės Hillsboro mieste (Oregonas, JAV) mokslininkai kartu su Dizaino laboratorijos inžinieriais Bangalore (Indija) pradėjo nagrinėti pagrindinę problemą – kaip gauti atsitiktinį bitų srautą nenaudojant analoginių grandinių.

Ironiška, bet jų siūlomas sprendimas pažeidžia pagrindinę skaitmeninio projektavimo taisyklę, kad grandinė visada turi būti konkrečioje padėtyje ir grąžinti arba loginį 0, arba 1. Žinoma, skaitmeninis elementas gali trumpai praleisti neapibrėžtoje padėtyje, persijungdamas. tarp šių dviejų verčių. Tačiau jis turi veikti itin tiksliai ir niekada neturėtų svyruoti tarp jų, antraip sukels sistemos uždelsimus ar net gedimus. Mūsų atsitiktinių bitų generatoriuje svyravimai yra savybė, o ne klaida.

Mūsų ankstesnis analoginis generatorius galėjo sukurti tik porą šimtų kilobitų atsitiktinių skaičių per sekundę, o naujasis generuoja juos maždaug 3 Gb/s greičiu. Jis prasideda renkant beveik atsitiktines dviejų keitiklių reikšmes 512 bitų blokuose. Vėliau šie blokai suskirstomi į 256 bitų skaičių poras. Žinoma, jei originalūs 512 bitų nėra visiškai atsitiktiniai, šie 256 bitų skaičiai taip pat nebus visiškai atsitiktiniai. Tačiau juos galima matematiškai sujungti ir gauti 256 bitų skaičių, kuris yra artimas idealui.

TRYS SKAIČIŲ LYGMENYS: „Intel Bull Mountain“ atsitiktinių skaičių generatorius apsaugo nuo bet kokių nuspėjamumo pokyčių per trijų etapų procesą. Pirma, skaitmeninė grandinė generuoja atsitiktinių bitų srautą. Tada „normalizatorius“ (kondicionierius) generuoja geras atsitiktines sėklas, remdamasis šiuo srautu. Trečiajame etape pseudoatsitiktinių skaičių generatorius sukuria skaitmenų srautą, skirtą naudoti programinė įranga.

Visa tai geriau iliustruoja paprasta iliustracija. Tarkime, kad sekundę atsitiktinių bitų generatorius sukuria 8 bitų šablonus, tai yra skaičius nuo 0 iki 255. Taip pat tarkime, kad šie 8 bitų skaičiai nėra visiškai atsitiktiniai. Dabar įsivaizduokite, kad, pavyzdžiui, kai kurie subtilūs grandinės trūkumai pakeičia išvesties reikšmes apatinė dalis diapazonas. Iš pirmo žvilgsnio atsitiktinių skaičių srautas atrodo geras, tačiau jei apdorosite milijonus reikšmių, pastebėsite, kad diapazono viršuje esantys skaičiai yra šiek tiek retesni nei skaičiai apačioje.

Vienas iš galimi sprendimai Problema paprasta: visada paimkite 8 bitų skaičių porą, padauginkite juos ir atmeskite aštuonis viršutinius gauto 16 bitų skaičiaus bitus. Ši procedūra pašalins iškraipymus beveik visiškai.

„Bull Mountain“ neveikia su 8 bitų skaičiais: jis veikia, kaip jau minėta, su 256 bitų skaičiais. Ir ne jų daugina, o atlieka sudėtingesnes kriptografines operacijas. Bet pagrindinė mintis ta pati. Galite galvoti apie šį etapą kaip „normalizavimą“, kad pašalintumėte tuos nukrypimus atsitiktinis pasiskirstymas skaičiai, kurie gali atsirasti grandinėje su dviem inverteriais.

Labai norime gerai miegoti naktį, todėl sukūrėme papildomą grandinę, kuri tikrina 256 bitų skaičių srautus, patenkančius į „normalizatorių“, kad jie nebūtų per daug iškreipti viena kryptimi. Jei tai randama, pažymime kaip sugedusį ir neatitinkantį standarto. Taigi operacijos atliekamos tik su kokybiškomis skaičių poromis.

Garantuoto atsitiktinumo nepakanka, jei atsitiktinės reikšmės nesukuriamos pakankamai greitai, kad atitiktų standartus. Nors aparatinės įrangos kilpa giją sukuria daug greičiau nei jos pirmtakai, kai kurioms šiuolaikinėms užduotims jos vis tiek nepakanka. Kad „Bull Mountain“ galėtų generuoti atsitiktinius skaičius taip pat greitai, kaip programinės įrangos pseudoatsitiktinių skaičių generatoriai sukuria srautą, bet tuo pačiu metu sutaupyti aukštos kokybės atsitiktinius skaičius, schemą papildėme dar vienu lygiu. Čia 256 bitų atsitiktiniai skaičiai naudojami kaip kriptografiškai saugūs atsitiktiniai skaičiai, generuojantys daug pseudoatsitiktinių 128 bitų skaičių. Kadangi 256 bitų numeriai pateikiami 3 GHz dažniu, garantuojama, kad yra pakankamai medžiagos greitai sugeneruoti kriptografinius raktus.

Naujoji instrukcija, vadinama RdRand, leidžia programai, kuriai reikia atsitiktinių skaičių, pateikti užklausą juos gaminančiai aparatūrai. Sukurta 64 bitų „Intel“ procesoriams, „RdRand“ instrukcija yra „Bull Mountain“ generatoriaus raktas. Jis ištraukia 16, 32 arba 64 bitų atsitiktines reikšmes ir įkelia jas į programos pasiekiamą registrą. „RdRand“ instrukcija buvo paskelbta visuomenei maždaug prieš metus, o pirmasis „Intel“ procesorius, palaikantis ją, bus „Ivy Bridge“. Naujasis mikroschemų rinkinys yra 37% greitesnis nei jo pirmtakas, o jo minimalių elementų dydis sumažintas nuo 32 iki 22 nanometrų. Bendras našumo padidėjimas puikiai atitinka mūsų atsitiktinių skaičių generatoriaus poreikius.

Nors lavos lempos atrodyk šauniai, jie tiks ne kiekviename interjere. Manome, kad mūsų požiūris į atsitiktinių skaičių generavimą, priešingai, ras universaliausią pritaikymą.

Kaip jau minėta, tikslaus klavišų paspaudimo laiko įrašymas anksčiau buvo naudojamas kaip patogus generatorių atsitiktinių pradinių verčių šaltinis. Tais pačiais tikslais naudojome pelės judesius ir net sektorių paieškos kietajame diske greitį. Tačiau tokie įvykiai ne visada suteikia pakankamai atsitiktinių bitų, o po tam tikro matavimo laiko šie bitai tampa nuspėjami. Dar blogiau, nes dabar gyvename serverių pasaulyje

Visi mums nutinkantys reiškiniai yra dviejų tipų – atsitiktiniai ir natūralūs. Pavyzdžiui, neturėjote pakankamai sąskaitų nusipirkti magnetofoną, o nusprendėte įsigyti grotuvą – t.y. veiksmas yra logiškas ir laukiamas. Tačiau eidamas į parduotuvę atrandi reikiamą sumą, kuri atsitiktinai pakeitė planus. Atsitiktinių skaičių generatoriaus veikimas visiškai priklauso nuo operatoriaus nurodyto mechanizmo, todėl visi išduodami skaičiai esamame įvykyje yra pseudoatsitiktiniai. Operatoriai, kurie grįžta atsitiktiniai skaičiai, nurodykite laiką, būtent sistemos laiką. Tie. Tiek pasaulyje, tiek programavime nieko nėra visiškai absoliutaus.

rand funkcija

C programavimo metu buvo išrasti įmontuoti operatoriai, norint gauti atsitiktines reikšmes, kurios duoda mums reikiamus rezultatus. Taigi, norėdami sukurti atsitiktinį skaičių, naudokite rand funkcija, kuris rand operatorius naudojami atsitiktiniams skaičiams, kurie grąžina diapazoną nuo 0 iki tam tikros konstantos, gauti. Be to, ši konstanta yra deklaruojama sistemos direktyvoje „stdlib.h“, kurioje yra pagrįsta ši randų funkcija. Šios funkcijos sintaksė paprasta: int m= rand(); tie. grąžinamas sveikasis skaičius. Praktiškai išbandę operatorių, pamatysite, kad paleidus programą pasirodantys skaičiai yra identiški. Priežiūra yra ta, kad rand operatorius dirba su tuo pačiu sistemos laiku, kuris buvo išsaugotas kompiliavimo metu. Šis generatorius atsitiktiniai skaičiai yra susieti su programos laiko keitimo algoritmu, tada viskas veikia neteisingai.

Dabar apie srandą ir atsitiktinius

Šiai problemai spręsti buvo būtina funkcija, kuri įtaisytąjį laiką atstatytų iki nulio kiekvieną kartą, kai iškviečiamas rand operatorius, ir programinės įrangos kūrėjai tai padarė. srand funkcija. Veiksmas leidžia rand funkcijai kiekvieną kartą pasiekti ne įdiegtą laikmatį, o esamą įmontuotą laikmatį, o tai atveria galimybę generatoriui tinkamai dirbti – generuoti atsitiktines reikšmes. Pastaruoju metu programuojant C++ atsitiktinių skaičių išdavimo mechanizmas buvo patobulintas dėl mikrosekundžių atsiradimo. Be to, išsiplėtė reikšmių diapazonas, o visos dabartinės naujovės buvo paverstos atsitiktine funkcija.

Kas yra atsitiktinumas kompiuteryje? Kaip generuojami atsitiktiniai skaičiai? Šiame straipsnyje mes bandėme pateikti paprastus atsakymus į šiuos klausimus.

Programinėje įrangoje ir apskritai technologijose reikia atkuriamo atsitiktinumo: atsitiktiniai skaičiai ir paveikslėliai iš tikrųjų generuojami pagal konkretų algoritmą. Tai vadinama pseudoatsitiktinumu ir panagrinėsime paprastus būdus sukuriant pseudoatsitiktinius skaičius. Straipsnio pabaigoje suformuluosime paprastą šių, atrodytų, atsitiktinių skaičių generavimo teoremą.

Nustatyti, kas tiksliai yra nelaimingas atsitikimas, gali būti gana sudėtinga. Yra testų (pvz., Kolmogorovo sudėtingumo), kurie gali suteikti tikslią tam tikros sekos atsitiktinumo reikšmę. Bet nesivarginsime, tik pabandysime sukurti skaičių seką, kuri atrodys nesusijusi viena su kita.

Dažnai reikia ne vieno skaičiaus, o kelių atsitiktinių skaičių, generuojamų nuolat. Todėl, atsižvelgiant į pradinę vertę, turime sukurti kitus atsitiktinius skaičius. Ši pradinė vertė vadinama sėkla, o kaip tai gauti, pamatysime vėliau. Kol kas susitelkime ties kitų atsitiktinių verčių kūrimu.

Atsitiktinių skaičių generavimas iš sėklos

Vienas iš būdų būtų taikyti kokią nors beprotišką matematikos formulę sėklai, tada ją pasukti tiek, kad išvesties skaičius atrodytų nenuspėjamas, ir paimti tai kaip kitos iteracijos pradžią. Vienintelis klausimas, kaip ši iškraipymo funkcija turėtų atrodyti.

Eksperimentuokime su šia idėja ir pažiūrėkime, kur ji mus nuves.

Iškraipymo funkcija paims vieną reikšmę ir grąžins kitą. Pavadinkime tai R.

R(Input) -> Output

Jei mūsų sėklos reikšmė yra 1, tada R sukurs 1, 2, 3, 4,... Tai visai neatrodo atsitiktinai, bet mes ten pasieksime. Leiskite R dabar pridėti konstantą vietoj 1.

Jei c lygus, pavyzdžiui, 7, tada gauname eilutę 1, 8, 15, 22, ... Vis tiek ne ta pati. Akivaizdu, kad mums trūksta to, kad skaičiai turėtų ne tik didėti, bet ir pasiskirstyti tam tikru diapazonu. Mums reikia savo sekos, kad grįžtume į pradžią – skaičių ratą!

Skaičių ratas

Pažiūrėkime į laikrodžio ciferblatą: mūsų eilė prasideda nuo 1 ir eina ratu iki 12. Bet kadangi dirbame kompiuteriu, tegul ten būna 0, o ne 12.

Dabar nuo 1 vėl pridėsime 7. Pažanga! Matome, kad po 12 mūsų serijos pradeda kartotis, nesvarbu, nuo kokio skaičiaus pradedame.

Čia gauname labai svarbią savybę: jei mūsų ciklas susideda iš n elementų, tai didžiausias elementų skaičius, kurį galime gauti prieš jiems pradedant kartotis, yra n.

Dabar perrašykime funkciją R, kad ji atitiktų mūsų logiką. Galite apriboti kilpos ilgį naudodami modulio operatorių arba likusios dalies operatorių.

R(x) = (x + c) % m

Šiuo metu galite pastebėti, kad kai kurie skaičiai netelpa į c. Jei c = 4 ir mes pradėtume nuo 1, mūsų seka būtų 1, 5, 9, 1, 5, 9, 1, 5, 9, ... kas, žinoma, mums netinka, nes ši seka yra absoliučiai ne atsitiktinai. Pasidaro aišku, kad skaičiai, kuriuos pasirenkame pagal kilpos ilgį ir šuolio ilgį, turi būti susieti ypatingu būdu.

Jei išbandysite keletą skirtingos reikšmės, tada galite pamatyti vieną savybę: m ir c turi būti santykinai pirminiai.

Iki šiol padarėme šuolius sudėdami, bet ką daryti, jei naudosime daugybą? Padauginkime Xį konstantą a.

R(x) = (ax + c) % m

Savybės, kurioms būtina paklusti, kad susidarytų visas ciklas, yra šiek tiek konkretesnės. Norėdami sukurti tinkamą kilpą:

1. (a - 1) turi dalytis iš visų pirminių veiksnių m
2. (a - 1) turi dalytis iš 4, jei m dalijasi iš 4

Šios savybės kartu su taisykle, kad m ir c turi būti santykinai pirminiai, sudaro Hull-Dobell teoremą. Mes nenagrinėsime jo įrodymo, bet jei paimtumėte daugybę skirtingų skirtingų konstantų reikšmių, galėtumėte padaryti tą pačią išvadą.

Sėklų pasirinkimas

Dabar atėjo laikas pakalbėti apie įdomiąją dalį: pradinės sėklos pasirinkimą. Galėtume tai padaryti pastovia. Tai gali būti naudinga tais atvejais, kai reikia atsitiktinių skaičių, bet norite, kad jie būtų vienodi kiekvieną kartą paleidžiant programą. Pavyzdžiui, kiekvienam žaidimui sukurti tą patį žemėlapį.

Kitas būdas – kiekvieną kartą paleidus programą gauti sėklą iš naujo šaltinio, pavyzdžiui, sistemos laikrodį. Tai naudinga, kai reikia viso atsitiktinio skaičiaus, pavyzdžiui, kauliukų metimo programoje.

Galutinis rezultatas

Kelis kartus pritaikę funkciją jos rezultatui, gauname pasikartojimo ryšį. Parašykime formulę naudodami rekursiją.