Tasodifiy sonlar generatorining ishlashi algoritmi. Tasodifiy raqamlar generatorlari. Chiziqli kongruent usuli

Tasodifiy raqamlar kriptografiyaning oddiy elementi bo'lib, u haqida eng kam gapiriladi, ammo qolganlari kabi muhimdir. Kriptografiyadan foydalanadigan deyarli barcha kompyuter xavfsizlik tizimlari tasodifiy raqamlarni talab qiladi - kalitlar uchun, protokollardagi noyob raqamlar va boshqalar - va bunday tizimlarning xavfsizligi ko'pincha uning tasodifiyligiga bog'liq. tasodifiy raqamlar. Agar tasodifiy sonlar generatori ishonchsiz bo'lsa, butun tizim buziladi.

Kim bilan gaplashayotganingizga qarab, tasodifiy raqamlarni yaratish ahamiyatsiz yoki imkonsiz ko'rinadi. Nazariy jihatdan bu mumkin emas. Hisoblashning otasi Jon fon Neyman shunday dedi: "Tasodifiy raqamlarni olishning arifmetik usullari borligiga ishongan har bir kishi, albatta, gunoh qiladi". U tasodifiy biror narsani olish mumkin emasligini aytdi har jihatdan so'zlar kompyuter kabi deterministik hayvonning chiqishidir. Bu haqiqat, lekin xayriyatki, biz qila oladigan ba'zi narsalar mavjud. Tasodifiy sonlar generatoridan bizga kerak bo'lgan narsa bu raqamlar haqiqatan ham tasodifiy emas, balki ularni oldindan aytib bo'lmaydi va takrorlanmaydi. Agar bizda bu ikki shart bajarilsa, biz xavfsizlikka erisha olamiz.

Boshqa tomondan, agar biz ushbu ikki shartni buzsak, xavfsizlik yo'q. 1994 yilda Monreal kazinosida lotereyalar uchun kompyuter tasodifiy raqamlar generatori o'rnatildi. Kazinoda ko'p vaqt o'tkazgan kuzatuvchi o'yinchilardan biri yutuq raqamlari har kuni bir xil bo'lishini payqadi. U ketma-ket uchta Jekpotni muvaffaqiyatli urdi va 600 000 dollar oldi. (Qo'llarini siqib, tishlarini g'ijirlatib, hamma narsani tekshirgandan so'ng, kazino yutuqni to'ladi.)

Tasodifiy sonlar generatorlarining bir nechta keng sinflari mavjud. Ulardan ba'zilari juda tasodifiy deb hisoblanishi mumkin bo'lgan jismoniy jarayonlarga asoslangan. Milliy xavfsizlik agentligi tasodifiy raqamlarni yaratish uchun o'z uskunasida diodlardan elektr shovqinidan foydalanishni yaxshi ko'radi. Boshqa imkoniyatlar Geiger hisoblagichlari yoki radio shovqinlarni qabul qiluvchilardir. Internetda bitta tizim foydalanadi Raqamli kamera, bir nechta stroblarga qaratilgan. Boshqa tizimlar drayvlardagi havo turbulentligi yoki tarmoq paketlarining vaqtini ishlatadi.

Ba'zi tasodifiy sonlar generatorlari foydalanuvchining tasodifiy harakatlarini kuzatib boradi. Dastur foydalanuvchidan klaviaturada ixtiyoriy belgilarning katta qatorini yozishni so'rashi mumkin; u tasodifiy raqamlarni yaratish uchun belgilar ketma-ketligidan yoki hatto tugmalar orasidagi vaqtdan foydalanishi mumkin. Boshqa dastur foydalanuvchidan sichqonchani oldinga va orqaga siljitishini yoki mikrofonga xirillashini osongina talab qilishi mumkin.

Ba'zi tasodifiy sonlar generatorlari ushbu kiritilgan ma'lumotlarni o'zgartirmasdan qo'llaydilar. Boshqalarida u matematik tasodifiy sonlar generatorlari uchun urug '(boshlang'ich raqam) bo'lib xizmat qiladi. Agar tizim kiritilgan ma'lumotlardan ko'ra ko'proq tasodifiy raqamlarni talab qilsa, bu usul eng yaxshi ishlaydi.

Tasodifiylikning kelib chiqishi qanday bo'lishidan qat'i nazar, generator bir qator tasodifiy bitlarni yaratadi. Keyinchalik ular kriptografik kalitlar sifatida va tizimga kerak bo'lgan barcha narsalar uchun ishlatilishi mumkin.

