Програмне генерування РВП0 1 (стр. 4 из 5)

Зараз найчастіше застосовується метод генерації випадкових чисел, що грунтується на використанні рівняння

при виконанні наступних умов

Відзначимо, що R - це попереднє число, а R - наступне. Даний метод інколи називають лінійним порівняльним методом. Формула така проста, що ви можете подумати, що генерувати випадкові числа просто. Проте, це пастка: наскільки добре працює дана формула, дуже сильно залежить від значення а, з і m. Вибір значень інколи більшою мірою мистецтво, ніж наука. Існують складні правила, які можуть допомогти вам вибрати значення; проте, ми розглянемо лише декілька простих правил і прикладів. Модуль (m) має бути досить великим, оскільки він визначає область випадкових чисел.

Операція узяття по модулю породжує залишок від ділення числа на модуль. Отже, 10 по модулю 4 рівне 2. Таким чином, якщо модуль дорівнює 12, то формулою породжуються числа від 0 до 11, а якщо модуль дорівнює 21425, то породжуються числа від 0 до 21424. Вибір множника а і прирости з є дуже складним завданням. У загальному випадку множник може бути задоволений великим, а приріст - маленьким. Безліч спроб і перевірок необхідна, аби створити хороший генератор. Як перший приклад тут приведений один з найчастіше використовуваних генераторів випадкових чисел. Рівняння, показане в Rаn1 використовується як основа для генератора випадкових чисел у ряді популярних мов.

Дана функція має три головні особливості. По-перше, випадкові числа насправді є цілими, хоча функція повертає дійсні числа. Даний метод працює з цілими числами, але генератори випадкових чисел, як це прийнято, повинні повертати числа в межах від 0 до 1, що означає, що це мають бути числа з плаваючою комою. По-друге, початкове значення задається через глобальну змінну а1. До першого виклику Ran1 змінна а1 має бути встановлена в 1. По-третє, в Ran1 випадкові числа діляться на модуль перш, ніж вони будуть повернені функцією, для того, щоб числа лежали в області від 0 до 1. Якщо ви поцікавитеся значенням глобальної змінної а1 до повернення рядка, то воно повинне лежати в області від 0 до 32748. Отже, коли а1 ділиться на 32749, отримане число буде більше або рівне 0 і менше 1. Багато генераторів випадкових чисел не застосовні, оскільки вони породжують не рівномірний розподіл або мають короткий цикл повторення. Навіть коли ці недоліки не дуже впадають в очі, вони можуть породити змішаний результат, якщо такий генератор використовується знову і знову. Рішення полягає в тому, аби створити різні генератори і застосовувати їх індивідуально або спільно для здобуття якісніших послідовностей випадкових чисел. Вживання декількох генераторів може згладити розподіл послідовності за рахунок зменшення малих змішень окремих генераторів. Далі приведена функція генерування випадкових чисел, звана Ran2, яка породжує хороший розподіл:

Обоє цих генератора випадкових чисел породжують хороші послідовності випадкових чисел. Проте залишаються питання: чи досить "випадковою" є послідовність? Чи хороші дані генератори?

3.2 Визначення якості генераторів

Ви можете застосувати різні тексти для визначення випадковості послідовності чисел. Жоден з тестів не скаже, що послідовність є випадковою, проте, він скаже, якщо вона не є такій. Тести можуть виявити не випадкові послідовності, але, якщо тест не знайшов недоліків, це не означає, що дана послідовність дійсно випадкова. Тести, проте, підвищують упевненість в генераторі випадкових чисел, який породив послідовність. Тепер ми коротко розглянемо декілька простих способів тестування послідовностей. Спершу розглянемо спосіб визначення того, наскільки близький розподіл чисел в послідовності відповідає очікуваному. Наприклад, ви намагаєтеся генерувати послідовність випадкових чисел від 0 до 9. Вірогідність появи кожної цифри дорівнює 1/10. Хай згенерувала наступна последовательность

Якщо ви підрахуєте число появ кожної цифри, то отримаєте результат

Далі вам слід відповісти самому собі на питання, чи досить схожий даний розподіл на очікуване вами. Пам'ятаєте: якщо генератор випадкових чисел хороший, він генерує послідовності випадково. У істинно випадковому варіанті всі послідовності можливі. Дійсно, як якась послідовність може бути не випадковою, якщо будь-яка послідовність можлива? Просто деякі послідовності менш схожі на те, якою має бути випадкова послідовність, чим інші. Ви можете визначити вірогідність того, що дана послідовність є випадковою, використовуючи критерій хі-квадрат. У критерії хі-квадрат очікувана кількість віднімається із спостережуваної кількості зустрічей числа в послідовності, що згенерувала. Цей результат називається V. Ви можете використовувати Vдля знаходження відсотка в таблиці значень хі-квадрат. Цей відсоток визначає вірогідність того, що була породжена випадкова послідовність. Мала таблиця хі-квадрат приведена на рисунку (3.1); ви можете знайти повні таблиці в більшості книг за статистикою

Рис. 3.1. Мала таблиця хі-квадрат

Вибрані значення хі-квадрат. Для визначення вірогідності того, що послідовність не випадкова, знайдіть рядок в таблиці, показаній на рис. (3.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, продемонстровані поруч для порівняння.

У даній програмі кожна функція генерує 1000 чисел і на основі цього створюються таблиці частот. Процедура Display малює всі три матриці частот на екрані після генерації кожного випадкового числа так, що ви можете спостерігати зростання частот. На рис.(3.2) показано виведення кожного генератора випадкових чисел після генерації 1000 чисел. Середні значення дорівнюють 0,489932 в Ran1, 0,4858311 y Ran2 і 0,494014 в Random. Це прийнятно.

Рис. 3.2. Порівняння генераторів випадкових чисел

Для ефективного використання програми ви повинні спостерігати як за формою діаграми, так і за динамікою зростання, аби виявити короткі цикли, що повторюються. Наприклад, Ran2 генерує значно менше чисел в області від 0,9 до 0,999999, чим Random і Ran1. Звичайно даний текст не є всеосяжним, але він допоможе вам зрозуміти спосіб, яким генератор породжує числа, і прискорить процес аналізу генераторів.