Метод серединных квадратов

Метод серединных квадратов — это один из первых алгоритмов генерации псевдослучайных чисел, предложенный Джоном фон Нейманом в 1946 году. Метод основан на итеративном возведении в квадрат исходного числа и извлечении из результата средней части цифр заданной длины. Относится к классу детерминированных генераторов псевдослучайных чисел, то есть его выходная последовательность полностью определяется начальным значением (зерном).

История

Метод серединных квадратов был разработан в середине 1940-х годов в рамках работ по созданию первых электронных вычислительных машин. Джон фон Нейман, работавший над проектом ENIAC в Лос-Аламосской национальной лаборатории, столкнулся с необходимостью получения случайных чисел для моделирования процессов ядерного деления. Поскольку аппаратные генераторы случайных чисел были ненадёжны, а таблицы случайных чисел — неудобны, фон Нейман предложил вычислительный подход.

В 1949 году метод был описан в докладе «Various Techniques Used in Connection with Random Digits» на симпозиуме по методу Монте-Карло. Несмотря на то, что метод серединных квадратов быстро выявил серьёзные недостатки (короткий период, вырождение последовательности в ноль), он сыграл важную роль в развитии вычислительной математики и стимулировал создание более совершенных генераторов, таких как линейный конгруэнтный метод (1951 год).

Алгоритм

Основная процедура

Пусть требуется генерировать последовательность псевдослучайных чисел, каждое из которых содержит n цифр в десятичной системе счисления. Алгоритм состоит из следующих шагов:

Выбирается начальное число (зерно) X₀, содержащее n цифр. Если число имеет меньше цифр, оно дополняется ведущими нулями до длины n.
Текущее число Xᵢ возводится в квадрат. В результате получается число, содержащее до 2n цифр.
Если в квадрате меньше 2n цифр, оно дополняется ведущими нулями слева до длины 2n.
Из полученного числа извлекаются n средних цифр. Если n чётно, берутся n цифр, начиная с позиции (n/2)+1 слева. Если n нечётно, возможны вариации (например, отбрасывание одной цифры слева и одной справа, или округление).
Извлечённое число становится следующим членом последовательности Xᵢ₊₁.
Для получения псевдослучайного числа в диапазоне [0, 1) результат делится на 10ⁿ.

Пример

Для n=4 и начального числа X₀=1234:

Шаг 1: X₀ = 1234
Шаг 2: 1234² = 1522756 (7 цифр)
Шаг 3: Дополнение до 8 цифр: 01522756
Шаг 4: Извлечение средних 4 цифр: 5227
Шаг 5: X₁ = 5227
Шаг 6: Псевдослучайное число: 0.5227

Повторение для X₁=5227:

5227² = 27321529 (8 цифр)
Средние 4 цифры: 3215
X₂ = 3215

Свойства и недостатки

Период и вырождение

Основным недостатком метода серединных квадратов является короткий период последовательности и склонность к вырождению. При определённых начальных значениях последовательность быстро зацикливается, часто попадая в цикл малой длины или в ноль. Например, для n=4 и зерна 0000 последовательность сразу вырождается в ноль. Для зерна 3792 последовательность зацикливается на числе 6100.

Чувствительность к начальному значению

Метод крайне чувствителен к выбору начального числа. Некоторые зерна приводят к последовательностям с приемлемыми статистическими свойствами, другие — к быстрому вырождению. Исследования показали, что для n=4 только около 20% всех возможных начальных значений дают последовательности, не вырождающиеся в ноль в течение первых 100 шагов.

Неравномерность распределения

Генерируемые числа не являются равномерно распределёнными. В последовательности часто наблюдаются корреляции между соседними значениями, что делает метод непригодным для большинства статистических приложений.

Применение

Несмотря на недостатки, метод серединных квадратов нашёл ограниченное применение:

Историческое: Использовался в ранних компьютерных программах для метода Монте-Карло, в частности, в моделировании нейтронного транспорта в Лос-Аламосе.
Образовательное: Часто приводится в учебниках по численным методам и программированию как пример простого генератора псевдослучайных чисел, иллюстрирующего проблемы, связанные с детерминированными последовательностями.
Криптография: Не применяется из-за предсказуемости и малого периода.

Вариации

Метод серединных произведений

Модификация, предложенная Дерриком Лемером в 1951 году, где вместо возведения в квадрат используется умножение двух последовательных чисел. Это несколько улучшает статистические свойства, но не устраняет фундаментальных недостатков.