Biz bilan sodir bo'ladigan barcha hodisalar ikki xil - tasodifiy va tabiiy. Misol uchun, sizda magnitafon sotib olish uchun hisob-kitoblar etarli emas edi va siz pleer sotib olishga qaror qildingiz - ya'ni. harakat mantiqiy va kutilgan. Ammo do'konga borganingizda, rejalarni tasodifiy o'zgartiradigan kerakli miqdorni topasiz. Tasodifiy sonlar generatorining ishlashi to'liq operatorda ko'rsatilgan mexanizmga bog'liq, shuning uchun joriy hodisada chiqarilgan barcha raqamlar psevdo-tasodifiy bo'ladi. Qaytgan operatorlar tasodifiy raqamlar, vaqtga qarang, ya'ni tizim vaqti. Bular. Dunyoda ham, dasturlashda ham hech narsa mutlaqo mutlaq emas.

rand funktsiyasi

C dasturlashda tasodifiy qiymatlarni olish uchun o'rnatilgan operatorlar ixtiro qilingan, bu bizga kerakli natijalarni beradi. Shunday qilib, tasodifiy raqam yaratish uchun foydalaning rand funktsiyasi, qaysi rand operatori 0 dan ma'lum bir doimiylik oralig'ini qaytaradigan tasodifiy sonlarni olish uchun ishlatiladi. Bundan tashqari, ushbu konstanta ushbu rand funktsiyasi asoslangan tizim direktivasi "stdlib.h" da e'lon qilingan. Bu funksiyaning sintaksisi oddiy: int m= rand(); bular. butun son qaytariladi. Operatorni amalda sinab ko'rganingizdan so'ng, dastur ishga tushganda paydo bo'ladigan raqamlar bir xil ekanligini ko'rasiz. Nazorat shundaki, rand operatori kompilyatsiya paytida saqlanib qolgan bir xil tizim vaqti bilan ishlaydi. Ushbu tasodifiy sonlar generatori dastur vaqtini o'zgartirish algoritmiga bog'langan, ammo hamma narsa noto'g'ri ishlaydi.

Endi srand va tasodifiy haqida

Ushbu muammo uchun rand operatori har safar chaqirilganda o'rnatilgan vaqtni nolga qaytaradigan funksiya ajralmas edi va dasturiy ta'minot ishlab chiquvchilari buni qildilar. srand funktsiyasi. Harakat rand funktsiyasiga har safar o'rnatilgan taymerga emas, balki joriy o'rnatilgan taymerga kirish imkonini beradi, bu generatorning to'g'ri ishlashi - tasodifiy qiymatlarni ishlab chiqarish qobiliyatini ochadi. So'nggi paytlarda C++ dasturlashda mikrosekundlarning paydo bo'lishi tufayli tasodifiy sonlarni chiqarish mexanizmi takomillashtirildi. Bundan tashqari, qiymatlar doirasi kengaydi va barcha joriy innovatsiyalar tasodifiy funktsiyaga aylantirildi.

Qimor va sarguzasht darajasidan qat'i nazar, har bir kishi, u yoki bu tarzda, lotereya kabi tushunchaga duch kelgan. Va faqat bir nechtasi o'zlariga tasodifiy taqsimot qanday sodir bo'lishini so'rashdi qozongan kombinatsiyalar raqamlar U yoki bu raqam qanday chiqadi? O'lchovni g'olib tomon nima qiladi? Keling, buni batafsil ko'rib chiqaylik.

Hammamiz hayotimizda kamida bir marta lotereya kabi hodisaga duch kelganmiz. Ammo bu tizim qanday ishlashini, lotereya uchun raqam generatori nima va uning ishlash printsipi nima ekanligini juda kam odam o'ylagan yoki tasavvur qilgan.

Raqam generatori haqida tushuncha

Lotereya uchun tasodifiy raqamlar generatori - bu tasodifiy (to'g'riroq, psevdo-tasodifiy) tartibda belgilangan oraliqda joylashgan raqamlarni ishlab chiqaradigan ma'lum bir qurilma yoki berilgan dastur. Lotereyaning ma'lum bir turi uchun, masalan, "Sportloto" uchun 1 dan 49 gacha bo'lgan raqamlar ishlab chiqariladi.

Lotereya uchun apparat va dasturiy ta'minot raqamlar generatorlari mavjud. Har qanday dasturlash tilida RAND() funksiyasi mavjud bo'lib, u ma'lum diapazonda psevdotasodifiy raqamlarni ishlab chiqarish uchun javobgardir.

