Метод средней квадратичной последовательности: история и недостатки
Middle-square method
Метод средних квадратов: генерация псевдослучайных чисел, предложенная фон Нейманом. Обладает коротким периодом и слабостями, не подходит для серьёзных задач.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В математике и информатике метод среднего квадрата — это метод генерации псевдослучайных чисел. На практике это крайне несовершенный метод для многих практических задач, поскольку его период обычно очень короткий и он имеет серьезные недостатки; при достаточном количестве повторений метод среднего квадрата либо начнет повторять одно и то же число, либо вернется к предыдущему числу в последовательности и зациклится бесконечно.
In mathematics and computer science, the middle square method is a method of generating pseudorandom numbers. In practice it is a highly flawed method for many practical purposes, since its period is usually very short and it has some severe weaknesses; repeated enough times, the middle square method will either begin repeatedly generating the same number or cycle to a previous number in the sequence and loop indefinitely.
В математике
Метод был изобретен Джоном фон Нейманом и описан им на конференции в 1949 году. В своей речи в 1949 году фон Нейман остроумно заметил, что "любой, кто рассматривает арифметические методы для генерации случайных цифр, конечно, совершает грех". Он пояснил, что истинных "случайных чисел" не существует, есть лишь способы их получения, и "строгая арифметическая процедура", такая как метод середины квадрата, "не является таковым". Тем не менее, он обнаружил, что эти методы в сотни раз быстрее, чем считывание "действительно" случайных чисел с перфокарт, что имело практическую ценность для его работы с ENIAC. Он считал, что "деградация" последовательностей середины квадрата является их преимуществом, поскольку её можно легко обнаружить: "всегда есть опасение появления незамеченных коротких циклов". В книге Ивара Экеланда "Сломанный кубик" подробно рассказывается о том, как этот метод был изобретен францисканским монахом, известным лишь как брат Эдвин, между 1240 и 1250 годами. Предположительно, рукопись утеряна, но Хорхе Луис Борхес прислал Экеланду копию, сделанную им в Ватиканской библиотеке. Модификация алгоритма середины квадрата с использованием последовательности Вейля улучшает период и случайность.
The method was invented by John von Neumann, and was described by him at a conference in 1949. In the 1949 talk, Von Neumann quipped that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." What he meant, he elaborated, was that there were no true "random numbers", just means to produce them, and "a strict arithmetic procedure", like the middle square method, "is not such a method". Nevertheless, he found these methods hundreds of times faster than reading "truly" random numbers off punch cards, which had practical importance for his ENIAC work. He found the "destruction" of middle square sequences to be a factor in their favor, because it could be easily detected: "one always fears the appearance of undetected short cycles". The book The Broken Dice by Ivar Ekeland gives an extended account of how the method was invented by a Franciscan friar known only as Brother Edvin sometime between 1240 and 1250. Supposedly, the manuscript is now lost, but Jorge Luis Borges sent Ekeland a copy that he made at the Vatican Library. Modifying the middle square algorithm with a Weyl sequence improves period and randomness.
Метод
Для создания последовательности псевдослучайных чисел с n цифр создается начальное значение с n цифр и возводится в квадрат, в результате чего получается число с 2n цифр. Если в результате получается меньше 2n цифр, то для компенсации добавляются ведущие нули. Средние n цифр результата становятся следующим числом в последовательности и возвращаются как результат. Этот процесс повторяется для генерации дополнительных чисел. Значение n должно быть четным для корректной работы метода; если n нечетное, то однозначно определить "средние n цифр" для выбора не всегда возможно. Например, при возведении в квадрат трехзначного числа может получиться шестизначное число (например, 540<sup>2</sup> = 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 итераций без возврата к значениям 10, 20, 60, 80 или циклу 42 ↔ 75.
To generate a sequence of n digit pseudorandom numbers, an n digit starting value is created and squared, producing a 2n digit number. If the result has fewer than 2n digits, leading zeroes are added to compensate. The middle n digits of the result would be the next number in the sequence and returned as the result. This process is then repeated to generate more numbers. The value of n must be even in order for the method to work if the value of n is odd, then there will not necessarily be a uniquely defined "middle n digits" to select from. Consider the following: If a 3 digit number is squared, it can yield a 6 digit number (e. g. 5402 = 291600). If there were to be middle 3 digits, that would leave 6 − 3 = 3 digits to be distributed to the left and right of the middle. It is impossible to evenly distribute these digits equally on both sides of the middle number, and therefore there are no "middle digits". It is acceptable to pad the seeds with zeros to the left in order to create an even valued n digit number (e. g. 540 → 0540). For a generator of n digit numbers, the period can be no longer than 8n. If the middle n digits are all zeroes, the generator then outputs zeroes forever. If the first half of a number in the sequence is zeroes, the subsequent numbers will be decreasing to zero. While these runs of zero are easy to detect, they occur too frequently for this method to be of practical use. The middle squared method can also get stuck on a number other than zero. For n = 4, this occurs with the values 0100, 2500, 3792, and 7600. Other seed values form very short repeating cycles, e. g., 0540 → 2916 → 5030 → 3009. These phenomena are even more obvious when n = 2, as none of the 100 possible seeds generates more than 14 iterations without in reverting to 10, 20, 60, 80, or a 42 ↔ 75 loop.