Как создать простой генератор псевдослучайных чисел без random

Зачем писать генератор самостоятельно

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

Формула линейного конгруэнтного генератора

Алгоритм хранит одно число — текущее состояние генератора, которое называют seed или начальным значением. Каждое следующее число получается из текущего по одной и той же формуле: новое значение равно остатку от деления выражения на модуль m, где само выражение — это текущее значение, умноженное на константу a, плюс ещё одна константа c. В привычной записи это выглядит так — X(n+1) = (a * X(n) + c) mod m, где X(n) — текущее состояние, X(n+1) — следующее, a называют множителем, c — приращением, а m — модулем. Именно это последнее число, X(n+1), и становится очередным «случайным» числом генератора, а заодно новым текущим состоянием для следующего шага.

Первое число в цепочке задаётся напрямую, а не вычисляется по формуле — это и есть seed, начальное значение всей последовательности. От выбора seed зависит, с какого именно числа генератор начнёт свою цепочку, но не то, насколько равномерно и длинно эта цепочка будет проходить по всем возможным значениям — за это отвечают уже a, c и m.

Как выбрать параметры a, c и m

Наугад взятые a, c и m почти всегда дают короткую и неравномерную последовательность — числа могут скатиться в цикл из нескольких повторяющихся значений уже через десяток шагов. Для генератора с хорошими свойствами параметры подбирают по правилам, которые математики сформулировали ещё в прошлом веке. Модуль m и приращение c не должны иметь общих делителей, кроме единицы. Множитель a минус один должен без остатка делиться на каждый простой делитель модуля m. Если m делится на четыре, то и a минус один тоже обязано делиться на четыре. При соблюдении всех трёх условий генератор проходит через все m возможных значений прежде, чем начнёт повторяться — такой результат называют полным периодом.

Период генератора и почему он важен

Периодом называют длину цепочки чисел, после которой последовательность начинает повторяться заново с того же самого состояния, что и в начале. У линейного конгруэнтного генератора период не может превышать модуль m — больше m различных остатков от деления просто не существует. Полный период в m шагов получают только при выполнении условий из предыдущего раздела; при их нарушении реальный период оказывается заметно короче, а иногда генератор вообще зацикливается на нескольких числах уже после первых итераций. Для учебной программы, которой нужно сгенерировать десяток-другой чисел, разница почти не заметна. Для симуляции с миллионами итераций короткий период станет видимой проблемой — узор из чисел начнёт повторяться прямо посреди расчёта.

Почему числа называются псевдослучайными

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

Где такие числа применять нельзя

Предсказуемость линейного конгруэнтного генератора делает его непригодным везде, где от случайности зависят деньги или безопасность. Зная всего несколько подряд идущих чисел из цепочки, можно восстановить параметры a, c и m и предсказать все следующие числа наперёд — это стандартная студенческая задача на курсах по криптографии, а не гипотетическая угроза. Поэтому такой генератор нельзя ставить в основу лотерей, розыгрышей призов, игр на реальные деньги, генерации паролей, токенов сессии или ключей шифрования. Для всех перечисленных задач существуют отдельные криптографически стойкие генераторы, устроенные принципиально иначе и специально защищённые от восстановления параметров по наблюдаемым числам.

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

Как проверить равномерность простыми тестами

Полноценную статистическую экспертизу генератора проводят специальными пакетами тестов, но для учебной проверки хватает пары простых приёмов, которые легко собрать самостоятельно. Первый — гистограмма частот. Генератор запускают несколько тысяч раз, каждое число делят на небольшое число корзин, например на десять, и считают, сколько значений попало в каждую корзину. У равномерного генератора все корзины набирают примерно одинаковое количество попаданий, без явных провалов или всплесков в одной из них. Второй приём — визуальная проверка парами. Числа откладывают на графике попарно, где по одной оси идёт каждое чётное по счёту число, а по другой — следующее за ним нечётное. Хороший генератор даёт на таком графике облако точек без видимой структуры, а генератор с неудачно подобранными параметрами часто выдаёт заметные полосы или решётку — числа выстраиваются вдоль нескольких прямых линий вместо равномерного облака.