Составители:
Рубрика:
75
Первое значение является наилучшим возможным расстоянием
при n(мерной выборке для генератора модуля m. В табл. 3.9 представ
лены значения наилучшего расстояния в зависимости от n и m, и мож
но считать, что они являются стандартом для оценки добротности ге
нератора, выраженной в расстоянии между плоскостями d
2
, …, d
9
при
заданном m.
Если поделить d исследуемого генератора на лучшее расстояние,
приведенное в табл. 3.9 для выбранного m, то полученное значение r
i
в пределе равно 1 и генератор тем лучше, чем ближе результат деле
ния к 1. Например, проверим на основе этого правила генератор
RANDU, пользуясь значениями d
L
,
полученными выше:
r
2
= 0.00002/0.00001 = 2, r
3
= 307, r
4
= 52, r
5
= 19,
r
6
= 12, r
7
= 7, r
8
= 5, r
9
= 4.
Из расчета видно, что наиболее плохое поведение генератора —
при размерностях 3 и 4. Из (3.31) найдем число плоскостей для
3размерного случая для этого генератора. В этом случае расстояние
d
3
= 0.092, следовательно, нижний предел равен 1/ 0.092 + 1 = 11.8,
а верхний —
3
/ 0.092 + 1 = 19.8. На самом деле, для этого генера
тора возможное число плоскостей (см. табл. 3.7) равно 2953, поэто
му с определенными оговорками этот генератор можно принять.
Пример. Проиллюстрируем сказанное на примере генератора с коэф
фициентами
x
i+1
= 7x
i
mod 11, x
0
= 1.
Из (3.29) оценим корреляцию R (U
i+1
, U
L
) = 1/7 + ε, а из (3.30) ε ≤ 13 /11 =
= 1.18
Таким образом, такой генератор может пройти тест благодаря большо
му значению ошибки. При n = 2 получим последовательность 1, 7, 5, 2, 3,
10, 4, 6, 9, 8, 1, которая имеет период m – 1 = 10. В результате получим
10 пар случайных чисел (1, 7), (7, 5), (5, 2), (2, 3), (3, 10), (10, 4), (4, 6),
(6, 9), (9, 8), (8, 1). Спектральный тест предусматривает получение 10 плос
костей с интервалом 1/11 = 0.909, каждая из которых содержит одну из
пар (рис. 3.11, линии А).
Но для конгруэнтного генератора при данных параметрах плоскостей
должно быть не больше (2! 11)
1/ 2
= 4 (рис. 3.11, линии Б) — это, естествен
но, предельный — худший — случай. Линии В (рис. 3.11) представляют
Таблица 3.9. Значения наилучшего расстояния
n
23456789
=m 2
61
8200.01410.01 920.01 440.0650.0560.0170.0670.0
=m 2
23
10000.03000.08100.0500.0800.0310.0710.0120.0
