Как работает генератор случайных чисел

Компьютер представляет собой машину, которая в точности выполняет инструкции. Как же тогда он подбрасывает монетку, бросает кубик или выбирает случайное имя? Если коротко, чаще всего он вообще не создаёт по-настоящему случайных чисел. Он создаёт числа, которые только выглядят случайными, и для большинства задач этого достаточно. Разберём, как работает генератор случайных чисел, где он может подвести и как выбирают результат инструменты нашего сайта.

Два вида случайности

• Истинно случайные числа берутся из физических явлений, которые никто не может предсказать: электрического шума в схеме, радиоактивного распада, атмосферных радиопомех. Например, Random.org использует атмосферный шум.
• Псевдослучайные числа получаются по формуле. Берут начальное число, которое называют зерном (seed), пропускают его через формулу и получают следующее число, затем ещё одно. Результат выглядит случайным, но одно и то же зерно всегда даёт одну и ту же последовательность.

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

Первый компьютерный метод и его изъян

Около 1949 года математик Джон фон Нейман предложил метод середины квадрата: число возводят в квадрат, берут средние цифры и повторяют. Начнём с 1234: его квадрат равен 01522756, значит, следующее число 5227, затем 3215, 3362, 3030 и так далее.

Выглядит случайно, но метод попадает в циклы. Если начать с 2916, получится 5030, 3009, 0540, 2916, а потом те же четыре числа без конца. Фон Нейман об этом знал. Он пользовался методом, потому что тот был быстрым, и проверял результаты на ошибки. Его знаменитая шутка гласила, что всякий, кто пытается получать случайные числа арифметическими методами, «пребывает в состоянии греха».

До компьютеров: книги случайных чисел

Учёным так нужны были случайные числа, что их печатали в книгах. В 1955 году RAND Corporation выпустила книгу A Million Random Digits with 100,000 Normal Deviates, составленную с помощью электронной рулетки. Исследователи открывали случайную страницу и выписывали цифры подряд. А задолго до этого люди пользовались игральными костями, монетами и жребием, об этом рассказывает наша статья о гадании на кубиках в древности.

Как работают современные генераторы

Современные генераторы псевдослучайных чисел намного лучше. Среди самых распространённых:

• Mersenne Twister (вихрь Мерсенна): генератор по умолчанию в Python и многих других инструментах. Он начинает повторяться только через 2¹⁹⁹³⁷ − 1 чисел, а в этом числе около 6000 цифр.
• xorshift128+: генератор, на котором работает Math.random() в Chrome и других браузерах на движке V8. Очень быстрый, хорошо подходит для игр и анимаций.
• Криптографические генераторы: такие используют для паролей и ключей шифрования. Операционная система подмешивает непредсказуемые физические события, например крошечные различия во времени работы оборудования, поэтому даже тот, кто знает формулу, не может предсказать следующее число.

Для игры обычных генераторов вполне хватает. Но если кто-то увидит достаточно их результатов, иногда он может вычислить и остальные. Там, где важны честность или безопасность, нужен криптографический генератор.

Скрытая ловушка: смещение по модулю

Даже идеальный генератор может давать нечестные результаты, если пользоваться им небрежно. Допустим, у вас есть случайный байт, то есть число от 0 до 255, а нужен бросок кубика. Проще всего разделить на 6 и взять остаток. Но 256 не делится на 6 нацело, поэтому четыре грани получают по одному лишнему шансу:

Разница небольшая, но на тысячах бросков она заметна. Исправить это просто: если случайное число попало в неровный остаток, его отбрасывают и берут новое. Этот приём называется выборкой с отклонением.

Как выбирают наши инструменты

Наши инструменты Подбросить монетку, Бросить кубик, Генератор случайных чисел, Рандомайзер имён и другие, у которых тот же код, берут числа из криптографического генератора вашего браузера, он называется crypto.getRandomValues. Кроме того, они применяют выборку с отклонением, поэтому у каждой грани, числа и имени ровно одинаковые шансы. Старые браузеры, где этой функции нет, переходят на Math.random(). Всё работает в вашем собственном браузере, на нашем сервере ничего не решается.

Так это действительно случайно?

Для подбрасывания монеты или броска кубика хороший генератор лучше настоящих предметов. Настоящая монета чуть-чуть чаще падает той стороной, которая была сверху в начале, об этом рассказано в нашей статье о вероятности орла и решки, а настоящие кубики могут быть слегка неровными. У хорошего генератора нет ни той, ни другой проблемы.

Больший риск исходит от человека, который смотрит на результаты. Мы видим закономерности в сериях и ждём, что «недостающий» результат вот-вот выпадет. Это ошибка игрока, и она обманывает людей гораздо чаще, чем любой компьютер. А о том, как плохо люди сами придумывают случайные числа, читайте в статье «Может ли человек быть случайным?».

Частые вопросы

Может ли компьютер создавать по-настоящему случайные числа?

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

Что такое зерно (seed) в генераторе случайных чисел?

Это начальное число для формулы. Одно и то же зерно всегда даёт одну и ту же последовательность. Это удобно для тестирования и для игр, где можно поделиться миром или уровнем по его зерну.

Math.random() действительно случаен?

Нет. Это быстрый генератор псевдослучайных чисел, он подходит для игр, но не для секретных данных и не там, где на кону деньги. Для этого в браузерах есть crypto.getRandomValues.

Честно ли подбрасывать монетку и бросать кубики онлайн?

Если инструмент сделан хорошо, да. Наши монетка и кубик используют криптографический генератор браузера с выборкой с отклонением, поэтому у каждого результата ровно одинаковый шанс.

Что такое смещение по модулю?

Небольшая нечестность, которая появляется, когда случайное число загоняют в меньший диапазон с помощью остатка от деления, а исходный диапазон не делится на него нацело. Выборка с отклонением её устраняет.