Page 57 - 2579

підібрані значення іноді називають магічними
числами.
Наведений приклад ілюструє й те, що
конгруентна послідовність завжди є циклічною, тобто
вона починає повторюватися через певну кількість
випадкових чисел. Кількість значень, після яких
випадкові числа починають повторюватися,
називається повним періодом генератора і є основним
його параметром. Значення повного періоду залежать
від розрядності комп'ютера, а також від значень т, с, а і
х 0 . Існує теорема, яка визначає умови існування
повного періоду генератора, а саме:
- числа с і т повинні бути взаємно простими,
тобто мати взаємний дільник 1;
- значення b= а - 1 має бути кратним q для
кожного простого q, бути дільником т;
- значення b має бути кратним 4, якщо m кратне 4.
Достатність цих умов уперше було доведено
Халлом (Hull) і Добеллом (Dobell).
Якщо с > 0, то генератор називається мішаним,
а якщо с = 0 — мультиплікативним.
Розглянемо, як потрібно вибирати параметри
лінійного конгруентного генератора, щоб отримати
послідовність з повним періодом. Для отримання
такої послідовності необхідно вибирати значення т =
g
2 - 1, де g - довжина розрядної сітки комп'ютера. Для
32-розрядного комп'ютера т — найбільше ціле число,
яке може бути відтворене в ньому, дане число
31
дорівнює 2 - 1 = 2147483647 (один розряд
відводиться під знак числа). У цьому разі ділення
X i+1/m виконувати не обов'язково. Якщо в результаті
роботи генератора буде отримане число х і+1, яке
більше ніж те, що може бути відтворене в комп'ютері,
виникне переповнення розрядної сітки. Це призведе

51