Nima uchun berilgan natijalar psevdo-tasodifiy ekanligi va lotereya raqamlari generatori aynan shu tamoyil asosida ishlashi aytilgan?

RAND funktsiyasi: tushunchasi va foydalanish usuli

RAND() funksiyasi dastur yoki, masalan, deterministik algoritmga ega bo'lgan qurilma bo'lib, u bir xil belgilangan sharoitlarda doimo bir xil natijalarni ko'rsatadi. Lekin haqiqiy tasodifiy ketma-ketlik shartlarini bajarish uchun hech qanday bog'liqlik bo'lmasligi kerak boshlang'ich sharoitlar yoki parametrlar. Shuning uchun, oldini olish uchun shunga o'xshash holatlar, maxsus RANDOMIZE protsedurasi qo'shimcha ravishda qo'llaniladi, bu dastlabki shartlarning taxminiyligini olib tashlaydi, ularni tasodifiy qiladi.

Bizga allaqachon ma'lum bo'lgan avlod printsipiga qo'shimcha ravishda, lotereya generatorining yana bir turi qo'llaniladi. Keling, buni quyida ko'rib chiqaylik.

Raqamlar generatori 45 dan 6 tasi

Lotereya uchun raqamlar generatori 45 dan 6 tasi - olish uchun foydalaniladigan dastur omadli raqamlar. Bunday holda, sozlash mumkin Qo'shimcha variantlar yaxshiroq natijalarga erishish uchun.

Siz tanlov mezonlarini belgilashingiz mumkin, masalan:

• Miqdori yutuq raqamlari, bu yakuniy natijada olinishi kerak.
• Tanlov amalga oshiriladigan raqamlar oralig'ini ko'rsating.
• Raqamlarni o'sish yoki kamayish tartibida tartiblash mumkin.
• Ajratish turi va usulini tanlang.
• Takroriy nusxalarni yo'q qiling yoki tanlovni tartibsiz qoldiring.
• Natijaga havolani nusxa ko'chiring va uni sahifaga joylashtiring ijtimoiy tarmoqlarda natijani e'lon qilish maqsadida.

Raqam generatori: foydalanish bo'yicha ko'rsatmalar

• Standart chiqish beshta raqamdan iborat. Sozlamalarni o'zgartirish orqali siz 250 ta tasodifiy yutuqli kombinatsiyani olishingiz mumkin.
• Biz diapazonni o'rnatdik, standart 0 dan 36 gacha, lekin siz maksimal 9,999,999,999 gacha belgilashingiz mumkin.
• Biz lotereya turi uchun kerakli tartibni tanlaymiz: o'sish, kamayish yoki raqamlarni tasodifiy tartibda joylashtirish.
• Keyingi qadam raqamlar bir-biridan qanday ajratilishini ko'rsatishdir - vergul, nuqta, bo'sh joy, nuqta-vergul.
• Namuna olish jarayonida paydo bo'lgan tasodifiy takrorlashlardan xalos bo'lamiz.

Shunday qilib, biz eng baxtli va g'olib bo'lishi mumkin bo'lgan yuqori sifatli tanlangan raqamlarni olamiz.

E'tibor bering, ideal holda tasodifiy sonlarni taqsimlash zichligi egri rasmda ko'rsatilgandek ko'rinadi. 22.3. Ya'ni, ideal holatda, har bir interval o'z ichiga oladi bir xil raqam ball: N i = N/k , Qayerda N — umumiy soni ball, k intervallar soni, i= 1, , k .

Shuni esda tutish kerakki, ixtiyoriy tasodifiy sonni yaratish ikki bosqichdan iborat:

