Составители:
Рубрика:
73
вать непрохождение на случайность по какомулибо из тестов. В на
стоящее время существует программа TESTRAND, проверяющая
10 млн случайных чисел по всем названным критериям, однако ее
применение прежде всего должно интересовать разработчиков гене
раторов и в меньшей степени — пользователей. Вместе с тем при
ИМ сложных, ответственных систем небесполезно проводить
тщательную проверку генерируемых БСВ!
3.5.3. Теоретическая оценка качества генераторов
В некоторых случаях до проверки последовательности БСВ на слу
чайность проводится теоретическая проверка конгруэнтных генера
торов, реализующих последовательность (3.22).
1. Последовательный корреляционный тест.
При случайности последовательности U
1
, U
2
, …, корреляция стро
го равна 0, т. е. R (U
i
, U
i +1
) = 0.
Подставив U
i
= x
i
/m в (3.22), можно показать, что
R (U
i
, U
i +1
) = 1/a (1 – 6c/m + 6 (c/m)
2
+ ε) (3.29)
при
| ε | ≤ (a + 6)/m. (3.30)
Если а и m простые числа, возможно (3.30) заменить на равен
ство. Дадевичем [14] показано, что не рекомендуется применять ге
нератор, у которого правая часть (3.29) больше 0.01, а правая часть
(3.30) меньше 0.005. Например, для генератора URN13 при с = 0,
а = 663 608 941 и m = 2
32
, проводя оценку по (3.29), (3.30), получаем
1/a = 0.0000000015, (a + 6)/m = 0.1545, следовательно, генератор
отвечает сформулированным правилам и проходит корреляционный
тест.
2. Спектральный тест (межплоскостных расстояний).
Этот тест основан на утверждении, что n выборок (U
1
, …, U
n
),
(U
2
, …, U
n+1
), (U
3
, …, U
n+2
),…, полученных от генератора по формуле
(3.22), лежат в конечном и малом числе параллельных, одинаково
расположенных гиперплоскостей [15]. То, что они лежат в конечном
числе плоскостей, очевидно, а то, что количество плоскостей мало,
является предметом обсуждения. Каждая плоскость должна содер
жать по меньшей мере три точки, тогда наименьшее число плоско
стей будет равно (n!m)
1/n
. В табл. 3.7 приведены значения этого про
изведения для разного числа выборок n при m = 2
32
.
Естественно, что существуют различные наборы плоскостей, со
держащие все эти точки. Рассмотрим такой набор, когда расстояние
