В математике и информатике метод средних квадратов — это метод генерации псевдослучайных чисел.
Метод имеет непоправимые недостатки для многих практических применений, так как его период обычно очень короткий, а также: после некоторого количества итераций либо начнётся повторное генерирование одного и того же числа, либо последовательность зациклится на предыдущем числе.
Метод был изобретен Джоном фон Нейманом и изложен им на конференции в 1949 году.
В 1949 году фон Нейман заметил: «Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». Он уточнил, что имел в виду, что не было никаких истинных «случайных чисел», а «строгая арифметическая процедура», как и метод средних квадратов, «не является таким методом». Тем не менее, он обнаружил, что эти методы в сотни раз быстрее, чем чтение «истинных» случайных чисел с перфокарт, что имело практическое значение для его работы. Он обнаружил, что «уничтожение» последовательностей средних квадратов является фактором в их пользу, потому что его можно легко обнаружить: «всегда боишься появления необнаруженных коротких циклов». Николас Метрополис сообщил о последовательности 750 000 цифр перед «уничтожением» с помощью 38-битных чисел с методом среднего квадрата.
Книга Ивара Экеланда «The Broken Dice» дает расширенное описание того, как метод был изобретен францисканским монахом, известным только как брат Эдвин, где-то между 1240 и 1250 годами. Предположительно, рукопись теперь потеряна, но Хорхе Луис Борхес отправил Экеланду копию, которую он сделал в Ватиканской библиотеке.
Изменение алгоритма среднего квадрата с помощью последовательности Вейля улучшает период и случайность.
Для генерации последовательности 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}.")
This article uses material from the Wikipedia Русский article Метод середины квадрата, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Если не указано иное, содержание доступно по лицензии CC BY-SA 4.0. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Русский (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.