• normallashtirilgan tasodifiy sonni yaratish (ya'ni 0 dan 1 gacha bir xil taqsimlangan);
• normallashtirilgan tasodifiy sonlar konvertatsiyasi r i tasodifiy raqamlarga x i, ular foydalanuvchi tomonidan talab qilinadigan (o'zboshimchalik) tarqatish qonuniga muvofiq yoki kerakli oraliqda taqsimlanadi.

Raqamlarni olish usuliga ko'ra tasodifiy sonlar generatorlari quyidagilarga bo'linadi:

• jismoniy;
• jadvalli;
• algoritmik.

Jismoniy RNG

Jismoniy RNGga misol bo'lishi mumkin: tanga ("boshlar" 1, "dumlar" 0); zar; raqamlar bilan sektorlarga bo'lingan o'qli baraban; shovqinli termal qurilmadan foydalanadigan apparat shovqin generatori (HS), masalan, tranzistor (22.422.5-rasm).

Jadvalli RNG

Jadvalli RNGlar tasodifiy sonlar manbai sifatida tekshirilgan o'zaro bog'liq bo'lmagan, ya'ni hech qanday tarzda bir-biriga bog'liq bo'lmagan raqamlarni o'z ichiga olgan maxsus tuzilgan jadvallardan foydalanadi. Jadvalda 22.1-rasmda bunday jadvalning kichik bir qismi ko'rsatilgan. Jadvalni chapdan o'ngga yuqoridan pastga aylantirib, kerakli o'nli kasrlar soni bilan 0 dan 1 gacha teng taqsimlangan tasodifiy sonlarni olishingiz mumkin (bizning misolimizda har bir raqam uchun uchta kasrdan foydalanamiz). Jadvaldagi raqamlar bir-biriga bog'liq bo'lmaganligi sababli, jadvalni kesib o'tish mumkin turli yo'llar bilan, masalan, yuqoridan pastga yoki o'ngdan chapga yoki, aytaylik, juft holatda bo'lgan raqamlarni tanlashingiz mumkin.

Qadr-qimmat bu usul Bu haqiqatan ham tasodifiy sonlarni ishlab chiqaradi, chunki jadvalda tasdiqlangan bog'liq bo'lmagan raqamlar mavjud. Usulning kamchiliklari: saqlash uchun katta miqdor raqamlar juda ko'p xotira talab qiladi; Ushbu turdagi jadvallarni yaratish va tekshirishda katta qiyinchiliklar mavjud, jadvaldan foydalanishda takrorlash endi raqamli ketma-ketlikning tasodifiyligini va natijaning ishonchliligini kafolatlamaydi.

500 ta mutlaqo tasodifiy tasdiqlangan raqamlarni o'z ichiga olgan jadval mavjud (I. G. Venetskiy, V. I. Venetskayaning "Iqtisodiy tahlildagi asosiy matematik va statistik tushunchalar va formulalar" kitobidan olingan).

Algoritmik RNG

Ushbu RNG-lar tomonidan yaratilgan raqamlar har doim psevdo-tasodifiy (yoki kvazi-tasodifiy), ya'ni hosil qilingan har bir keyingi raqam avvalgisiga bog'liq:

r i + 1 = f(r i) .

Bunday raqamlardan tashkil topgan ketma-ketliklar halqalarni hosil qiladi, ya'ni takrorlanadigan tsikl mavjud. cheksiz son bir marta. Takroriy tsikllar davrlar deb ataladi.

Ushbu RNGlarning afzalligi ularning tezligi; generatorlar deyarli hech qanday xotira resurslarini talab qilmaydi va ixchamdir. Kamchiliklari: raqamlarni to'liq tasodifiy deb atash mumkin emas, chunki ular o'rtasida bog'liqlik mavjud, shuningdek, kvazi-tasodifiy raqamlar ketma-ketligida davrlar mavjud.

Keling, RNGni olishning bir nechta algoritmik usullarini ko'rib chiqaylik:

• median kvadratlar usuli;
• o'rta mahsulotlar usuli;
• aralashtirish usuli;
• chiziqli kongruent usuli.

O'rta kvadrat usuli

Ba'zi to'rt xonali raqam mavjud R 0 . Bu raqam kvadratga bo'linadi va kiritiladi R 1 . Keyingi dan R 1 o'rtadagi (to'rtta o'rta raqam) yangi tasodifiy sonni oladi va uni yozadi R 0 . Keyin protsedura takrorlanadi (22.6-rasmga qarang). E'tibor bering, aslida tasodifiy raqam sifatida qabul qilmaslik kerak ghij, A 0.ghij chapga nol va o'nli nuqta qo'shilgan. Bu fakt rasmdagi kabi aks ettirilgan. 22.6 va keyingi shunga o'xshash raqamlarda.

Usulning kamchiliklari: 1) agar ba'zi iteratsiyada raqam bo'lsa R 0 nolga teng bo'ladi, keyin generator buziladi, shuning uchun dastlabki qiymatni to'g'ri tanlash muhimdir R 0 ; 2) generator ketma-ketlikni takrorlaydi M n qadamlar (in eng yaxshi stsenariy), Qayerda n raqam raqami R 0 , M sanoq tizimining asosi.

Masalan, rasmda. 22.6: agar raqam R 0 ikkilik sanoq sistemasida, keyin esa ketma-ketlikda ifodalanadi psevdor tasodifiy raqamlar 2 4 = 16 bosqichda takrorlanadi. E'tibor bering, agar boshlang'ich raqam noto'g'ri tanlangan bo'lsa, ketma-ketlikning takrorlanishi oldinroq sodir bo'lishi mumkin.

Yuqorida tavsiflangan usul Jon fon Neumann tomonidan taklif qilingan va 1946 yilga borib taqaladi. Ushbu usul ishonchsiz bo'lib chiqqanligi sababli, u tezda tark etildi.

O'rta mahsulot usuli

Raqam R 0 ga ko'paytiriladi R 1, olingan natijadan R 2 o'rtasi chiqariladi R 2 * (bu boshqa tasodifiy raqam) va ko'paytiriladi R 1 . Barcha keyingi tasodifiy sonlar ushbu sxema yordamida hisoblab chiqiladi (22.7-rasmga qarang).

Aralashtirish usuli

Aralash usuli hujayra tarkibini tsiklik ravishda chapga va o'ngga siljitish uchun operatsiyalardan foydalanadi. Usulning g'oyasi quyidagicha. Hujayra boshlang'ich raqamni saqlasin R 0 . Hujayra tarkibini tsiklik ravishda hujayra uzunligining 1/4 qismiga chapga siljitish orqali biz yangi raqamga ega bo'lamiz. R 0 *. Xuddi shu tarzda, hujayraning tarkibini velosipedda aylantirish R 0 o'ngga hujayra uzunligining 1/4 qismiga, biz ikkinchi raqamni olamiz R 0**. Raqamlar yig'indisi R 0* va R 0** yangi tasodifiy raqamni beradi R 1 . Keyinchalik R 1 kiritilgan R 0 va operatsiyalarning butun ketma-ketligi takrorlanadi (22.8-rasmga qarang).

E'tibor bering, yig'indidan olingan raqam R 0* va R 0 ** , hujayra ichiga to'liq sig'masligi mumkin R 1 . Bunday holda, olingan raqamdan qo'shimcha raqamlarni olib tashlash kerak. Keling, buni rasmda tushuntiramiz. 22.8, bu erda barcha hujayralar sakkizta ikkilik raqam bilan ifodalanadi. Mayli R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Keyin R 0 * + R 0 ** = 100110010 2 = 306 10 . Ko'rib turganingizdek, 306 raqami 9 ta raqamni (ikkilik sanoq tizimida) egallaydi va hujayra R 1 (xuddi shunday R 0) maksimal 8 bitni o'z ichiga olishi mumkin. Shuning uchun, qiymatni kiritishdan oldin R 1, 306 raqamidan bitta "qo'shimcha", eng chap bitni olib tashlash kerak, natijada R 1 endi 306 ga emas, balki 00110010 2 = 50 10 ga boradi. Shuni ham yodda tutingki, Paskal kabi tillarda hujayra to'lib ketganda qo'shimcha bitlarni "qirqish" o'zgaruvchining belgilangan turiga muvofiq avtomatik ravishda amalga oshiriladi.

Chiziqli kongruent usuli

Chiziqli kongruent usuli hozirgi vaqtda tasodifiy sonlarni simulyatsiya qilishda eng oddiy va eng ko'p qo'llaniladigan protseduralardan biridir. Bu usulda mod( x, y), birinchi argument ikkinchisiga bo'linganda qoldiqni qaytaradi. Har bir keyingi tasodifiy son oldingi tasodifiy raqam asosida quyidagi formula yordamida hisoblanadi:

r i+ 1 = mod( k · r i + b, M) .

Ushbu formula yordamida olingan tasodifiy sonlar ketma-ketligi deyiladi chiziqli kongruent ketma-ketlik. Ko'pgina mualliflar chiziqli kongruent ketma-ketlikni qachon deb atashadi b = 0 multiplikativ kongruent usuli, va qachon b ≠ 0 — aralash kongruent usuli.

Yuqori sifatli generator uchun mos koeffitsientlarni tanlash kerak. Raqam bo'lishi kerak M ancha katta edi, chunki davr bundan ortiq bo'lishi mumkin emas M elementlar. Boshqa tomondan, ushbu usulda ishlatiladigan bo'linish juda sekin ishlaydi, shuning uchun ikkilik kompyuter uchun mantiqiy tanlov bo'ladi. M = 2 N, chunki bu holda bo'linishning qolgan qismini topish kompyuter ichida "VA" ikkilik mantiqiy operatsiyasiga qisqartiriladi. Eng katta tub sonni tanlash ham keng tarqalgan M, 2 dan kam N: maxsus adabiyotlarda isbotlanganki, bu holda olingan tasodifiy sonning past tartibli raqamlari r i+ 1 xuddi eskilari kabi tasodifiy harakat qiladi, bu umuman tasodifiy sonlarning butun ketma-ketligiga ijobiy ta'sir qiladi. Misol tariqasida, ulardan biri Mersenne raqamlari, 2 31 1 ga teng va shunday qilib, M= 2 31 1 .

Chiziqli kongruent ketma-ketliklarga qo'yiladigan talablardan biri bu davr uzunligi imkon qadar uzun bo'lishidir. Davrning uzunligi qiymatlarga bog'liq M , k Va b. Quyida keltirilgan teorema davrga erishish mumkinligini aniqlash imkonini beradi maksimal uzunlik muayyan qiymatlar uchun M , k Va b .

Teorema. Raqamlar bilan aniqlangan chiziqli kongruent ketma-ketlik M , k , b Va r 0, uzunlik davriga ega M agar va faqat agar:

• raqamlar b Va M nisbatan oddiy;
• k 1 marta p har bir asosiy uchun p, bu bo'luvchidir M ;
• k 1 4 ning karrali, agar M 4 ga karra.

Nihoyat, tasodifiy sonlarni hosil qilish uchun chiziqli kongruent usulidan foydalanishga bir nechta misollar bilan yakunlaylik.

1-misol ma'lumotlari asosida yaratilgan bir qator psevdo-tasodifiy raqamlar har safar takrorlanishi aniqlandi. M/4 raqam. Raqam q hisob-kitoblar boshlanishidan oldin o'zboshimchalik bilan o'rnatiladi, ammo shuni yodda tutish kerakki, seriyalar umuman tasodifiy taassurot qoldiradi. k(va shuning uchun q). Natijani biroz yaxshilash mumkin, agar b g'alati va k= 1 + 4 · q bu holda qator har bir takrorlanadi M raqamlar. Uzoq qidiruvdan keyin k tadqiqotchilar 69069 va 71365 qiymatlariga qaror qilishdi.

2-misoldagi ma'lumotlardan foydalangan holda tasodifiy sonlar generatori 7 million davriy tasodifiy, takrorlanmaydigan raqamlarni ishlab chiqaradi.

Soxta tasodifiy raqamlarni yaratishning multiplikativ usuli 1949 yilda D. H. Lehmer tomonidan taklif qilingan.

Jeneratorning sifatini tekshirish

Butun tizimning sifati va natijalarning aniqligi RNG sifatiga bog'liq. Shuning uchun, RNG tomonidan yaratilgan tasodifiy ketma-ketlik bir qator mezonlarga javob berishi kerak.

O'tkazilgan tekshiruvlar ikki turga bo'linadi:

• taqsimotning bir xilligini tekshiradi;
• statistik mustaqillik testlari.

Tarqatishning bir xilligini tekshiradi

1) RNG yagona tasodifiy qonunga xos bo'lgan statistik parametrlarning quyidagi qiymatlariga yaqin bo'lishi kerak:

