НОУ ІНТУІТ, Лекція, Генерування на ЕОМ послідовностей рівномірно розподілених випадкових
У стандартному математичному та програмному забезпеченні різних типів ЕОМ є спеціальні процедури та підпрограми для генерації рівномірно розподілених послідовностей псевдовипадкових чисел.
В даний час всі мови високого рівня мають програмні генератори рівномірно розподілених послідовностей псевдовипадкових чисел. Їх називають датчиками випадкових чисел. Датчики випадкових чисел зазвичай мають імена: RAN, RAND, RANDU, RND , RANDOM, RANDOMIZE і т.д. Ці імена отримані від англійського слова random, що означає випадковий або вибраний навмання. Тому датчики випадкових чисел іноді називають рандомізаторами.
Датчики випадкових чисел зазвичай генерують послідовність дійсних чисел Un рівномірно розподілених між нулем і одиницею, тобто. послідовність випадкових дробів в інтервалі [0,1]. Але спочатку датчики генерують послідовність цілих випадкових чисел xi в інтервалі від нуля до m, де m - розмір машинного слова (на одиницю менше максимального цілого числа, що розміщується в машинному слові).
Як мовилося раніше, для 32-х розрядного машинного слова:
m = 231 = 2147483648;
1/m = 0.4656613 E-9.
Наведемо датчик рівномірно розподілених випадкових чисел RANDU.
Цей датчик спеціально призначений системи IBM і утворює 2 29 значень перед початком повторень, тобто. довжина циклу дорівнює 229 (при 32-х розрядному машинному слові). Алгоритм датчика реалізує метод залишку ступенів (рис. 8.1).
Призначення датчика RANDU:
Обчислення рівномірно розподілених випадкових дійсних чисел YF в інтервалі [0,1] тавипадкових цілих чисел IY в інтервалі [0,231]. Як вход служить ціле випадкове число IX, на виході утворюється нове ціле число IY і речовинне YF.
Звернення до датчика:
IX – при першому зверненні – непарне ціле число з числом цифр.
Після першого звернення IX = IY , де IY - ціле число, обчислене при попередньому обігу.
IY - отримане в результаті ціле випадкове число, необхідне при подальшому зверненні. IY знаходиться в інтервалі [0, 231].
YF - отримане в результаті рівномірно розподілене дійсне число в інтервалі [0,1], представлене у формі з плаваючою комою.
Використовуючи датчик RANDU, побудуємо алгоритм обчислення послідовності рівномірно розподілених випадкових чисел та її друк (рис. 8.2).
Алгоритм обчислення послідовності рівномірно розподілених випадкових чисел.
N – довжина послідовності (кількість випробувань).
IX - початкове значення, непарне ціле число з числом цифр >