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

Abstract

Идеи случайного числа и случайной последовательности не поддаются абсолютной формализации. Взамен чего по тем или иным соображениям предлагаются массивы Генераторов случайных чисел, по ним создаются методы проверки (тестирования) их на случайность. Последовательности, прошедшие такой экзамен объявляются случайными, а каждый её элемент случайным числом, – в результате различных видов случайности столько, сколько проверочных тестов. Статья посвящена полному решению задачи в постановках, объектах и продолжительной респектабельной историей исследования с поучительными выводами, в совокупности находящихся, надеемся, в высших эшелонах Компьютерных наук: Генератор Лехмера (1949 год) – один из самых популярных, если не самый популярный датчик и спектральный тест Ковею и Макферсона 1965 года создания как «наиболее совершенный из имеющихся тестов», оба в связке с 50-летней историей, в развитии подробно изложенной во всех изданиях монографии «Искусство программирования» Дональда Эрвина Кнута с 1969 года по настоящее время, стало быть, бывшей в постоянной разработке. Именно, мало что проясняющая односторонняя оценка сверху главной числовой характеристики случайности νs с пессимистическим прогнозом «было бы очень трудно вычислить точность νs , когда s ≥ 10 » заменена на неожидаемую асимптотическую при всех s ≥ 2 – в чем в идеале состояла задача и в этом состоит её решение.