слідовність, молодші значущі двійкові розряди ( X n mod 2 ) якої мають довжину періоду 2 55 - 1 .
Алгоритм В. (Адитивний генератор чисел). У комірки пам'яті Y [1], Y [2], ..., Y [55] записано безліч значень X 54 , X 53 , ..., X 0 відповідно; на початку вважають j =24, k =55.
При реалізації цього алгоритму на виході послідовно отримуємо числа X 55 , X 56 , ...
В1. [Підсумовування] (Якщо на виході ми опиняємося в точці X n , то
Y [j] = X n - 24 , а Y [k] = X n - 55 .
Y [k] ¬ (Y [k] + Y [j] ) mod 2 e .
В2. [Просування] Зменшимо j і k на 1. Якщо j=0 , то привласнимо j ¬ 24 , інакше, якщо k=0 , привласнити k ¬ 55 .
Числа 24 і 55 у виразі (4.2) називаються запізненням, а числа X n , визначені в (4.2) - послідовністю Фібоначчі з запізненням.
Можливо побудувати досить хороший генератор випадкових чисел, використовуючи всілякі лінійні комбінації X n - 1 , ... , X nk для малих k . У цьому випадку найкращий результат виходить, коли модуль m є великим простим числом; наприклад, m - найбільше просте число, яке можна записати одним комп'ютерним словом.
Формула для генерації може бути обрана такою:
X n =(a 1 X n - 1 + ... + a k X nk) mod p (4.3)
з періодом p k - 1 . Тут X 0 , X 1 , ..., X k - 1 можуть бути обрані довільно, але не рівні нулю одночасно.
Звернемося до процесу генерування випадкових чисел 0 і 1 за формулою (4.3). Задамо довільно ненульове двійкове слово (1 0 1 1), тобто X 1 =1, X 2 =0 , X 3 =1, X 4 =1; k =4; p =2. Задамо довільно коефіцієнти а 1 , а < b align="justify"> 2 , а 3 , а 4 двійковим словом (0 0 1 1), тобто а 1 =0, а < b align="justify"> 2 =0, а 3 =1, а 4 =1 . Перепишемо (4.3) з урахуванням введених величин, отримаємо:
X n =(a 1 ? X
