В математике и информатике метод средних квадратов — это метод генерации псевдослучайных чисел. Метод имеет непоправимые недостатки для многих практических применений, так как его период обычно очень короткий, а также: после некоторого количества итераций либо начнётся повторное генерирование одного и того же числа, либо последовательность зациклится на предыдущем числе.
В 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).