2) Chastotani tekshirish

Chastotani tekshirish sizga oraliqda qancha raqam tushishini aniqlash imkonini beradi (m r – σ r ; m r + σ r) , ya'ni (0,5 0,2887; 0,5 + 0,2887) yoki oxir-oqibat (0,2113; 0,7887). 0,7887 0,2113 = 0,5774 bo'lgani uchun biz yaxshi RNGda chizilgan barcha tasodifiy sonlarning taxminan 57,7% i ushbu intervalga to'g'ri kelishi kerak degan xulosaga keldik (22.9-rasmga qarang).

Shuni ham hisobga olish kerakki, (0; 0,5) intervalga tushadigan sonlar soni taxminan (0,5; 1) oraliqdagi raqamlar soniga teng bo'lishi kerak.

3) Xi-kvadrat testi

Xi-kvadrat testi (ch 2 testi) eng mashhur statistik testlardan biridir; boshqa mezonlar bilan birgalikda qo'llaniladigan asosiy usuldir. Xi-kvadrat testi 1900 yilda Karl Pirson tomonidan taklif qilingan. Uning ajoyib ishi zamonaviy matematik statistikaning asosi hisoblanadi.

Bizning holatimizda, chi-kvadrat mezonidan foydalangan holda sinov bizga qancha ekanligini aniqlashga imkon beradi haqiqiy RNG ga yaqin RNG standarti, ya'ni bir xil taqsimlash talabini qondiradimi yoki yo'qmi.

