Элементарное построение линейной конгруэнтной последовательности Лехмера с той степенью случайности, с какой требованиям случайности отвечает спектральный тест Ковэю и Макферсона

Аннотация

Идеи случайного числа и случайной последовательности не поддаются
абсолютной формализации. Взамен чего по тем или иным соображениям предлагаются
массивы Генераторов случайных чисел, по ним создаются методы проверки (тестирования)
их на случайность. Последовательности, прошедшие такой экзамен объявляются случайными,
а каждый её элемент случайным числом, – в результате различных видов случайности столько,
сколько проверочных тестов.
Статья посвящена полному решению задачи в постановках, объектах и продолжительной
респектабельной историей исследования с поучительными выводами, в совокупности
находящихся, надеемся, в высших эшелонах Компьютерных наук: Генератор Лехмера (1949
год) – один из самых популярных, если не самый популярный датчик и спектральный
тест Ковею и Макферсона 1965 года создания как «наиболее совершенный из имеющихся
тестов», оба в связке с 50-летней историей, в развитии подробно изложенной во всех
изданиях монографии «Искусство программирования» Дональда Эрвина Кнута с 1969 года
по настоящее время, стало быть, бывшей в постоянной разработке. Именно, мало что
проясняющая односторонняя оценка сверху главной числовой характеристики случайности
νs с пессимистическим прогнозом «было бы очень трудно вычислить точность νs , когда
s ≥ 10 » заменена на неожидаемую асимптотическую при всех s ≥ 2 – в чем в идеале состояла
задача и в этом состоит её решение.
Генератор случайных чисел Лехмера или же Линейная конгруэнтная последовательность
максимального периода есть, по определению, рекуррентная последовательность hXni целых
неотрицательных чисел
Xn+1 = (aXn + c) mod N, n ≥ 0, (0.1)
где
N − модуль 0 < N, a − множитель 0 ≤ a < N,
c − приращение 0 ≤ A < N, X0 − начальное значение 0 ≤ X0 < N,
целые числа a > 1, N > a, τ (a, N) ≥ 2 и 1 ≤ λ (a, N) ≡
(a−1)τ(a,N)
N < (a − 1)τ(a,N)−1
) связаны
сравнениями (a − 1)τ(a,N) ≡ 0 (modN) и (a − 1)τ(a,N)−1
6≡ 0 (modN).
Как это часто встречается, в этом случае тоже, вся проблема сводится к четко
формулируемой математической задаче (все мотивировки и детали приведены в самом тексте
статьи): при заданных s ≥ 2 и τ ≥ 2 и растущем N найти асимтотику величины (все
параметры – целые положительные числа)
sup
νs (a, N) : 2 ≤ a < N,(a − 1)τ ≡ 0(modN),(a − 1)τ−1
6≡ 0(modN)

, (0.2)

где
νs (a, N) = inf



q
m2
1 + · · · + m2
s
: m = (m1, ..., ms) ∈ Z
s
, m 6= 0,
Xs
j=1
mja
j−1 ≡ 0 (modN)



.
Тем самым, задача заключается в указании числа a = a(N) с как можно большим значением
величины νs(a, N), тогда как при всех a, N и s известны только неравенства νs(a, N) ≤
γ(s)N
1
s . Как и всякая оценка сверху, это неравенство может быть сильно завышенным,
поэтому задачи не решает.
В данной работе в зависимости от всех возможных, и поэтому обеспечивающих полное
решение исследуемой задачи, соотношений между параметрами s, τ и λ получены новые и
окончательные результаты по спектральному тестированию (ST), носящие асимптотический
характер:
ST : ν2

a, N; (a − 1)2 = N

= (a − 1) s
1 − 2
a − 2
(a − 1)2 =
√
N
s
1 − 2
√
N − 1
N
,
ST (2 ≤ s = τ ) : N
1
s

1 − (bs − 1) N
− 1
s

