§3. Математические датчики: станок, который сам плодит цифру

Железо отпало, тетрадь со случайными цифрами жрёт память и таскать её западло. Нормальному пацану нужен станок прямо в процессоре: коротенький алгоритм, который сам, из головы, штампует псевдослучайные числа — быстро, пачками, и чтоб при нужде можно было отмотать тот же расклад назад (задал стартовое число — получил ту же серию). Вот такие станки и называют математическими датчиками.

Устроены они обычно как рекуррентные алгоритмы: следующее число лепится из предыдущего. Задал старт — и понеслась цепочка $y_1, y_2, y_3, \dots$, где каждое вытекает из соседа слева. Коротко, детерминированно, воспроизводимо. Разберём от простого к рабочему.

Метод середины квадрата: красиво, но гнилой

Первый заход — метод середины квадрата (Джон фон Нейман, 1946). Схема детская:

1. Берём четырёхзначное число $k_0$.
2. Возводим в квадрат (получаем до восьми цифр).
3. Выдираем средние четыре цифры — это $k_1$.
4. Нормируем: $y_1 = k_1 \cdot 10^{-4}$ (то есть $k_1/10000$ — загоняем в $[0,1)$).
5. С $k_1$ повторяем всё заново, и так далее.

Пример от Лагутина. Старт $k_0 = 8473$. Квадрат: $k_0^2 = 71\,791\,729$. Средние четыре цифры — $7917$, значит $k_1 = 7917$ и $y_1 = 0{,}7917$. Дальше $k_1^2 = 62\,678\,889$, середина — $6788$, выходит $y_2 = 0{,}6788$. И покатилось.

Погоняй сам — жми Run:

Красиво? Красиво. Только датчик гнилой, и вот где он палится:

1. Старт решает всё. $k_0$ полностью задаёт всю цепочку — никакой свободы, вся «случайность» зашита в одно число.
2. Зацикливается быстро — не позже чем через $10^4$ шагов (четырёхзначных чисел всего-то десять тысяч). Хуже: есть числа, которые воспроизводят сами себя и намертво застревают. Например $3792^2 = 14\,379\,264$, середина — снова $3792$. Приехали, датчик встал на месте.
3. Можно убить на ровном месте. Задашь неудачный старт (скажем, $1000$ или $0085$) — и датчик через пару шагов схлопывается в ноль и дальше плюёт одни нули. Полное фуфло.

Глянь на этот кидок своими глазами:

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

Линейный конгруэнтный датчик: рабочая лошадь

Вот это уже по-взрослому. Общая схема мультипликативного (и чуть шире — линейного конгруэнтного) датчика. Задаём стартовое $k_0$, множитель $a$, приращение $c$ и делитель $m$, и крутим по формуле:

Разбираем по кирпичикам, тут один новый значок:

• $\bmod m$ — это остаток от деления на $m$. Поделил нацело, что осталось в хвосте — то и берём. Фишка в том, что остаток всегда сидит в диапазоне $0, 1, \dots, m-1$ — то есть сколько ни умножай, результат всегда загнан в рамки. Как счётчик по кругу: добежал до $m$ — и обнулился.
• $a \cdot k_{n-1} + c$ — берём прошлое число, раскручиваем умножением на $a$, добавляем $c$.
• $k_n$ — остаток этой движухи по модулю $m$.
• $y_n = k_n / m$ — делим на $m$, чтобы загнать в $[0,1)$.

При $c = 0$ датчик называют мультипликативным — приращения нет, только умножение по кругу.

Теперь главное — какие $a$ и $m$ брать, чтобы датчик держал марку. Делитель выгодно брать простым: например $m = 2^{31} - 1 = 2\,147\,483\,647$ (ровно влезает в 32-битное целое). А множитель $a$ подбирают так, чтобы цепочка $k_1, k_2, \dots$ пробежала все возможные значения от $1$ до $m-1$, прежде чем зациклиться — тогда период максимальный. Фишман и Мур после изучения кучи вариантов предложили, в частности, $a = 630\,360\,016$.

Покрути датчик руками. Ниже — решётка пар $(y_n, y_{n+1})$: берём соседние числа и кидаем точкой на плоскость. На пресете «Кривой» сразу видно палево — точки садятся на несколько прямых (датчик с грубым модулем предсказуем). На «Хорошем (MINSTD)» — ровная заливка, закономерности не видно:

RANDU: самый знаменитый кидок в истории датчиков

А теперь поучительная история про то, как целое поколение инженеров развели. В библиотеке SSP для машин IBM-360 жил датчик RANDU: $m = 2^{31}$, множитель $a = 65539$, $c = 0$. На пары $(y_n, y_{n+1})$ он смотрится прилично — в плоскости палева нет. Им пользовались годами и не чуяли подвоха.

А подвох был жирнейший. Если брать числа тройками $(y_{3n-2},\, y_{3n-1},\, y_{3n})$ и кидать их точками в трёхмерный куб, они не заполняют его, как положено честным независимым числам, а ложатся всего на 15 плоскостей:

То есть «случайные» тройки на самом деле сидят по струнке на полутора десятках плоскостей — в 2D этого не видать, а в 3D вылезает наружу. Классический случай: датчик выглядит чётко, пока не посмотришь под правильным углом.

Покрути куб. Переключи на RANDU и поймай ракурс вдоль диагонали — точки схлопнутся в плоскости. А на «хорошем» датчике облако заполняет куб ровно, без строя:

Мораль простая и злая: датчик может выглядеть чистым на одном тесте и с треском спалиться на другом. Нельзя верить генератору на слово — его надо гонять по проверкам.

Уичман–Хилл: три датчика в одной упряжке

Как сделать надёжно? Не полагаться на один станок, а запустить несколько сразу и смешать. Датчик Уичмана–Хилла (1982) гоняет три мультипликативных датчика параллельно, с такими параметрами:

На $n$-м шаге каждый выдаёт своё $y'_n, y''_n, y'''_n$, а итог — дробная часть их суммы: $y_n = \{\,y'_n + y''_n + y'''_n\,\}$ (фигурные скобки — «взять только то, что после запятой»).

Выхлоп: период такого комбо — около $3 \cdot 10^{13}$. Это на порядки длиннее периода одиночного датчика Фишмана–Мура ($2^{31} - 2 \approx 2 \cdot 10^9$), да ещё и на компьютере считается в несколько раз быстрее. Трое по понятиям держат район куда дольше, чем один.

Что в сухом остатке

Математический датчик — это короткий рекуррентный алгоритм: задал старт (seed) — получил воспроизводимую цепочку псевдослучайных чисел, быстро и без тетрадей. Но:

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

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

Проверь себя