Відмінності між версіями «Доповідь на тему "Генератор випадкових чисел"»
| Рядок 121: | Рядок 121: | ||
p=99% p=95% p=75% p=50% p=25% p=5% | p=99% p=95% p=75% p=50% p=25% p=5% | ||
| − | n=5 0.5543 1.1455 2.675 4.351 6.626 | + | n=5 0.5543 1.1455 2.675 4.351 6.626 11.07 |
| − | n=10 2.558 3.940 6.737 9.342 | + | n=10 2.558 3.940 6.737 9.342 12.55 18.31 |
| − | n=15 5.229 7.261 | + | n=15 5.229 7.261 11.04 14.34 18.25 25.00 |
| − | n=20 8.260 | + | n=20 8.260 10.85 15.45 19.34 23.83 31.41 |
n=30 14.95 18.49 24.48 29.34 34.80 43.77 | n=30 14.95 18.49 24.48 29.34 34.80 43.77 | ||
Вибрані значення хи-квадрат. | Вибрані значення хи-квадрат. | ||
Поточна версія на 09:18, 24 травня 2011
Зміст
Генерація випадкових чисел і моделювання
Послідовності випадкових чисел використовуються в програмуванні в найрізноманітніших випадках, починаючи з моделювання (це найбільш часте застосування) і кінчаючи іграми і іншим розважальним програмним забезпеченням. Турбо Паскаль містить вбудовану функцію, звану Random, яка генерує випадкові числа. Як ви побачите в даному розділі, Random - це чудовий генератор випадкових чисел, але для деяких застосувань вам може потрібно два або більш різних генераторів для забезпечення різних наборів випадкових чисел для різних завдань. Крім того, при моделюванні потрібний ассиметрічний або дісбалансний генератор випадкових чисел, який породжує послідовність, зміщену до одного з кінців. Перша частина даного розділу присвячена побудові генераторів випадкових чисел і оцінці їх якості.
Генератори випадкових чисел
Технічно термін "генератор випадкових чисел" - це абсурд; числа само по собі не є випадковими. Наприклад, 100 - це випадкове число? А 25? Що насправді означає цей термін, так це те, що створюється послідовність чисел, що з'являються випадковим чином. Це породжує складніше питання: що таке послідовність випадкових чисел? Єдино правильна відповідь: послідовність випадкових чисел _ це послідовність, в якій всі елементи є незв'язаними. Це визначення приводить до такого парадоксу, що будь-яка послідовність може бути як випадковою, так і невипадковою залежно від того, як ця послідовність отримана. Наприклад, наступний рядок чисел 1 2 3 4 5 6 7 8 9 0 була отримана друкуванням верхнього рядка клавіатури по порядку, таким чином послідовність звичайно не може розглядатися як що згенерувала випадковим чином. Але як бути, якщо ви отримаєте ту ж саму послідовність, виймаючи пронумерований тенісні кулі з боченка. В даному випадку це вже випадковим чином послідовність, що згенерувала. Даний приклад показує, що випадковість послідовності залежить від того, як вона була отримана, а не від неї самої. Пам'ятаєте, що послідовність чисел, що згенерувала комп'ютером, є детермінованою: кожне число, окрім першого, залежить від попередніх чисел. Технічно це означає, що комп'ютером може згенерувати тільки квазівипадкова послідовність чисел. Проте, це досить для більшості завдань і в даній книзі такі послідовності для простоти називатимуться випадковими. У загальному випадку вважається добре, коли числа в послідовності випадкових чисел розподілені рівномірно (не плутайте це з нормальним розподілом або колоколообразной кривою). При рівномірному розподілі всі події рівноімовірні так, що діаграма рівномірного розподілу прагне до прямої горизонтальної лінії, а не до кривій. До широкого розповсюдження комп'ютерів всякий раз, коли необхідні були випадкові числа, вони виходили або киданням гральних кісток, або вийманням пронумерованих куль з ящика. У 1955 році фірма RAND опублікувала таблицю з 1 мільйона випадкових чисел, отриманих за допомогою обчислювальної машини. На ранній стадії розвитку обчислювальної техніки було розроблено багато методів генерації випадкових чисел, але більшість з них не знайшла застосування. Один дуже цікавий метод був розроблений Джоном фон Нейманом; його часто називають середньоквадратичним. У даному методі попереднє випадкове число зводиться в квадрат, а потім з результату виділяються середні цифри. Наприклад, якщо ви створюєте числа з трьох цифр, а попереднє число було 121, то зведення в квадрат дає результат 14641. Виділення трьох середніх цифр дає наступне випадкове число 464. Недоліком даного методу є те, що він має дуже короткий період повторення, званий циклом. З даної причини даний метод сьогодні не використовується. Зараз найчастіше застосовується метод генерації випадкових чисел, що грунтується на використанні рівняння
R = (aR +c)modm
n+1 n
при виконанні наступних умов
R>0 a>0 c>0 m>R , a и c
Відзначимо, що R - це попереднє число, а R - наступне. Даний метод іноді називають лінійним порівняльним методом. Формула така проста, що ви можете подумати, що генерувати випадкові числа просто. Проте, це пастка: наскільки добре працює дана формула, дуже сильно залежить від значення а, з і m. Вибір значень іноді більшою мірою мистецтво, ніж наука. Існують складні правила, які можуть допомогти вам вибрати значення; проте, ми розглянемо лише декілька простих правил і прикладів. Модуль (m) повинен бути досить великим, оскільки він визначає область випадкових чисел. Операція узяття по модулю породжує залишок від ділення числа на модуль. Отже, 10 по модулю 4 рівне 2. Таким чином, якщо модуль рівний 12, то формулою породжуються числа від 0 до 11, а якщо модуль рівний 21425, то породжуються числа від 0 до 21424. Вибір множника а і прирости з є дуже складним завданням. У загальному випадку множник може бути задоволене великим, а приріст - маленьким. Безліч спроб і перевірок необхідна, щоб створити хороший генератор. Як перший приклад тут приведений один з найчастіше використовуваних генераторів випадкових чисел. Рівняння, показане в Rаn1 використовується як основа для генератора випадкових чисел у ряді популярних мов.
var
a1: integer; { установка до первого вызова Ran1 }
function Ran1: real;
var
t: real;
begin
t := (a1*32749+3) mod 32749;
a1 := Trunc(t);
Ran1 := Abs(t/32749);
end; {Rea1}
Дана функція має три головні особливості. По-перше, випадкові числа насправді є цілими, хоча функція повертає дійсні числа. Даний метод працює з цілими числами, але генератори випадкових чисел, як це прийнято, повинні повертати числа в межах від 0 до 1, що означає, що це повинні бути числа з плаваючою комою. По-друге, початкове значення задається через глобальну змінну а1. До першого виклику Ran1 змінна а1 повинна бути встановлена в 1. По-третє, в Ran1 випадкові числа діляться на модуль перш, ніж вони будуть повернені функцією, для того, щоб числа лежали в області від 0 до 1. Якщо ви поцікавитеся значенням глобальної змінної а1 до повернення рядка, то воно повинне лежати в області від 0 до 32748. Отже, коли а1 ділиться на 32749, отримане число буде більше або рівне 0 і менше 1. Багато генераторів випадкових чисел не застосовні, оскільки вони породжують не рівномірний розподіл або мають короткий цикл повторення. Навіть коли ці недоліки не дуже впадають в очі, вони можуть породити змішаний результат, якщо такий генератор використовується знову і знову. Рішення полягає в тому, щоб створити різні генератори і застосовувати їх індивідуально або спільно для отримання якісніших послідовностей випадкових чисел. Застосування декількох генераторів може згладити розподіл послідовності за рахунок зменшення малих змішень окремих генераторів. Далі приведена функція генерування випадкових чисел, звана Ran2, яка породжує хороший розподіл:
var
a2:integer; { встановити в значення 203 до першого виклику
Ran2 }
function Ran2: real;
var
t: real;
begin
t := (a2*10001+3) mod 17417;
a2 := Trunc(t);
Ran2 := Abc(t/17417);
end; {Ran2}
Обидва цих генератора випадкових чисел породжують хороші послідовності випадкових чисел. Проте залишаються питання: чи достатньо "випадковою" є послідовність? Чи хороші дані генератори?
Типи генераторів
Без комп'ютера використання випадкових чисел,передбачене методом статистичних випробувань, не мас сенсу, тому генератори випадкових чисел повинні бути безпосередньо з'єднані з комп'ютером. Це можна зробити за допомогою апаратних приставок до комп'ютера (апаратні методи) або спеціальних програм (програмні методи). Крім того, під час моделювання можна використати готові таблиці випадкових чисел, які слід розміщати в пам'яті комп'ютера або на зовнішньому накопичувачі. Апаратні методи генерування0 випадкових чисел базуються на використанні деяких фізичних явищ (наприклад, шумів електронних приладів, радіоактивного випромінення та ін.). Під час застосування апаратних генераторів випадковий електричний сигнал перетворюють у двійковий код, який уводиться в комп'ютер за допомогою спеціальних аналого-цифрових перетворювачів. Один з найбільш поширених методів це використання шумів електронних приладів. Якщо на підсилювач не подавати ніякого сигналу та увімкнута його па повну потужність, то буде чутно шипіння (шум). Це і є шум електронних елементів підсилювача, який є випадковим процесом. Цей неперервний сигнал можна перетвориш в дискретний. Існують. Різні схеми перетворення випадкового сигналу в послідовність двійкових цифр. У більшості випадків його підсилюють і встановлюють граничне значення напруги шумового сигналу, перевищення якого можна вважати значенням двійкової одиниці на деякому малому проміжку часу t.У протилежному випадку отримуємо двійковий нуль. Для отримання m - розрядного випадкового двійкового числа провадиться m вимірювань неперервного сигналу у фіксовані моменти часу t1, t2,…tm. Вбудовані в комп'ютери апаратні генератори випадкових чисел останнім часом часто використовуються в системах захисту інформації. Прикладом застосування таких генераторів для забезпечення конфіденційності, цілісності та достовірності електронної інформації, яка зберігається в комп'ютері або передасться по мережі, є пристрій для шифрування даних PadLock інтегрований у деякі моделі процесорів, розроблених компанією Intel. Пристрій має інтерфейс прикладного рівня, що дає змогу розробникам програмного забезпечення отримувати випадкові числа без використання програмних драйверів. Такий спосіб отримання високоякісних випадкових послідовностей простіший та ефективніший, ніж використання апаратно-програмної RNG (Random Number Generator) архітектури і суто програмних генераторів, що особливо важливо під час побудови захищених і криптографічних програм. Табличний метод. У 1955 році корпорація «Ренд» опублікувала таблиці випадкових чисел, які мали мільйон значень. Для заповнення цих таблиць застосовувались апаратні методи. Дані цих таблиць можна використовувати під час моделювання систем за допомогою методу статистичних випробувань. У сучасних комп'ютерах ці таблиці можна зберігати на зовнішніх носіях або навіть в основній пам'яті. Головним недоліком табличного методу є те, що під час його використання витрачаються значні об'єми основної пам'яті комп'ютера. Найбільш розповсюдженими на практиці є програмні генератори, які дають змогу отримувати послідовності випадкових чисел за рекурентними формулами. Якщо бути абсолютно точним, то числа, які виробляють програмні генератори, насправді є псевдовипадковими («псевдо» у перекладі з грецької — нібито). Так їх називають тому, що алгоритми їх отримання завжди е детермінованими. Загалом же програмні генератори повинні задовольняти таким вимогам:
- генерувати статистично незалежні випадкові числа, рівномірно розподілені
в інтервалі [0, 1];
- мати можливість відтворювати задані послідовності випадкових чисел;
- затрати ресурсів процесора на роботу генератора повинні бути мінімальними;
- легко створювати незалежні послідовності випадкових чисел (потоки).
Слід звернути увагу на те, що більшість програмних генераторів виробляють випадкові числа, рівномірно розподілені в інтервалі [0, 1]. Необхідність моделювання таких чисел обумовлена тим, що на їх основі можна отримати випадкові числа практично будь-яких розподілів. Потрібно також мати на увазі, що випадкові числа,які наробляють програмні генератори, є квазірівномірно розподіленими («квазі» у перекладі з латинської — майже). Причина в тому, що вони створюються комп'ютером, кількість двійкових розрядів якого обмежена, і за його допомогою можна зобразити тільки дискретні (а не неперервні) значення з діапазону від 0 до 1. Якість роботи генераторів визначається статистичними властивостями послідовностей випадкових чисел, які він виробляє, - незалежністю і випадковістю. Властивості послідовностей перевіряються за статистичними критеріями, детально описаними нижче. Здатність відтворювання послідовності випадкових чисел полягає в тому, що за однакових початкових умов і параметрів генератор повинен відтворювати одні і ті ж послідовності випадкових чисел. Ідентичні послідовності випадкових чисел рекомендується використовувати у випадку, коли потрібно порівняти альтернативні варіанти систем, що моделюються, і налагодити програми. Однак можливість відтворення не завжди бажана під час моделювання систем і в комп'ютерних іграх (як це було на перших версіях відомої гри «Тетріс», коли кожна гра починалась з тієї ж послідовності фігур). Для усунення такого недоліку початкові значення величин, необхідних для запуску програмного генератора, рекомендується брати з таймера комп'ютера. Під час дослідження складних систем виникає необхідність у моделюванні послідовностей випадкових чисел великої довжини. Для їх створення потрібні швидкодіючі алгоритми генерування з мінімальними вимогами до ресурсів комп'ютера. Інколи дослідники з невеликим досвідом роботи використовують під час моделювання складних систем один і той же генератор, звертаючись до нього з різних місць програми. Однак це часто призводить до того, що процес моделювання швидко вироджується у зв'язку з виходом псевдовипадкової послідовності за межі аперіодичності. Тому для моделювання різних випадкових факторів бажано мати окремі послідовності (набори значень), які відтворювались би одним і тим же генератором, але за різних значень параметрів. У більшості генераторів псевдовипадкових чисел хi, використовується рекурентна процедура xi+1=f(хi). Найпростішим та найдавнішим серед таких генераторів є генератор фон Неймана та Метрополіса, робота якого базувалась на методі середин квадратів. Пояснімо суть цього методу. Зобразимо умовно довільне чотирирозрядне десяткове число як х х х х. Піднесемо це число до квадрату і в отриманому результаті відкинемо по дві цифри зліва і справа:
Чотири цифри, які залишились, і є новим випадковим числом. Якщо результатом множення є число з кількістю цифр менше восьми, зліва дописуються додаткові нулі. Реалізувати програмно цей генератор дуже просто, але він має ряд вад: якщо початкове число парне, то може відбутися виродження послідовності, тобто починаючи з деякого значення всі наступні дорівнюватимуть нулю (спробуйте взяти як початкове число 4500); числа, які виробляє генератор, є сильно корельованими.
Лінійні конгруентні генератори Зважаючи на ці вади, на практиці використовують більш складні програмні гене-ратори. У більшості сучасних програмних генераторів використовується властивість конгруентності, яка полягає в тому, що два цілих числа А і В є конгруентними за модулем m якщо їх різниця (А - В) є числом, яке ділиться на m без остачі (тобто є кратним m). Записується це так: А = В (mod m). Наприклад, щоб знайти число, конгруентне з числом 134 за модулем 10, необхідно знайти цілочислову остачу від ділення 134 на 10, яка дорівнює 4. Наведемо кілька прикладів обчислення .конгруентних значень для різних m: 12 ≡ 5 (mod 7); 35 ≡ 5 (mod 10); 125 ≡ 5 (mod 10). Серед методів генерування випадкових чисел найбільш поширеним є ліній¬ний мультиплікативний конгруентний метод: xi+1 = (axi + c) mod m, (1) де і = 1, 2,...; а,с і m - цілі константи. Щоб отримати нове число, необхідно взяти псевдовипадкове число х, (або задати вихідне х0). помножити його на коефіцієнт а, додати константу с і взяти модуль отриманого числа за m. тобто розділити на m, і отримати остачу. Ця остача і буде наступним псевдовипадковим числом хі+1. У разі правильного підбору параметрів цей генератор повертає випадкові числа від 0 до m-1. Отримані за формулою (1) значення xi+1 належать до діапазону 0 < xi+1< m-1 і мають рівномірний дискретний розподіл. Для того щоб отримати випадкове значення rі+1 з інтервалу [0, 1], необхідно число xi+1розділити на m. У цьому разі всі значення m, с. а,x0 повинні бути додатними й задовольняти умовам: 0<m; а<m;с<m; х0<m. Отримана за формулою (1) послідовність називається лінійною конгруентною послідовністю. Однією із вад лінійних конгруентних генераторів є те, що отримані випадкові числа хi+1 суттєво залежать від значень m, с, а, х0 і обчислюються за однією й тією ж формулою (1), тобто не є абсолютно випадковими. Але незважаючи на те що, алгоритм їх отримання є детермінованим, за умови відповідного вибору констант m, с, а послідовність чисел хi+1, на основі яких отримують значення ri+1 повністю задовольнятиме більшості статистичних критеріїв. Ще одна вада цих генераторів стосується того, що випадкові числа ri+1, отримані за допомогою генератора, можуть приймати тільки дробово-раціональні значення - 0; 1/m; 2/m;...; [m-1)/m. Більше того, числа ri+1 можуть приймати лише деякі з указаних значень залежно від вибраних параметрів m,с, а і x0, а також від того, як реалізується операція ділення чисел з плаваючою комою на число m у комп'ютері, тобто залежно від типу комп'ютера і системи програмування. Наприклад, якщо m = 10, х0=а=с=7, то отримаємо послідовність 7; 6; 9; 0; 7; 6; 9; 0,..., яка не є випадковою. Це свідчить про важливість правильного вибору значень констант m, с, а і x0 Правильно підібрані значення іноді називають магічними числами. Наведений приклад ілюструє й те, що конгруентна послідовність завжди є ци-клічною, тобто вона починає повторюватися через певну кількість випадкових чисел. Кількість значень, після яких випадкові числа починають повторюватися, називається повним періодом генератора і є основним його параметром. Значення повного періоду, залежать від розрядності комп'ютера, а також від значень m, с, а і x0.Існує теорема, яка визначає умови існування повного періоду генератора, а саме: числа c і m повинні бути взаємно простими, тобто мати взаємний дільник 1; значення b= а - 1 має бути кратним q для кожного простого q, бути дільником m; значення b має бути кратним 4, якщо m кратне 4. Достатність цих умов уперше було доведене Халлом і Добеллом. Якщо с > 0, то генератор називається мішаним, а якщо с = 0 - мультиплікативним. Розглянемо, як потрібно вибирати параметри лінійного конгруентного генератора, щоб отримати послідовність з повним періодом. Для отримання такої послідовності необхідно вибирати значення m = 2g -1, де g — довжина розрядної сітки комп'ютера. Для 32-розрядного комп'ютера m — найбільше ціле число, яке може бути відтворене в ньому, дане число дорівнює 231 - 1 = 2147483647 {один розряд відводиться під знак числа). У цьому разі ділення хі+1/m виконувати не обов'язково. Якщо в результаті роботи генератора буде отримане число яке більше ніж те, що може бути відтворене з комп'ютері, виникне переповнення розрядної сітки. Це призведе до втрати крайніх лівих двійкових знаків цілого числа, які перевищили допустимий розмір. Однак розряди, що залишились, саме і є значеннями хі+1 (mod 2g). Таким чином, під час генерування замість операції ділення можна скористатись переповненням розрядної сітки. Стосовно константи с теорема стверджує, що для отримання послідовності з повним періодом генератора значення с повинне бути непарним, і, крім того, а - 1 має ділитися на 4. Для такого генератора початкове значення х0 може бути довільним і лежати в діапазоні від 0 до m-1. Якщо с = 0, то отримуємо мультиплікативний конгруентний метод, який передбачає використання таких рекурентних виразів: xi = ахi (mod m). (2) Цей метод більш швидкодіючий, ніж попередній, але він не дає послідовності з повним періодом. Дійсно, з виразу (2) видно, що значення х = 0 може з'явитись тільки в тому випадку, якщо послідовність вироджується в нуль. Взагалі, якщо d - будь-який дільник m і xi кратне d, всі наступні елементи мультиплікативної послідовності хі+1, хі+2,… будуть кратними d. Таким чином, якщо с = 0, потрібно, щоб xi,- і m були взаємно простими числами з m і знаходились між 0 і m.. Що стосується вибору а, то у випадку, коли m =2g, де g ≥4, викладені в праці умови приводять до єдиної вимоги стосовно значення а: а ≡ 3 (mod 8) або а ≡ 5 (mod 8). У цьому випадку четверта частина всіх можливих значень множників дає довжину періоду, що дорівнює m/4, яка й буде максимальним періодом генератора.
Визначення якості генераторів
Ви можете застосувати різні тексти для визначення випадковості послідовності чисел. Жоден з тестів не скаже, що послідовність є випадковою, проте, він скаже, якщо вона немає такій. Тести можуть виявити не випадкові послідовності, але, якщо тест не знайшов недоліків, це не означає, що дана послідовність дійсно випадкова. Тести, проте, підвищують упевненість в генераторі випадкових чисел, який породив послідовність. Тепер ми стисло розглянемо декілька простих способів тестування послідовностей. Спершу розглянемо спосіб визначення того, наскільки близький розподіл чисел в послідовності відповідає очікуваному. Наприклад, ви намагаєтеся генерувати послідовність випадкових чисел від 0 9. Вірогідність появи кожної цифри рівна 1/10. Хай згенерувала наступна послідовність
9 1 8 2 4 6 3 7 5 2 9 0 4 2 4 7 8 6 2
Якщо ви підрахуєте число появ кожної цифри, то отримаєте результат
Цифри Число появ
0 1
1 1
2 4
3 1
4 3
5 1
6 2
7 2
8 3
9 2
Далі вам слід відповісти самому собі на питання, чи достатній схоже даний розподіл на очікуване вами. Пам'ятаєте: якщо генератор випадкових чисел хороший, він генерує послідовності випадково. У істинно випадковому варіанті всі послідовності можливі. Дійсно, як якась послідовність може бути не випадковою, якщо будь-яка послідовність можлива? Просто деякі послідовності менш схожі на те, якою повинна бути випадкова послідовність, чим інші. Ви можете визначити вірогідність того, що дана послідовність є випадковою, використовуючи критерій хи-квадрат. У критерії хи-квадрат очікувана кількість віднімається із спостережуваної кількості зустрічей числа в послідовності, що згенерувала. Цей результат називається V. Ви можете використовувати Vдля знаходження відсотка в таблиці значень хи-квадрат. Цей відсоток визначає вірогідність того, що була породжена випадкова послідовність. Мала таблиця хи-квадрат приведена на ріс.7-1; ви можете знайти повні таблиці в більшості книг за статистикою
p=99% p=95% p=75% p=50% p=25% p=5% n=5 0.5543 1.1455 2.675 4.351 6.626 11.07 n=10 2.558 3.940 6.737 9.342 12.55 18.31 n=15 5.229 7.261 11.04 14.34 18.25 25.00 n=20 8.260 10.85 15.45 19.34 23.83 31.41 n=30 14.95 18.49 24.48 29.34 34.80 43.77
Вибрані значення хи-квадрат. Для визначення вірогідності того, що послідовність не випадкова, знайдіть рядок в таблиці, показаній на ріс.7-1, з числом елементів послідовності; в даному випадку це 20. Потім шукайте число по рядку, яке більше V. В даному випадку це колонка 1. Це означає, що існує вірогідність 99% того, що приклад з 20 елементів матиме V більше 8,260. З іншого боку це означає, що існує вірогідність тільки в 1% того, що послідовність, що перевіряється, згенерувала випадковим чином. Щоб пройти через критерій хи-квадрат, вірогідність V повинна знизитися до рівня від 25% до 75%. Проте ви можете протиставити цьому виводу питання: Оскільки всі послідовності можливі, як може дана послідовність мати тільки однопроцентний шанс бути законною? Відповідь така: це всього лише вірогідність. Фактично, якщо ви застосовуєте критерій хи-квадрат, вам слід отримати декілька різних послідовностей і усереднений результат, щоб уникнути відкидання хорошого генератора випадкових чисел. Будь-яка одинична послідовність може бути знехтувана, але ряд різних послідовностей після усереднювання повинен давати добрий результат. З іншого боку, послідовність може пройти через критерій хи-квадрат і не бути випадковою. Наприклад, послідовність 1 3 5 7 9 1 3 5 7 9 пройде критерій хи-квадрат, але вона виглядає не дуже випадковою. В даному випадку згенерував пробіг по діапазону значень. Пробіг - це просто зростаюча або убуваюча послідовність чисел з довільним інтервалом. В даному випадку кожна група з п'яти цифр є зростаючою послідовністю і як така не може вважатися випадковою послідовністю. Можна створити тест для виявлення такої ситуації, але це виходить за рамки даної книги. Іншою характеристикою, належній оцінці, є довжина періоду: тобто, як багато чисел може згенерувати до початку повторення послідовності. Всі машинні генератори випадкових чисел завжди генерували послідовність, що повторюється. Чим довше період, тим краще генератор. Навіть якщо частота чисел усередині періоду розподілена рівномірно, числа не утворюють випадкову серію, оскільки дійсно випадкова серія не може достатньо повторюватися. У загальному випадку період в декілька тисяч чисел задовольняє більшості застосувань. Тест для з'ясування періоду може бути розроблений. Різні інші тести можуть бути застосовані для визначення якості генератора випадкових чисел. Напевно, можна написати більше програм для перевірки генераторів випадкових чисел, чим створити самих генераторів. Розглянемо ще один тест, який дозволить вам перевірити генератор випадкових чисел "візуально", використовуючи діаграму для демонстрації характеристик послідовності, що згенерувала. У ідеалі діаграма повинна грунтуватися на частоті кожного числа. Проте оскільки генератор може породжувати тисячі різних чисел, це не здійснимо. Замість цього створюватимуться діаграми, згруповані до десяти цифрам. Наприклад, оскільки породжувані числа лежать в області від 0 до 1, число 0.9365783 буде включено в групу 9, а число 0.34523445 буде включено в групу 3. Це означає, що діаграма виведення випадкових чисел має 10 ліній, кожна з яких представляє число попадань в групу. Програма також виводить середнє значення послідовності, яке може бути використане для виявлення змішення. Як і всі інші програми даного розділу, наступна програма виконується тільки на персональному комп'ютері IBM РС, який має адаптер кольорового графічного дисплея. Розроблені раніше функції Ran1 і Ran2, а також вбудована функція Турбо Паскаля Random, продемонстровані поряд для порівняння.
{ програма, яка порівнює три генератори випадкових чисел }
program RanGenerator;
uses
Graph;
const
COUNT = 1000;
var
freg1, freg2, freg3: array[0..9] of integer;
a2, a1: integer;
f, f2, f3: real;
r, r2, r3: real;
y, x: integer;
GraphDriver, GraphMode: integer;
{ відображення графічного виводу}
procedure Display;
var
t : integer;
begin
for t := 0 to 9 do
begin
Line(t*10, 180, t*10, 180-freg1[t]);
Line(t*10+110, 180, t*10+110, 180-freg2[t]);
Line(t*10+220, 180, t*10+220, 180-freg3[t]);
end;
end; {Display}
function Ran1: real;
var
t: real;
begin
t := (a1*32749+3) mod 32749;
a1 := Trunc(t);
Ran1 := Abs(t/32749);
end; {Ran1}
function Ran2: real;
var
t: real;
begin
t := (a2*10001+3) mod 17417;
a2 := Trunc(t);
Ran2 := Abs(t/17417);
end; {Ran2}
begin
{ перемикання на графічний режим, використовуючи режим 4 Cga/ega }
GraphDriver := CGA;
GraphMode := CGAC1;
InitGraph(GraphDriver, GraphMode, );
SetColor(2);
SetLineStyle(SolidLn, 0, NormWidth);
OutTextXy(80, 10, 'Comparison of Random');
OutTextXy(96, 20, 'Number Generators');
{ прорисовать базовые линии }
Line(0, 180, 90, 180);
Line(110, 180, 200, 180);
Line(220, 180, 310, 180);
OutTextXy(30, 190, 'Random Ran1 Ran2');
{инициализация переменных генераторов случайных чисел }
a1:=1; a2:=203;
f := 0; f2 := 0; f3 := 0;
for x := 0 to 9 do
begin { инициализация матриц частот }
freg1[x] := 0;
freg2[x] := 0;
freg3[x] := 0;
end;
for x := 1 to COUNT do
begin
r:=Random; { взять случайное число }
f:=f+r; { прибавить для вычисления среднего }
y:=Trunc(r*10);{ преобразовать в целое число от 0 до 9 }
freg1[y]:=freg1[y]+1;{ увеличить счетчик частоты }
r2 := Ran1; { взять случайное число }
f2:=f2+r2; { прибавить для вычисления среднег }
y:=Trunc(r2*10);{ преобразовать в целое число от 0 до 9}
freg2[y]:=freg2[y]+1;{ увеличить счетчик частоты }
r3 := Ran2; { взять случайное число }
f3:=f3+r3; { прибавить для вычисления среднего }
y:=Trunc(r3*10);{ преобразовать в целое число от 0 до 9}
freg3[y]:=freg3[y]+1;{увеличить счетчик частоты }
Display; { отобразить счетчики частот }
end;
ReadLn;
RestoreCrtMode;
WriteLn('mean of Random is: ', f/COUNT);
WriteLn('mean of Ran1 is: ', f2/COUNT);
WriteLn('mean of Ran2 is: ', f3/COUNT);
end.
У даній програмі кожна функція генерує 1000 чисел і на основі цього створюються таблиці частот. Процедура Display малює всі три матриці частот на екрані після генерації кожного випадкового числа так, що ви можете спостерігати зростання частот. На ріс.7-2 показано виведення кожного генератора випадкових чисел після генерації 1000 чисел. Середні значення рівні 0,489932 у Ran1, 0,4858311 у Ran2 і 0,494014 у Random. Це прийнятно.
Порівняння генераторів випадкових чисел
¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L-+-+-+-+-+-+-+-+-- L-+-+-+-+-+-+-+-+-- L-+-+-+-+-+-+-+-+-
Random Ran1 Ran2
----------------------------------------------------------.
Вивід з програми відображення роботи генераторів
випадкових чисел.
Для ефективного використання програми ви повинні спостерігати як за формою діаграми, так і за динамікою зростання, щоб виявити короткі цикли, що повторюються. Наприклад, Ran2 генерує значно менше чисел в області від 0,9 до 0,999999, чим Random і Ran1. Звичайно даний текст не є всеосяжним, але він допоможе вам зрозуміти спосіб, яким генератор породжує числа, і прискорить процес аналізу генераторів.
Використання декількох генераторів
Один простий метод, який покращує властивості випадкових послідовностей, що породжуються трьома генераторами, полягає в комбінуванні їх під управлінням однієї головної функції. Дана функція вибирає між двома з них, грунтуючись на результаті третьої. За допомогою цього методу ви можете отримати дуже довгий період і зменшити вплив циклів і зсувів. Функція, звана Combrandom, показана тут, здійснює комбінування виводів генераторів Ran1, Ran2, Random:
{ дана функція використовує три генератори для повернення одного випадкового числа}
function CombRandom: real;
var
f: real;
begin
f := Ran2;
if f>0.5 thenCombRandom := Random
else CombRandom := Ran1; { случайный выбор генератора }
end; {CombRandom}
Результат Ran2 використовується для того, щоб вирішити, Ran1 або Random видасть значення головної функції Combrandom. При такому методі період головної функції рівний або більше суми періодів Random і Ran1. Таким чином, даний метод робить можливим породження послідовності з дуже довгим періодом. Можна легко змінювати суміш Random і Ran1 зміною константи в операторові if, щоб отримати бажаний вами розподіл між цими двома генераторами. Крім того, ви можете додати додаткові генератори і здійснювати вибір між ними для отримання ще довшого періоду. Далі слідує програма для відображення діаграми Comprandom і її середнього значення. На ріс.7-3 показана фінальна діаграма після генерації 1000 чисел. Середнє значення Combrandom рівне 0,493361.
{ дана програма демонструє комбіноване виведення трьох генераторів випадкових чисел }
program MultiRandom;
uses
Graph;
const
COUNT=1000;
var
freg: array[0..9] of integer;
a2,a1: integer;
f, r: real;
y, x: integer;
GraphDriver, GraphMode: integer;
{ отображение графического представления работы генераторов }
procedure Display;
var
t: integer;
begin
for t := 0 to 9 do
Line(t*10+110, 180, t*10+110, 180-freg[t]);
end; {Display}
function Ran1: real;
var
t: real;
begin
t := (a1*32749+3) mod 32749;
a1 := Trunc(t);
Ran1 := Abs(t/32749);
end; {Ran1}
function Ran2: real;
var
t: real;
begin
t := (a2*10001+3) mod 17417;
a2 := Trunc(t);
Ran2 := Abs(t/17417);
end; {Ran2}
{данная функция использует три генератора для возврата одного случайного числа
}
function CombRandom real;
var
t: real;
begin
f := Ran2;
if f>0.5 then CombRandom := Random
else CombRandom := Ran1; {случайный выбор генератора }
end; {CombRandom}
begin
{ переключение на графический режим, используя режим 4 CGA/EGA }
GraphDriver := CGA;
GraphMode := CGAC1;
InitGraph(GraphDriver, GraphMode, );
SetColor(2);
SetLineStyle(SolidLn, 0, NormWidth);
OutTextXy(48, 10, 'вывод, полученный комбинированием ');
OutTextXy(40,20, 'три генератора случайных чисел ');
Line(110, 180, 200, 180);
a1:=1; a2:=203; {инициализация переменных для
генераторов случайных чисел }
f := 0;
for x:=0 to 9 do freg[x]:=0; {инициализация матрицы
частот}
for x := 1 to COUNT do begin
r:=CombRandom; { взять случайное число }
f:=f+1; { прибавить для вычисления среднего }
y:=Trunc(r*10);{ преобразовать в целое число от 0 до 9}
freg[y]:=freg[y]+1;{ увеличить счетчик частоты } Display;
end;
ReadLn;
RestoreCrtMode;
WriteLn('Среднее случайное число равно : ', f/COUNT);
end.
.
Вивід, отриманий комбінуванням трьох генераторів випадкових чисел.
¦ ¦
¦ ¦ ¦ ¦
¦¦¦¦¦¦¦¦¦¦
¦¦¦¦¦¦¦¦¦¦
¦¦¦¦¦¦¦¦¦¦
¦¦¦¦¦¦¦¦¦¦
¦¦¦¦¦¦¦¦¦¦
L++++++++
------------------------------------------------------
Фінальне відображення функції Combrandom
Моделювання
Частина даного розділу, що залишилася, присвячена застосуванням генераторів випадкових чисел для моделювання на комп'ютерах. Промоделіровать можна все; успіх моделювання залежить головним чином від того, наскільки добре програміст зрозумів ситуацію, яку треба моделювати. Оскільки реальні ситуації часто мають тисячі змінних, багато речей насилу піддаються моделюванню. Проте, існують ситуації, які дуже добре підходять для моделювання. Моделювання важливе по двох причинах. По-перше, воно дозволяє вам змінювати параметри моделювання для перевірки і спостереження можливих результатів в той час, як в реальності такі експерименти можуть бути і дорогими і небезпечними. Наприклад, моделювання атомної електростанції може бути використане для перевірки впливу різних типів відмов без якої-небудь небезпеки. По-друге, моделювання дозволяє нам створювати ситуації, які не можуть відбутися в реальному житті. Наприклад, психологи можуть захотіти вивчити вплив безперервного зростання інтелекту миші до людського, щоб визначити, коли миша проходитиме лабіринт найшвидше. Хоча це не може бути зроблено в реальному житті, моделювання може допомогти проникненню в природу співвідношення інтелекту і інстинкту. Далі розберемо перший з двох прикладів, в яких використовуються генератори випадкових чисел.
Моделювання черг обслуговування
У першому прикладі моделюється обслуговування в бакалійній лавці. Припустимо, що лавка відкрита 10 годин в день з піковим годинником з 12 до 13 і з 17 до 18 годин. Період з 12 до 13 годин має навантаження в два рази, а з 17 до 18 - в три рази більше звичайною. При моделюванні один генератор "породжує" покупців, другий генератор визначає час обслуговування покупця, а третій вирішує, в яку чергу піде покупець. Мета моделювання полягає в тому, щоб допомогти керівникові знайти оптимальне число черг, які повинні працювати в звичайний день за умови, що число людей в черзі у будь-який час не перевищувало б 10 і касири не чекали б покупців. Ключ до даного типу моделювання полягає в створенні багатьох процесів. Хоча Турбо Паскаль безпосередньо не підтримує паралельності, ви можете моделювати за допомогою безлічі процесів або за допомогою головної програми з циклами. Далі показана програма з її глобальними даними для моделювання черг без підтримки процедур і функцій:
var
gueues, count: array[0..9] of integer;
open: array[0..9] of boolean;
cust, time: integer;
a1, a2: integer;
y, x: integer;
change: boolean;
GraphDiver, GraphMode: integer;
begin
{переключение на графику, используя режим 4 CGA/EGA}
GraphDriver := CGA;
GraphMode := CGAC1;
InitGraph(GraphDriver, GraphMode, );
SetColor(2);
SetLineStyle(SolidLn, 0, NormWidth);
a1:=1; a2:=203; {инициализация переменных генератора
случайных чисел}
change := FALSE;
cust := 0;
time := 0;
for x:=0 to 9 do begin
gueues[x]:=0; {инициализация очереди }
open[x]:=FALSE; { нет покупателей или очередей в
начале дня }
count[x]:=0; {счетчик очереди }
end;
OutTextXy(155, 190, '1 10');
OutTextXy(8,190,'Check-out lines: ');
{ теперь начинается день открытием первой очереди }
open[0] := TRUE;
repeat
AddCust;
AddQueue;
Display;
CheckOut;
Display;
if (time>30) and (time<50) then AddCust;
if (time>70) and (nime<80) then begin
AddCust;
AddCust;
end;
time := time+1;
until time>100; { конец дня }
ReadLn;
RestoreCrtMode;
end.
Елемент Graph.P включений, щоб програма могла використовувати графічні функції. Головний цикл управляє всім моделюванням:
repeat
AddCust;
AddQueue;
Display;
CheckOut;
Display;
if (time>30) and (time<50) then AddCust;
if (time>70) and (time<80) then begin
AddCust;
AddCust;
end;
time := time+1;
until time>100; { конец дня }
Функція Addcust використовує або Ran1, або Ran2 для генерації числа покупців, що встають в черзі при кожному запиті. Функція Addquece використовується для приміщення покупців в черзі відповідно до результату Ran2, а також відкриває нові черги, якщо ті, що всі існують переповнені. Функція Display відображає програму моделювання. Checkout використовує Ran2 для призначення кожного покупця в чергу з відповідним збільшенням лічильника черги; кожен виклик зменшує лічильник на 1. Коли лічильник покупців рівний 0, черга стає порожньою. Змінна time (час) змінює інтенсивність, з якою генеруються покупці, для того, щоб відстежити годинні списи. Кожен прохід по циклу представляє одну десяту години. На ріс.7-4, 7-5 і 7-6 показані стани черг, коли time=28, time=60 і time=88, що відповідає нормальному часу, кінцю першого піку і кінцю другого піку, відповідно. Відзначимо, що в кінці другого піку потрібно максимум п'ять черг, Якщо моделююча програма написана правильно, то в бакалійній лавці п'ять черг, що залишилися, не потрібно.
gueue 1: 10 time: 28
gueue 2: 8
gueue 3: 0
gueue 4: 0
gueue 5: 0
gueue 6: 0
gueue 7: 0
gueue 8: 0
gueue 9: 0
gueue 10: 0
Очередь ¦
¦
¦ ¦
¦ ¦
¦ ¦
¦ ¦
¦ ¦
¦ ¦
1 10
Рис.7-4. Состояние очередей, когда time=28:
gueue 1: 6 time: 60
gueue 2: 8
gueue 3: 8
gueue 4: 1
gueue 5: 0
gueue 6: 0
gueue 7: 0
gueue 8: 0
gueue 9: 0
gueue 10: 0
Очередь ¦ ¦
¦ ¦
¦ ¦ ¦
¦ ¦ ¦
¦ ¦ ¦
¦ ¦ ¦ ¦
1 10
Рис.7-5. Состояние очередей, когда time=60:
gueue 1: 8 time: 80
gueue 2: 9
gueue 3: 6
gueue 4: 6
gueue 5: 7
gueue 6: 0
gueue 7: 0
gueue 8: 0
gueue 9: 0
gueue 10: 0
Очередь ¦
¦ ¦
¦ ¦ ¦
¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦
1 10
Ріс.7-6. Стан черг, коли time=88: Ви можете безпосередньо управляти різними змінними в програмі. По-перше, ви можете змінити шлях і число покупців, що прибувають. Ви також можете змінити функцію Addcost, щоб вона повертала число покупців в піковий годинник з великим або меншим поступовим збільшенням або зменшенням. Програма припускає, що покупці випадковим чином вибирають, в яку чергу їм встати. Такий підхід справедливий для одних покупців, а інші вибиратимуть найкоротшу чергу. Ви можете врахувати це, змінивши функцію Addqueue так, щоб вона в деяких випадках поміщала покупців в найкоротшу чергу, а в деяких - випадковим чином. При моделюванні не враховуються такі випадковості, як булка, що впала, або буйний покупець в черги, які викликають тимчасові зупинки черги. Цілком програма виглядає таким чином:
program simulation; {моделирование очередей в бакалейной
лавке }
uses
Graph;
var
gueues, count: array[0..9] of integer;
open: array[0..9] of boolean;
cust, time: integer;
a1, a2: integer;
y,x: integer;
change: boolean;
GraphDriver, GraphMode: integer;
function Ran1: real;
var
t: real;
begin
t := (a1*32749+3) mod 32749;
a1 := Trunc(t);
Ran1 := Abs(t/32749);
end; {Ran1}
function Ran2: real;
var
t: real;
begin
t := (a2*10001+3) mod 17417;
a2 := Trunc(t);
Ran2 := Abs(t/17417);
end; {Ran2}
function CombRandom: real;
{random selection of generators} 2
var
f: real;
begin
f := Ran2;
if f>0.5 then CombRandom := Random
else CombRandom:=Ran1;{случайный выбор генераторов}
end; {CombRandom}
{ добавление покупателей в очередь }
procedure AddCust;
var
f, r: real;
begin
if change then f:=Random {переключение между двумя }
else f := Ran2; {генераторами }
if f>0.5 then
if f>0.6 then cust:=cust+1 {добавить одного покупателя}
else if f>0.7 then cust:=cust+2 {два покупателя}
else if f<0.8 then cust:=cust+3 {три покупателя }
else cust := cust+4; {четыре покупателя }
end; {AddCust}
{ обслуживание покупателя }
Procedure CheckOut;
var
t: integer;
begin
for t := 0 to 9 do
begin
if gueues[t]<>0 then
begin
{получить время обслуживания }
while count[t]=0 do count[t]:=Trunc(Ran1+5);
{новый покупатель требует времени обслуживания }
count[t]:=count[t]-1;
if count[t]=0 then gueues[t]:=gueues[t]-1;
{удаление покупателя}
end;
if gueues[t]=0 then open[t]:=FALSE;{закрытие очереди}
end;
end; {CheckOut}
{возвращается TRUE, если очередь переполнена }
function AllFull: Boolean;
var
t: integer;
begin
AllFull := TRUE;
for t := 0 to 9 do
if (gueues[t]<10) and open[t] then AllFull:=FALSE;
end; {AllFull}
{данная процедура вводит новые очереди }
procedure AddQueue;
var
t, line: integer;
done: Boolean;
begin
done := FALSE;
while cust<>0 do
begin
if AllFull then
begin
t:=0;
repeat
if not open[t] then
begin
open[t]:=TRUE;
done:=TRUE;
end;
t:=T+1;
until done or (t=9);
end
else
begin
Line:=Trunc(Ran2*10);
if open[line] and (gueues[line]<10) then
begin
gueues[line]:=gueues[line]+1;
cust:=cust-1;
end;
end;
if AllFull and open[9] then cust:=0; {all full}
end;
end; {AddQueue}
{очистить символы длины, начиная с позиции Х, У }
procedure ClrVed(x,y,len: integer);
var
i: integer;
s: string[80];
begin
for i := 1 to len do
s := concat(Chr(219), Chr(219));
SetColor(0);
OutTextXy(x, y, s);
SetColor(2);
end; {ClrVid}
{отображение экрана результатов моделирования очереди }
procedure Display;
var
t: integer;
value: string[80];
begin
cirVid(170, 10, 3);
str(time, value);
OutTextXy(120, 10, 'Time: ');
OutTextXy(170, 10, value);
for t := 0 to 9 do
begin
{erase old line}
SetColor(0);
Line((t*10)+160, 180, (t*10)+160, 180);
{нарисовать новое состояние моделирования }
SetColor(2);
Circle((t*10)+160, 180, 3);
Line((t*10)+160, 180, (t*10)+160, 180-gueues[t]*10);
{дать также текстовый вывод }
OutTextXy(8, t*10, 'gueue');
str(t+1, value);
value := concat(value, ':');
OutTextXy(56, t*10, value);
ClrVid(80, t*10, 3);
str(gueues[t], value);
OutTextXy(80, t*10, value);
end;
end; {Display}
begin
{переключение на графику, используя режим 4 CGA/EGA }
GraphDriver := CGA;
GraphMode := CGAC1;
InitGraph(GraphDriver, GraphMode, );
SetColor(2);
SetLineStyle(SolidLn, 0, NormWidth);
a1:=1; a2:=203; {инициализация переменных генератора
случайных чисел }
change:=FALSE;
cust:=0;
time:=0;
for x := 0 to 9 do begin
gueues[x]:=0; {инициализировать очереди }
open[x]:=FALSE;{нет покупателей или очередей в начале
дня }
count[x]:=0; {счетчик очереди }
end;
OutTextXy(155, 190, '1 10');
OutTextXy(8, 190, 'Check-out lines; ');
{теперь начинается ден.
открытием первого пункта обслуживания
}
open[0]:=TRUE;
repeat
AddCust;
AddQueue;
Display;
CheckOut;
Display;
if (time>30) and (time<50) then AddCust;
if (time>70) and (time<80) then begin
AddCust;
AddCust;
end;
time:=time+1;
until time>100; { конец дня }
ReadLn;
RestoreCrtMode;
end.
