Алгоритм фон Неймана

Алгоритм фон Неймана — это метод генерации псевдослучайных чисел, основанный на возведении исходного числа в квадрат и извлечении средней части полученного результата. Предложен американским математиком Джоном фон Нейманом в 1946 году и является одним из первых алгоритмов для получения случайных последовательностей на электронных вычислительных машинах. Относится к классу детерминированных алгоритмов, что означает, что при одинаковом начальном значении (зерне) последовательность чисел полностью повторяется.

История

В середине 1940-х годов, в период создания первых программируемых компьютеров (например, ENIAC), возникла необходимость в генерации случайных чисел для моделирования физических процессов, криптографии и численных методов (метод Монте-Карло). Джон фон Нейман, участвовавший в разработке компьютеров и теории игр, предложил простой алгоритм, который мог быть реализован вручную или на ранних вычислительных машинах без использования специализированных аппаратных генераторов.

Первое описание алгоритма было дано фон Нейманом в 1946 году в неопубликованных заметках, а затем популяризировано в 1949 году в работе «Various Techniques Used in Connection with Random Digits» (сборник статей по методу Монте-Карло). Несмотря на простоту, алгоритм быстро проявил недостатки, и к концу 1950-х годов его вытеснили более совершенные методы (например, линейный конгруэнтный метод). Тем не менее, он остаётся классическим примером в учебной литературе по программированию и теории случайных чисел.

Принцип работы

Алгоритм фон Неймана (также известный как «метод серединных квадратов») работает следующим образом:

1. Выбирается начальное число — зерно (seed), которое является n-значным числом (обычно чётное количество цифр).
2. Зерно возводится в квадрат, в результате чего получается число, содержащее до 2n цифр (при необходимости результат дополняется слева нулями до 2n цифр).
3. Из полученного квадрата извлекаются средние n цифр — это и есть следующее псевдослучайное число.
4. Процесс повторяется, используя полученное число как новое зерно.

Пример

Возьмём 4-значное зерно: 1234.

• Квадрат: 1234² = 1 522 756.
• Дополняем до 8 цифр: 01522756.
• Извлекаем средние 4 цифры: 5227.
• Следующее число: 5227.
• Квадрат: 5227² = 27 321 529 → 27321529 → средние 4 цифры: 3215.
• И так далее.

Последовательность: 1234 → 5227 → 3215 → 3322 → 0356 → 1267 → 6052 → 6267 → 2792 → 7952 → 2343 → 4896 → 9708 → 2452 → 0123 → 0151 → 0228 → 0519 → 2696 → 2684 → 2018 → 0723 → 0527 → 0277 → 0767 → 0588 → 3457 → 9508 → 4016 → 1282 → 6435 → 4092 → 7444 → 4131 → 0651 → 4238 → 9606 → 2752 → 5735 → 8902 → 2456 → 0319 → 1017 → 0342 → 1169 → 3665 → 4322 → 6796 → 1856 → 4447 → 7758 → 1865 → 4782 → 8675 → 2556 → 5331 → 4195 → 5980 → 7604 → 8208 → 3712 → 7789 → 6685 → 6892 → 4996 → 9600 → 1600 → 5600 → 3600 → 9600 → 1600 → … (цикл повторяется).

Характеристики и недостатки

Достоинства

• Простота реализации — алгоритм требует только операций умножения и извлечения цифр, что легко выполняется вручную или на простых вычислителях.
• Наглядность — позволяет понять базовые принципы генерации псевдослучайных чисел.

Недостатки

• Короткий период — последовательность быстро зацикливается (как в примере выше, цикл из 4 чисел). Для 4-значных чисел период редко превышает несколько тысяч шагов.
• Вырождение в ноль — если на каком-то шаге получено число, состоящее из одних нулей (например, 0000), то все последующие числа будут нулями.
• Неравномерность распределения — некоторые числа могут выпадать чаще других, а некоторые — никогда.
• Зависимость от начального зерна — неудачный выбор зерна (например, 0000) приводит к немедленному вырождению.
• Низкое качество случайности — алгоритм не проходит статистические тесты на случайность (например, тест на равномерность или независимость).

Применение

В настоящее время алгоритм фон Неймана не используется в серьёзных приложениях из-за низкого качества генерируемых последовательностей. Однако он применяется:

• В учебных целях — для демонстрации принципов работы генераторов псевдослучайных чисел и их недостатков.
• В исторических исследованиях — для реконструкции ранних вычислительных экспериментов.
• В простых любительских проектах — где не требуется высокая статистическая случайность (например, в игровых прототипах).

Современные генераторы псевдослучайных чисел (например, Mersenne Twister, линейный конгруэнтный метод, криптостойкие генераторы) обеспечивают значительно больший период и лучшее качество случайности.

Критика

Сам Джон фон Нейман впоследствии критически относился к своему алгоритму. В 1951 году он писал: «Любой, кто считает, что арифметические методы получения случайных чисел пригодны для серьёзных целей, находится в состоянии греха». Эта фраза стала крылатой в сообществе специалистов по численным методам. Алгоритм часто приводится как пример того, как простая идея может быть неэффективной на практике.

Интересные факты

• Алгоритм фон Неймана был одним из первых методов, реализованных на компьютере ENIAC для генерации случайных чисел при моделировании ядерных реакций (Манхэттенский проект).
• В 1949 году математик Деррик Лемер предложил улучшенный вариант — метод серединных произведений, где вместо возведения в квадрат перемножались два последовательных числа.
• Для 2-значных чисел алгоритм быстро вырождается: например, зерно 12 → 12²=144 → 14 → 14²=196 → 19 → 19²=361 → 36 → 36²=1296 → 29 → 29²=841 → 84 → 84²=7056 → 05 → 05²=25 → 02 → 02²=4 → 00 → 00 → … (вырождение в ноль).

Источники

• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley. — Глава 3.1 «Random Numbers».
• von Neumann, J. (1949). Various Techniques Used in Connection with Random Digits. In A. S. Householder, G. E. Forsythe, & H. H. Germond (Eds.), Monte Carlo Method (National Bureau of Standards Applied Mathematics Series, Vol. 12, pp. 36–38).
• Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. — Глава 7.1 «Random Numbers».