Chastotalar diagrammasi ma'lumotnoma RNG rasmda ko'rsatilgan. 22.10. Yo'naltiruvchi RNG ning taqsimot qonuni bir xil bo'lgani uchun, u holda (nazariy) ehtimollik p i raqamlarni kiritish i th interval (bu barcha intervallar k) ga teng p i = 1/k . Va shunday qilib, har birida k intervallar uriladi silliq tomonidan p i · N raqamlar ( N hosil qilingan raqamlarning umumiy soni).

Haqiqiy RNG raqamlarni taqsimlaydi (va teng ravishda emas!). k intervallarni va har bir intervalni o'z ichiga oladi n i raqamlari (jami n 1 + n 2 + + n k = N ). Sinov qilinayotgan RNG qanchalik yaxshi ekanligini va u mos yozuvlarga qanchalik yaqinligini qanday aniqlashimiz mumkin? Olingan sonlar soni o'rtasidagi kvadratik farqlarni hisobga olish juda mantiqiy n i va "ma'lumotnoma" p i · N . Keling, ularni qo'shamiz va natija:

ch 2 tajriba. = ( n 1 p 1 · N) 2 + (n 2 p 2 · N) 2 + + ( n k – p k · N) 2 .

Ushbu formuladan kelib chiqadiki, har bir atamadagi farq qanchalik kichik bo'lsa (va shuning uchun kamroq qiymat ch 2 tajriba. ), haqiqiy RNG tomonidan yaratilgan tasodifiy sonlarni taqsimlash qonuni qanchalik kuchli bo'lsa, bir xil bo'ladi.

