Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

Требования, предъявляемые к генераторам псевдослучайных 
чисел, предназначенных для использования на многопроцессорных 
системах
:

---

119 
1) возможность формирования последовательности достаточно 
большой длины;
2) возможность определения любого элемента последовательности за 
короткое время без вычисления всех ее предыдущих членов. 
Линейно-конгруэнтные генераторы 
Линейные конгруэнтные генераторы (22) позволяют с помощью 
соотношений (23) - (24) одновременно вычислять на векторном компьютере, 
оснащенном 
k 
процессорами, очередные 
k 
элементов последовательности, 
используя для вычисления каждого элемента порядка 
O(1)
операций [2]. 
Для этого достаточно один раз предварительно вычислить величины 
 a
k
 mod m
и 
Выражение (23) позволяет вычислять элементы с произвольным 
номером n, используя порядка 
O(logn)
операций.
Например, понизим вдвое 
степени стоящих в скобках слагаемых. Используя (25), можно преобразовать 
(23) к виду (26) где
n=k+ t, k=n/2, x
– 
наименьшее целое, не меньшее
x
. 
Рекурсивно повторяя процесс понижения степени, получим требуемый 
результат.
(22) 
(23
)
(24) 
(25) 
(26) 

---

120 
Алгоритм, основанный на использовании бинарного представления 
номера вычисляемого элемента 
n, 
потребует еще меньшего числа операций: 
Рассмотрим 
функцию 
вычисления 
значения 
элемента 
последовательности, имеющего номер на