Для чего этот генератор годится, а для чего нет
Псевдослучайные генераторы колоссально различаются по пригодности. Этот быстр, воспроизводим и статистически хорошо ведёт себя в повседневных задачах — и он решительно не является источником секретов.
| Применение | Годится? | Почему |
|---|---|---|
| Преподавание, моделирование, выборки | Да | Воспроизводимость выборки здесь преимущество |
| Розыгрыш, кости, лотерейные номера | Да, с новым зерном | Всякий, кто знает зерно, воспроизведёт выборку |
| Пароли, ключи, токены, идентификаторы сессий | Нет | Состояние восстанавливается из вывода; используйте генератор паролей |
| Регулируемые игры и азартные игры | Нет | Там требуются сертифицированные аппаратные или криптографические генераторы |
- Оба конца диапазона включены, поэтому диапазон от 1 до 100 содержит 100 возможных значений.
- Без возвращения число выборок не может превышать число значений в диапазоне. Калькулятор отказывается, а не повторяет молча.
Что такое псевдослучайный генератор
Псевдослучайный генератор — это детерминированный алгоритм, порождающий последовательность, которая проходит статистические проверки на случайность. Физически случайной она не является: это фиксированное рекуррентное соотношение, и от заданного начального значения — зерна — оно всегда порождает одну и ту же последовательность.
Здесь применён 32-битный генератор xorshift, опубликованный Джорджем Марсальей в Journal of Statistical Software в 2003 году. Он работает, многократно применяя исключающее ИЛИ к значению и его сдвинутым копиям, с тройкой сдвигов, подобранной так, чтобы последовательность обошла все ненулевые 32-битные состояния прежде, чем повторится.
Работа от зерна — осознанный выбор, а не ограничение. Каждый калькулятор на этом сайте является чистой функцией своих входных данных, и именно это делает результаты воспроизводимыми и проверяемыми. Заодно это даёт то, чего генератор от часов дать не может: укажите зерно рядом с числами, и любой воспроизведёт вашу выборку в точности.
Как пользоваться генератором случайных чисел
- Задайте наименьшее и наибольшее значения. Оба конца входят в диапазон.
- Выберите, сколько чисел взять.
- Решите, разрешены ли повторы. Без возвращения ни одно значение не может выпасть дважды, поэтому взять чисел больше, чем содержит диапазон, нельзя.
- Меняйте зерно всякий раз, когда нужна другая выборка. Одно и то же зерно всегда возвращает те же числа.
Как получаются числа
Рекуррентное соотношение xorshift трижды преобразует 32-битное состояние за одну выборку, а затем делит его на 2^32, давая значение в промежутке от нуля до единицы, не включая её. Умножение на размер диапазона и взятие целой части отображают это в целое число.
Выборка без возвращения использует частичное перемешивание Фишера — Йейтса по диапазону. Каждый шаг меняет местами один оставшийся элемент, что выбирает равномерно случайное подмножество за один проход и не может застопориться, как подход «тяни и повторяй» по мере опустошения набора.
Частые ошибки
- Использовать псевдослучайный генератор для чего-либо секретного. Последовательность полностью определяется зерном.
- Ждать новых чисел, не меняя зерна. Воспроизводимость здесь и есть смысл, а зерно — орган управления.
- Считать, что верхняя граница исключена. Здесь оба конца диапазона включены.
- Запрашивать больше неповторяющихся значений, чем содержит диапазон.
- Принимать череду похожих значений за неисправность. Скучивание — нормальное свойство случайных последовательностей, и его отсутствие подозрительнее его наличия.
Часто задаваемые вопросы
Почему одно и то же зерно всегда даёт одни и те же числа?
Потому что псевдослучайный генератор — детерминированное рекуррентное соотношение, а зерно задаёт его начальное состояние. Это достоинство, а не изъян: указав зерно, вы позволяете любому в точности воспроизвести вашу выборку, а именно это и нужно воспроизводимым исследованиям и демонстрациям в классе. Чтобы выборка стала другой, смените зерно.
Достаточно ли это случайно для розыгрыша призов?
Для неформального розыгрыша — да, при условии что вы выберете зерно, которое участники не смогут предугадать, и опубликуете его потом, чтобы результат можно было проверить. Для регулируемых игр — нет: там требуются сертифицированные аппаратные генераторы или криптографически стойкие алгоритмы.
Можно ли этим сгенерировать пароль?
Нет. Внутреннее состояние генератора xorshift восстанавливается по короткому отрезку его вывода, поэтому всё производное от него предсказуемо. Используйте генератор паролей на этом сайте: он берёт данные из криптографически стойкого источника случайности операционной системы.
Что значит выборка без возвращения?
Это значит, что ни одно значение не может выпасть больше одного раза, как при вытягивании лотерейных шаров. Поскольку каждая выборка убирает значение из набора, взять чисел больше, чем содержит диапазон, нельзя: вытянуть шесть различных значений из диапазона в пять невозможно.
Равномерно ли распределены числа?
Да, с точностью до самого генератора. Каждое значение диапазона равновероятно, а режим без возвращения использует частичное перемешивание Фишера — Йейтса, которое выбирает любое подмножество заданного размера с одинаковой вероятностью.
Источники
- Marsaglia G. Xorshift RNGs. Journal of Statistical Software 2003; 8(14): 1-6. doi:10.18637/jss.v008.i14.
- Knuth DE. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition. Addison-Wesley, 1997 — random number generation and statistical testing.
- Fisher RA, Yates F. Statistical Tables for Biological, Agricultural and Medical Research. Oliver and Boyd, 1938 — the shuffle used for sampling without replacement.
- L'Ecuyer P, Simard R. TestU01: A C library for empirical testing of random number generators. ACM Transactions on Mathematical Software 2007; 33(4): 22.