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

1.3 Програмний спосіб

При програмному способі наступне випадкове число

дістають за допомогою рекурентного співвідношення

Генеровані так випадкові числа називаються псевдовипадковими (псевдо... від грец. yeudoV — обман, вигадка, помилка; відповідає поняттям «несправжній», «неправильний»), оскільки між двома сусідніми числами існує залежність. Функцію

вибирають складною, що включає логічні перетворення, аби згадана залежність практично не впливала на результат.

Один із перших алгоритмів утворення випадкових чисел за допомогою рекурентного співвідношення — метод серединних квадратів, запропонований 1946 року фон Нейманом і Метрополісом. Сутність його розкриємо спочатку на прикладі, а далі розглянемо загальний випадок.

Приклад.

Загальний випадок.

Нехай

— m-розрядне двійкове число (0 < < 1), причому — парне. Загальний вигляд :

де коефіцієнти

набувають значення 0 або 1.

Квадрат цього числа

Виокремимо середні розряди цього числа і покладемо

Як показали статистичні випробування, утворювані таким способом випадкові числа мають розподіл, близький до РВП [0, 1]. Очевидний недолік методу серединних квадратів полягає ось у чому. У разі відсутності заміни нульового значення випадкового числа, котре може з’явитися в результаті наступної спроби, якимось іншим, усі наступні числа послідовності будуть нулями.

Можливе циклічне повторення й інших цифр. Нехай, наприклад, потрібно дістати серію випадкових чотирицифрових десяткових чисел

методом серединних квадратів. Розглянемо випадок, коли за початкове число даної серії взято 4500:

і т.д.

Недоліки методу серединних квадратів обмежують його практичне застосування, хоча раніше до цього методу вдавалися завдяки його простоті.

Загальної теорії побудови псевдовипадкових чисел досі не створено. Вигляд фунції

установлюють емпірично. Ця функція містить різні арифметичні та логічні операції. Якість утворюваних чисел перевіряється з допомогою спеціальних тестів.

Тепер майже всі стандартні бібліотечні програми обчислення послідовності рівномірно розподілених випадкових чисел грунтуються на конгруентних методах. В основу кожного з них покладено поняття конгруентності.

Два цілі числа A і B конгруентні (порівнянні) за модулем m (де m — ціле число) тоді і тільки тоді, коли існує таке ціле число k, що A – B = km, тобто коли різниця A – B ділиться на m без остачі (числа A та B дають однакові остачі при діленні на абсолютну величину числа m). Це визначення записується як

і читається «А конгруентне В за модулем m». Наприклад, 13 º 3 (за модулем 10), 124 º 4 (за модулем 10), 5 º 1 (за модулем 4), 4339 º 39 (за модулем 100 ) і т.д.

Найвідомішими є такі конгруентні методи: мультиплікативний, мішаний і адитивний

Мультиплікативний конгруентний метод(метод лишків)

Випадкове число

Î РВП [0, 1] дістаємо перетворенням цілих чисел , що визначаються з допомогою рекурентного виразу

(2)

де a і m — невід’ємні цілі числа.

Згідно з (2) для знаходження наступного випадкового числа

достатньо виконати такі дії:

1) взяти останнє випадкове число

;

2) помножити його на коефіцієнт a ;

3) добуток поділити на модуль m;

4) остачу від ділення вважати шуканим випадковим числом

; це буде одне з цілих чисел 0, 1, 2, 3, . . . , m – 1.

Для генерування послідовності випадкових чисел

потрібно мати початкове число , множник a і модуль m. При виборі a і m потрібно виявити певну обережність. Коли a = 1, то = при будь-якому і . Коли = 0, то = 0 при довільному і . Очевидно, що будь-який генератор псевдовипадкових чисел може дати лише скінченну множину цілих випадкових чисел; після чого послідовність повторюватиметься.

Період (довжина) послідовності залежить від розрядності ЕОМ та вибраного модуля, а статистичні властивості — від вибору початкового числа та множника. Отже, вибирати

потрібно так, щоб забезпечити максимальний період і мінімальну кореляцію (автокореляцію).

Мультиплікативний конгруентний метод пояснимо, розглянувши процес генерування десяткових дробів

з десятьма знаками після коми. Перепишемо формулу (2), узявши — довільне непарне число, що не ділиться на 5:

Нехай x₀= 123456789, тоді

і т.д.

У системах ЕОМ типу IBM широко застосовується метод Хатчинсона. Двійкові числа в цих машинах подаються 32 розрядами: 31 розряд містить значущі цифри, крайній зліва розряд показує знак числа. За модуль беруть

множник Максимальна довжина послідовності випадкових чисел дорівнює m – 1; 0,46566113 . Запишемо програму цього датчика випадкових чисел мовою фортран.

SUBROUTINE RAND (N1, N, R)

1. N = 1220703125 ´ N1

2. IF(N)3,4,4

3. N = N + 2147483647 + 1

4. NI = N

5. R = N

6. R = R´0.4656613E – 9

7. RETURN

8. END

У програмі

— ціле число між 1 і — випадкове число з плаваючою крапкою (оператори 5 і 6 дають результати з плаваючою крапкою). Від’ємне число N може виникнути після команди 1 у результаті відкидання старших розрядів, тому оператор 3 змінює його значення.

Щоб дістати кілька послідовностей випадкових чисел РВП [0, 1], необхідно ввести різні значення початкових чисел:

, а щоб повторити початковий відрізок будь-якої послідовності, достатньо всередині основної програми присвоїти відповідній змінній N1її початкове значення і повторити весь цикл звертань до генератора.