= a − bs ≤ νs (a, N; (a − 1)s = N) ≤
≤
p
a
2 + 1 = N
1
s
q
1 + 2N − 1
s + 2N − 2
s ,
ST (2 ≤ s < τ, λ ≥ 1) : (Nλ)
1
τ

1 − (bs − 1) (Nλ)
− 1
τ

= (a − bτ ) ≤
≤ νs

a, N; (a − 1)τ = Nλ, 1 ≤ λ ≤ (a − 1)τ−s

≤
p
a
2 + 1 = (Nλ)
1
τ
q
1 + 2 (Nλ)
− 1
τ + 2 (Nλ)
− 2
τ ,
ST (s > τ ≥ 2, λ ≥ 1) : νs (a, N; (a − 1)τ = Nλ, λ ≥ 1) ≤
vuutXτ
k=0
τ
k
2
,
где (−bm) есть наибольший по модулю отрицательный биномиальный коэффициент в
разложении (a − 1)m по степеням a : b2 = 2, b3 = 3, b4 = 4, b5 = 10, b6 = 20, b7 = 35, b8 = 56 ,
b9 = 126, b10 = 252, b11 = 462, b12 = 792, b13 = 1716, b14 = 3432, b15 = 6435, ... и т. д.
Все построения по этой теме в монографии Д. Кнута «Искусство программирования»
носят полуэмпирический характер – выдвигаются теоретические положения на основе которых
проводятся статистические эксперименты. К тому же, Д. Кнут на примере казалось бы
несомненно случайного подбора параметров в методе «середин квадратов» фон Неймана
приходит к выводу, что чисто экспериментальные поиски ненадежны и всегда нужна какая-то
теория.
Нами проведено чисто теоретическое исследование.
Как это следует из оценок снизу во всех ST-утверждениях, все они с точностью стремящегося
к 1 при возрастании N явно выписываемого (что имеет решающее значение в практических
применениях) множителя γN имеют вид γN · N
1
s ≤ νs(a, N).
Это означает, что одновременно решены две задачи (с единственным ограничением –
вычислительными возможностями компьютерной техники)
а. Количество случайных чисел N должно и может быть произвольно большим,
b. Основная характеристика случайности νs(a, N) должна и может быть столь угодно
большой при всех s ≥ 2 .
При этом, главная часть N
1
s величины s -мерной точности генератора hXni из-за малого
показателя 1/s , известного как «проклятие размерности», требует от N в обратной к ней
степени s быть большим (этим повторяется величина скорости приближения квадратурной
формулы с равномерной сеткой и равными весами в численном интегрировании).
Возникает новая задача «В каждом конкретном случае применения Генератора случайных
чисел (0.1)–(0.2) выяснить, какими большими должны быть N и νs(a, N) ?». Разумеется,
это отдельная задача, быть может, даже нетривиальная

Асимптотически точные оценки сверху νs (a, N) ≤ γN · N
1
s

γN → 1

выступают в роли
гаранта не взять N и νs(a, N) неоправданно большими с сопровождающими большими
затратами при реализации.
За исключением случая s = 2 все ST-утверждения не точные, а асимптотические, что
никак не ограничивает применений – требуются не точные значения N и νs(a, N), а только
приблизительные в нужных по контексту случая границах.
Если от неосязаемой напрямую оценки νs(a, N) перейти к непосредственной
проверке случайности через «частотность» (это свойство также называют равномерной
распределенностью, от случайности требуется много больше), в которой числа 0, 1, . . . N − 1
надо переставить в другом порядке X0, . . . , XN−1 как биективное отображение на себя таким
образом, чтобы для любого сегмента [α, β] из [0, 1] количество чисел Xn
N
попавших в [α, β]
должно быть близко (β − α), то обнаруживается, что всякая последовательность Лехмера
с максимальным периодом изначально равномерно распределена с неулучшаемой оценкой
отклонения 1
N
, что следует отнести к ее замечательным свойствам. Тем самым, проблематика
заключается только в показателе случайности νs(a, N)