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

Метод середины квадрата, в математике и информатике — метод генерации псевдослучайных чисел.

На практике это очень несовершенный метод для многих практических целей, поскольку его период обычно очень короток и он имеет некоторые серьезные недостатки; повторяется достаточное количество раз, метод среднего квадрата либо начнет повторно генерировать одно и то же число, либо будет циклически переходить к предыдущему числу в последовательности и циклически повторяться до бесконечности.

История

Был изобретен Джоном фон Нейманом и описан им на конференции в 1949 году.

В выступлении 1949 года фон Нейман пошутил, что «любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». Он уточнил, что он имел в виду, что не существует настоящих «случайных чисел», есть только средства их получения, и «строгая арифметическая процедура», такая как метод среднего квадрата, «не является таким методом». Тем не менее, он обнаружил, что эти методы в сотни раз быстрее, чем чтение «настоящих» случайных чисел с перфокарт, что имело практическое значение для его работы с ENIAC. Он обнаружил, что «разрушение» последовательностей средних квадратов является фактором в их пользу, потому что его можно легко обнаружить: «всегда опасаются появления необнаруженных коротких циклов». Николас Метрополис сообщил о последовательностях из 750 000 цифр до «уничтожения» посредством использования 38-битных чисел с помощью метода «средних квадратов».

В книге Ивара Экланда «Сломанные кости» дается подробный отчет о том, как этот метод был изобретен монахом-францисканцем, известным только как брат Эдвин, где-то между 1240 и 1250 годами. Предположительно, рукопись сейчас утеряна, но Хорхе Луис Борхес прислал Экеланду копию, которую он сделал в Ватиканской библиотеке.

Модификация алгоритма среднего квадрата с помощью последовательности Вейля улучшает период и случайность.

Метод

Чтобы сгенерировать последовательность n-значных псевдослучайных чисел, создается n-значное начальное значение и возводится в квадрат, в результате чего получается 2n-значное число. Если результат содержит менее 2n цифр, для компенсации добавляются ведущие нули. Средние n цифр результата будут следующим числом в последовательности и будут возвращены как результат. Затем этот процесс повторяется, чтобы сгенерировать больше чисел.

Чтобы метод работал, значение n должно быть четным — если значение n нечетное, то не обязательно будет однозначно определенное «среднее n-значное число» для выбора. Рассмотрим следующее: если возвести в квадрат трехзначное число, то получится шестизначное число (например, 5402 = 291600). Если бы были средние 3 цифры, осталось бы 6 − 3 = 3 цифры, которые нужно распределить слева и справа от середины. Равномерно распределить эти цифры одинаково по обеим сторонам от среднего числа невозможно, и поэтому «средних цифр» нет. Допустимо дополнять начальные числа нулями слева, чтобы создать четное число из n цифр (например, 540 → 0540).

Для генератора n-значных чисел период не может быть длиннее 8n. Если средние n цифр все нули, генератор выводит нули навсегда. Если первая половина числа в последовательности нулевая, то последующие числа будут уменьшаться до нуля. Хотя эти прогоны нуля легко обнаружить, они происходят слишком часто, чтобы этот метод имел практическое применение. Метод среднего квадрата также может застрять на числе, отличном от нуля. При n = 4 это происходит со значениями 0100, 2500, 3792 и 7600. Другие начальные значения образуют очень короткие повторяющиеся циклы, например, 0540 → 2916 → 5030 → 3009. Эти явления еще более очевидны, когда n = 2, как ни одно из 100 возможных начальных значений не генерирует более 14 итераций без возврата к 0, 10, 50, 60 или циклу 24 ↔ 57.