Oldingi ifodada atamalarning har biriga bir xil og'irlik (1 ga teng) berilgan, bu aslida to'g'ri bo'lmasligi mumkin; shuning uchun, chi-kvadrat statistikasi uchun har birini normallashtirish kerak i th muddat, uni bo'lish p i · N :

Nihoyat, keling, hosil bo'lgan ifodani ixchamroq yozamiz va uni soddalashtiramiz:

uchun chi-kvadrat sinov qiymatini oldik eksperimental ma'lumotlar.

Jadvalda 22.2 berilgan nazariy chi-kvadrat qiymatlari (ch 2 nazariy), bu erda ν = N 1 - erkinlik darajalari soni, p Bu RNG yagona taqsimot talablariga qanchalik javob berishi kerakligini ko'rsatadigan foydalanuvchi tomonidan belgilangan ishonch darajasi yoki p — ch 2 eksperimental qiymatining ehtimoli. jadvalli (nazariy) ch 2 nazariydan kamroq bo'ladi. yoki unga teng.

Qabul qilinadigan deb hisoblanadi p 10% dan 90% gacha.

Agar ch 2 exp. ch 2 nazariyasidan ancha ko'p. (ya'ni p katta), keyin generator qanoatlantirmaydi kuzatilgan qiymatlardan beri yagona taqsimot talabi n i nazariyadan juda uzoqqa boring p i · N va tasodifiy deb hisoblanmaydi. Boshqacha qilib aytganda, u juda katta o'rnatilgan ishonch oralig'i raqamlarga bo'lgan cheklovlar juda bo'shashib, raqamlarga qo'yiladigan talablar zaiflashadi. Bunday holda, juda katta mutlaq xatolik kuzatiladi.

Hatto D. Knuth o'zining "Dasturlash san'ati" kitobida ch 2 tajribaga ega ekanligini ta'kidladi. kichiklar uchun, umuman olganda, bu ham yaxshi emas, garchi bu bir qarashda bir xillik nuqtai nazaridan ajoyib bo'lib tuyulsa ham. Darhaqiqat, 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 raqamlar qatorini oling, ular ideallik va bir xillik nuqtai nazaridan. 2 tajriba. amalda nolga teng bo'ladi, lekin siz ularni tasodifiy deb tan olishingiz dargumon.

