Page 58 - 2579

до втрати крайніх лівих двійкових знаків цілого
числа, які перевищили допустимий розмір. Однак
розряди, що залишились, саме і є значеннями х І+1
g
(mod 2 ). Таким чином, під час генерування замість
операції ділення можна скористатись
переповненням розрядної сітки.
Стосовно константи с теорема стверджує, що
для отримання послідовності з повним періодом
генератора значення с повинне бути непарним, і, крім
того, а- 1 має ділитися на 4. Для такого генератора
початкове значення х 0 може бути довільним і лежати
в діапазоні від 0 до т - 1. Якщо с = 0, то отримуємо
мультиплікативний конгруентний метод, який
передбачає використання таких рекурентних
виразів:
x i= аx i (mod m). (3.2)

Цей метод більш швидкодіючий, ніж
попередній, але він не дає послідовності з повним
періодом. Дійсно, з виразу (3.2) видно, що значення
х і+1 = 0 може з'явитись тільки в тому випадку, якщо
послідовність вироджується в нуль. Взагалі, якщо d —
будь-який дільник m i x i кратне d, всі наступні
елементи мультиплікативної послідовності х і+1, х і+2,...
будуть кратними d. Таким чином, якщо с = 0, потрібно,
щоб x i і т були взаємно простими числами з т і
знаходились між 0 і т.
Що стосується вибору а, то у випадку, коли m =
g
2 , де g >= 4 значення а=:
а = 3 (mod 8) або а = 5 (mod 8).
У цьому випадку четверта частина всіх
можливих значень множників дає довжину періоду,
що дорівнює т/4, яка й буде максимальним періодом
генератора.

52