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

n=k+ t, k=n/2, x
–
наименьшее целое, не меньшее
x
. 
Рекурсивно повторяя процесс понижения степени, получим требуемый 
результат. 
(22) 
(23
)
(24) 
(25) 
(26) 

---

120 
Алгоритм, основанный на использовании бинарного представления 
номера вычисляемого элемента 
n, 
потребует еще меньшего числа операций:
Рассмотрим 
функцию 
вычисления 
значения 
элемента 
последовательности, имеющего номер на 
2
i
больше, чем номер элемента, 
заданного в качестве аргумента (28).
Пусть в качестве аргумента функции 
F
i
задан элемент 
последовательности с номером 
j
. Тогда при 
b
i
=1 
значением функции 
является элемент последовательности с номером 
j + 2
i
, а при элемент с 
номером 
j.
Коэффициенты a
i
и 
c
i
 
определяются рекуррентно, согласно (29), 
(30), и могут быть вычислены однократно в начале работы. Их количество 
равно 
M= log N
, где
N
—
максимальный номер требуемого в ходе 
выполнения всех вычислений элемента последовательности. Таким образом,
зная элемент последовательности с нулевым номером, можно, используя 
(31), вычислить произвольный элемент последовательности за 
M
обращений 
к функции 
F
i
.
 
К недостаткам линейных конгруэнтных генераторов относится
: 
-
малая длина периода ПСЧ, обусловленная тем, что для 
эффективной реализации операций умножения и сложения по модулю m, 
разрядность модуля ограничена разрядностью операндов, непосредственно 
обрабатываемых процессором; 
(28) 
(29) 
(30) 
(31) 
(27)

---

121 
-
d-
мерные точки, координаты которых сформированы с помощью 
(25), располагаются не более чем в d!m гиперплоскостях размерности (d –
1). 
Этот факт значительно ограничивает применимость линейных конгруэнтных 
генераторов, например, в геометрических приложениях. В частности, при 
a = 
216 
+ 3, c = 0 и m = 2
31 
(параметры, использованные
в библиотеке IBM 
System 360/370) в трехмерном случае (
d = 3
) таких плоскостей не более 16.