Метод среднего квадрата
В математике и информатике метод средних квадратов — это метод генерации псевдослучайных чисел . На практике это очень ошибочный метод для многих практических целей, поскольку его период обычно очень короткий и у него есть некоторые серьезные недостатки; повторяется достаточное количество раз, метод среднего квадрата либо начнет повторно генерировать одно и то же число, либо будет переходить к предыдущему числу в последовательности и выполнять цикл бесконечно.
История [ править ]
По математике [ править ]
Метод был изобретен Джоном фон Нейманом и описан им на конференции в 1949 году. [1]
В выступлении 1949 года фон Нейман пошутил: «Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». Он имел в виду, пояснил он, что не существует настоящих «случайных чисел», а есть только средства их получения, и «строгая арифметическая процедура», такая как метод средних квадратов, «не является таким методом». Тем не менее, он обнаружил, что эти методы в сотни раз быстрее, чем считывание «по-настоящему» случайных чисел с перфокарт , что имело практическое значение для его по ENIAC работы . Он обнаружил, что «разрушение» последовательностей средних квадратов является фактором в их пользу, поскольку его можно легко обнаружить: «всегда опасаешься появления необнаруженных коротких циклов». [1] Николас Метрополис сообщил о последовательностях из 750 000 цифр перед «уничтожением» посредством использования 38-битных чисел с помощью метода «среднего квадрата». [2]
В книге «Сломанные кости» Ивара Экланда подробно рассказывается о том, как этот метод был изобретен монахом-францисканцем, известным только как брат Эдвин, где-то между 1240 и 1250 годами. [3] Предположительно, рукопись сейчас утеряна, но Хорхе Луис Борхес отправил Экеланду копию, которую он сделал в Библиотеке Ватикана.
Модификация алгоритма среднего квадрата с помощью последовательности Вейля улучшает период и случайность. [4] [5]
Метод [ править ]
Чтобы сгенерировать последовательность n -значных псевдослучайных чисел, n создается -значное начальное значение и возводится в квадрат, в результате чего получается 2 n -значное число. Если результат содержит менее 2 n цифр, ведущие нули для компенсации добавляются . Средние n цифр результата будут следующим числом в последовательности и будут возвращены в качестве результата. Затем этот процесс повторяется для генерации большего количества чисел.
Значение n должно быть четным, чтобы метод работал - если значение n нечетное, то не обязательно будут однозначно определенные «средние n -цифры», из которых можно выбирать. Рассмотрим следующее: если возвести в квадрат трехзначное число, получится шестизначное число (например, 540 2 = 291600). Если бы были средние 3 цифры, то слева и справа от середины осталось бы 6 − 3 = 3 цифры. Невозможно равномерно распределить эти цифры поровну по обе стороны от среднего числа, и поэтому «средних цифр» не существует. Допустимо дополнять начальные числа нулями слева, чтобы получить четное n -значное число (например, 540 → 0540).
Для генератора n -значных чисел период не может быть длиннее 8. н . Если все средние n цифр — нули, генератор всегда выводит нули. Если первая половина числа в последовательности равна нулям, последующие числа будут уменьшаться до нуля. Хотя эти серии нулей легко обнаружить, они происходят слишком часто, чтобы этот метод мог иметь практическое применение. Метод среднего квадрата также может застрять на числе, отличном от нуля. При n = 4 это происходит со значениями 0100, 2500, 3792 и 7600. Другие начальные значения образуют очень короткие повторяющиеся циклы, например, 0540 → 2916 → 5030 → 3009. Эти явления еще более очевидны при n = 2, поскольку ни одно из 100 возможных начальных чисел не генерирует более 14 итераций без возврата к 10, 20, 60, 80 или циклу 42 ↔ 75.
Пример реализации [ править ]
Здесь алгоритм отображается на Python 3.12 .
seed_number = int(input("Please enter a four-digit number:\n[####] "))
number = seed_number
already_seen = set()
counter = 1
while number not in already_seen:
counter += 1
already_seen.add(number)
number = int(str(number * number).zfill(8)[2:6]) # zfill adds padding of zeroes
print(f"#{counter}: {number}")
print(f"We began with {seed_number} and"
f" have repeated ourselves after {counter} steps"
f" with {number}.")
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Статьи 1949 года не переиздавались до 1951 года. Джон фон Нейман, «Различные методы, используемые в связи со случайными цифрами», в книге А. С. Хаусхолдера, Дж. Э. Форсайта и Х. Х. Джермонда, ред., Метод Монте-Карло, Серия Национального бюро стандартов по прикладной математике , том. 12 (Вашингтон, округ Колумбия: Типография правительства США, 1951): стр. 36–38.
- ^ Дональд Э. Кнут, Искусство компьютерного программирования, Том. 2, Получисловые алгоритмы , 2-е изд. (Ридинг, Массачусетс: Аддисон-Уэсли, 1981), гл. 3, раздел 3.1.
- ^ Ивар Экеланд (15 июня 1996 г.). Сломанные кости и другие математические случайные истории . Издательство Чикагского университета. ISBN 978-0-226-19992-4 .
- ^ Кнейзель, Рон (2018). Случайные числа и компьютеры (1-е изд.). Спрингер. стр. 13–14.
- ^ Видынски, Бернар (апрель 2017 г.). «ГСЧ последовательности Вейля среднего квадрата». arXiv : 1704.00358 [ cs.CR ].