Метод середины квадрата
В математике и информатике метод средних квадратов — это метод генерации псевдослучайных чисел. Метод имеет непоправимые недостатки для многих практических применений, так как его период обычно очень короткий, а также: после некоторого количества итераций либо начнётся повторное генерирование одного и того же числа, либо последовательность зациклится на предыдущем числе.
История[править | править код]
Метод был изобретен Джоном фон Нейманом и изложен им на конференции в 1949 году.[1]
В 1949 году фон Нейман заметил: «Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». Он уточнил, что имел в виду, что не было никаких истинных «случайных чисел», а «строгая арифметическая процедура», как и метод средних квадратов, «не является таким методом». Тем не менее, он обнаружил, что эти методы в сотни раз быстрее, чем чтение «истинных» случайных чисел с перфокарт, что имело практическое значение для его работы. Он обнаружил, что «уничтожение» последовательностей средних квадратов является фактором в их пользу, потому что его можно легко обнаружить: «всегда боишься появления необнаруженных коротких циклов».[1] Николас Метрополис сообщил о последовательности 750 000 цифр перед «уничтожением» с помощью 38-битных чисел с методом среднего квадрата.[2]
Книга Ивара Экеланда «The Broken Dice» дает расширенное описание того, как метод был изобретен францисканским монахом, известным только как брат Эдвин, где-то между 1240 и 1250 годами.[3] Предположительно, рукопись теперь потеряна, но Хорхе Луис Борхес отправил Экеланду копию, которую он сделал в Ватиканской библиотеке.
Изменение алгоритма среднего квадрата с помощью последовательности Вейля улучшает период и случайность.[4][5]
Метод[править | править код]
Для генерации последовательности n-значных псевдослучайных чисел создаётся n-значное начальное значение, образующее 2n-значное число. Если результат имеет менее 2n цифр, для компенсации добавляются ведущие нули. Средние n цифр результата будут следующим числом в последовательности и будут возвращены в результате. Затем этот процесс повторяется для получения большего количества чисел.
Значение n должно быть четным, чтобы метод работал — если значение n нечётное, то не обязательно будет существовать единственно определенная «середина из n цифр» для выбора. Рассмотрим следующее: если трехзначное число возвести в квадрат, то может получиться шестизначное число (например, 5402 = 291600). Если бы существовала середина из 3 цифр, то осталось бы 6 − 3 = 3 цифры, которые нужно было бы распределить слева и справа от середины. Невозможно равномерно распределить эти цифры симметрично по обе стороны от середины числа, поэтому «серединных цифр» нет. Допустимо дополнять исходные значения нулями слева, чтобы получить число с чётным значением n (например, 540 → 0540).
Для генератора n-значных чисел период может быть не более 8n. Если середина числа состоит только из нулей, то генератор будет бесконечно выводить нули. Если первая половина числа в последовательности состоит из нулей, последующие числа будут убывать до нуля. И хотя эти серии из нулей легко обнаружить, они возникают слишком часто, чтобы этот метод был практически полезным. Метод среднего квадрата также может застрять на числе, отличном от нуля. Для n = 4 это происходит с значениями 0100, 2500, 3792 и 7600. Другие начальные значения образуют очень короткие повторяющиеся циклы, например, 0540 → 2916 → 5030 → 3009. Эти явления становятся еще более очевидными, когда n = 2, так как ни одно из 100 возможных исходных значений не генерирует более 14 итераций без возврата к 0, 10, 50, 60 или циклу 24 ↔ 57.
Пример реализации[править | править код]
Программа на языке Python 3:
seed_number = int(input("Введите число из 4 цифр:\n[####] "))
number = seed_number
already_seen = set()
counter = 0
while number not in already_seen:
counter += 1
already_seen.add(number)
number = int(str(number * number).zfill(8)[2:6])#zfill добавляет заполнение нулями
print(f"#{counter}: {number}")
print(f"Мы начали с числа {seed_number} и"
f" повторились через {counter} шагов"
f" с числом {number}.")
Примечания[править | править код]
- ↑ 1 2 (Статьи 1949 года не переиздавались до 1951 года.) John von Neumann, «Various techniques used in connection with random digits», in A. S. Householder, G. E. Forsythe, and H. H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol. 12 (Washington, D.C.: U.S. Government Printing Office, 1951): pp. 36-38.
- ↑ Donald E. Knuth, The art of computer programming, Vol. 2, Seminumerical algorithms, 2nd edn. (Reading, Mass.: Addison-Wesley, 1981), ch. 3, section 3.1.
- ↑ Ivar Ekeland. The Broken Dice, and Other Mathematical Tales of Chance. — University of Chicago Press, 15 June 1996. — ISBN 978-0-226-19992-4.
- ↑ Kneusel, Ron. Random Numbers and Computers. — 1. — Springer, 2018. — P. 13–14.
- ↑ Widynski, Bernard (April 2017). "Middle-Square Weyl Sequence RNG". arXiv:1704.00358 [cs.CR].