Agar ch 2 exp. ch 2 nazariyasidan ancha kam. (ya'ni p kichik), keyin generator qanoatlantirmaydi kuzatilgan qiymatlardan beri tasodifiy yagona taqsimot talabi n i nazariyaga juda yaqin p i · N va tasodifiy deb hisoblanmaydi.

Lekin agar ch 2 exp. ch 2 nazariyasining ikkita qiymati o'rtasida ma'lum bir oraliqda yotadi. , mos keladigan, masalan, p= 25% va p= 50%, keyin sensor tomonidan yaratilgan tasodifiy son qiymatlari butunlay tasodifiy deb taxmin qilishimiz mumkin.

Bundan tashqari, barcha qadriyatlarni yodda tutish kerak p i · N etarlicha katta bo'lishi kerak, masalan, 5 dan ortiq (ampirik tarzda topilgan). Shundagina (etarlicha katta statistik namunaga ega bo'lgan holda) tajriba sharoitlarini qoniqarli deb hisoblash mumkin.

Shunday qilib, tekshirish tartibi quyidagicha.

Statistik mustaqillik uchun testlar

1) Ketma-ketlikda raqamlarning paydo bo'lish chastotasini tekshirish

Keling, bir misolni ko'rib chiqaylik. Tasodifiy son 0,2463389991 2463389991 raqamlaridan, 0,5467766618 raqamlari esa 5467766618 raqamlardan iborat. Raqamlar ketma-ketligini birlashtirib, bizda: 2463389996161.

Nazariy ehtimollik aniq p i yo'qotish i Raqam (0 dan 9 gacha) 0,1 ga teng.

2) Bir xil sonlar qatorining ko'rinishini tekshirish

bilan belgilaymiz n L uzunlikdagi bir qatordagi bir xil raqamlar qatori soni L. Hamma narsani tekshirish kerak L 1 dan m, Qayerda m bu foydalanuvchi tomonidan ko'rsatilgan raqam: ketma-ketlikda bir xil raqamlarning maksimal uchraydigan soni.

“24633899915467766618” misolida uzunligi 2 (33 va 77) bo'lgan 2 ta seriya topildi, ya'ni n 2 = 2 va 2 seriyali uzunlik 3 (999 va 666), ya'ni n 3 = 2 .

Bir qator uzunlikning paydo bo'lish ehtimoli L teng: p L= 9 10 L (nazariy). Ya'ni, bir belgi uzunlikdagi seriyaning paydo bo'lish ehtimoli quyidagilarga teng: p 1 = 0,9 (nazariy). Ikkita belgilar seriyasining paydo bo'lish ehtimoli: p 2 = 0,09 (nazariy). Bir qator uchta belgi paydo bo'lish ehtimoli: p 3 = 0,009 (nazariy).

Masalan, bir belgi uzunlikdagi seriyaning paydo bo'lish ehtimoli p L= 0,9, chunki 10 tadan bitta belgi bo'lishi mumkin va jami 9 ta belgi bo'lishi mumkin (nol hisobga olinmaydi). Va ikkita bir xil "XX" belgisining ketma-ket paydo bo'lish ehtimoli 0,1 · 0,1 · 9 ga teng, ya'ni "X" belgisining birinchi holatda paydo bo'lish ehtimoli 0,1 ga ko'paytiriladi. xuddi shu belgi ikkinchi "X" pozitsiyasida paydo bo'ladi va bunday kombinatsiyalar soni 9 ga ko'paytiriladi.

Qatorlarning paydo bo'lish chastotasi qiymatlar yordamida biz ilgari muhokama qilgan chi-kvadrat formulasi yordamida hisoblanadi p L .

Eslatma: Jeneratör bir necha marta sinovdan o'tkazilishi mumkin, ammo testlar to'liq emas va generator tasodifiy raqamlarni ishlab chiqarishiga kafolat bermaydi. Misol uchun, 12345678912345 ketma-ketligini ishlab chiqaradigan generator sinovlar davomida ideal deb hisoblanadi, bu mutlaqo to'g'ri emas.

Xulosa qilib shuni ta'kidlaymizki, Donald E.Knutning "Dasturlash san'ati" (2-jild) kitobining uchinchi bobi butunlay tasodifiy sonlarni o'rganishga bag'ishlangan. Oʻrganadi turli usullar tasodifiy sonlarni yaratish, tasodifiylikning statistik testlari va bir xil taqsimlangan tasodifiy sonlarni boshqa turlarga aylantirish tasodifiy o'zgaruvchilar. Ikki yuzdan ortiq sahifalar ushbu materialning taqdimotiga bag'ishlangan.