Как работает компьютерный рандом

Обновлено: 18.05.2024

Генератор псевдослучайных чисел

Так как же генерировать случайные числа? В реальной жизни мы часто бросаем монетку (орел/решка), кости или перетасовываем карты. Эти события включают в себя так много физических переменных (например, сила тяжести, трение, сопротивление воздуха и т.д.), что они становятся почти невозможными для прогнозирования/контроля и выдают результаты, которые во всех смыслах являются случайными.

Однако компьютеры не предназначены для использования физических переменных — они не могут подбросить монетку, бросить кости или перетасовать реальные карты. Компьютеры живут в контролируемом электрическом мире, где есть только два значения (true и false), чего-то среднего между ними нет. По своей природе компьютеры предназначены для получения прогнозируемых результатов. Когда мы говорим компьютеру посчитать, сколько будет 2 + 2 , мы всегда хотим, чтобы ответом было 4 (не 3 и не 5 ).

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

На самом деле, написать простой ГПСЧ не так уж и сложно. Вот небольшая программа, которая генерирует 100 рандомных чисел:

// Берем стартовое число и, с его помощью, генерируем новое значение. // Из-за использования очень больших чисел (и переполнения) угадать следующее число исходя из предыдущего - очень сложно // Берем стартовое число и возвращаем значение в диапазоне от 0 до 32767 // Если вывели 5 чисел, то вставляем символ новой строки

Результат выполнения программы:

18256 4675 32406 6217 27484
975 28066 13525 25960 2907
12974 26465 13684 10471 19898
12269 23424 23667 16070 3705
22412 9727 1490 773 10648
1419 8926 3473 20900 31511
5610 11805 20400 1699 24310
25769 9148 10287 32258 12597
19912 24507 29454 5057 19924
11591 15898 3149 9184 4307
24358 6873 20460 2655 22066
16229 20984 6635 9022 31217
10756 16247 17994 19069 22544
31491 16214 12553 23580 19599
3682 11669 13864 13339 13166
16417 26164 12711 11898 26797
27712 17715 32646 10041 18508
28351 9874 31685 31320 11851
9118 26193 612 983 30378
26333 24688 28515 8118 32105

Каждое число кажется случайным по отношению к предыдущему. Главный недостаток этого алгоритма — его примитивность.

Функции srand() и rand()

Языки Cи и C++ имеют свои собственные встроенные генераторы случайных чисел. Они реализованы в двух отдельных функциях, которые находятся в заголовочном файле cstdlib:

Функция srand() устанавливает передаваемое пользователем значение в качестве стартового. srand() следует вызывать только один раз — в начале программы (обычно в верхней части функции main()).

Функция rand() генерирует следующее случайное число в последовательности. Оно будет находиться в диапазоне от 0 до RAND_MAX (константа в cstdlib, значением которой является 32767 ).

Вот пример программы, в которой используются обе эти функции:

srand ( 4541 ) ; // устанавливаем стартовое значение - 4 541 // Если вывели 5 чисел, то вставляем символ новой строки

Результат выполнения программы:

14867 24680 8872 25432 21865
17285 18997 10570 16397 30572
22339 31508 1553 124 779
6687 23563 5754 25989 16527
19808 10702 13777 28696 8131
18671 27093 8979 4088 31260
31016 5073 19422 23885 18222
3631 19884 10857 30853 32618
31867 24505 14240 14389 13829
13469 11442 5385 9644 9341
11470 189 3262 9731 25676
1366 24567 25223 110 24352
24135 459 7236 17918 1238
24041 29900 24830 1094 13193
10334 6192 6968 8791 1351
14521 31249 4533 11189 7971
5118 19884 1747 23543 309
28713 24884 1678 22142 27238
6261 12836 5618 17062 13342
14638 7427 23077 25546 21229

Стартовое число и последовательности в ГПСЧ

Помните, что каждое новое число в последовательности ГПСЧ генерируется исходя из предыдущего определенным способом. Таким образом, при постоянном начальном числе ГПСЧ всегда будет генерировать одну и ту ​​же последовательность! В программе, приведенной выше, последовательность чисел всегда одинакова, так как стартовое число всегда равно 4541 .

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

В языке Cи есть функция time(), которая возвращает в качестве времени общее количество секунд, прошедшее от полуночи 1 января 1970 года. Чтобы использовать эту функцию, нам просто нужно подключить заголовочный файл ctime, а затем инициализировать функцию srand() вызовом функции time(0) .

Вот вышеприведенная программа, но уже с использованием функции time() в качестве стартового числа:

srand ( static_cast < unsigned int > ( time ( 0 ) ) ) ; // устанавливаем значение системных часов в качестве стартового числа // Если вывели 5 чисел, то вставляем символ новой строки

Теперь наша программа будет генерировать разные последовательности случайных чисел! Попробуйте сами.

Генерация случайных чисел в заданном диапазоне

Вот небольшая функция, которая конвертирует результат функции rand() в нужный нам диапазон значений:

// Генерируем рандомное число между значениями min и max. static const double fraction = 1.0 / ( static_cast < double > ( RAND_MAX ) + 1.0 ) ; // Равномерно распределяем рандомное число в нашем диапазоне return static_cast < int > ( rand ( ) * fraction * ( max - min + 1 ) + min ) ;

Чтобы сымитировать бросок кубика, вызываем функцию getRandomNumber(1, 6) .

Какой ГПСЧ является хорошим?

Как мы уже говорили, генератор случайных чисел, который мы написали выше, не является очень хорошим. Сейчас рассмотрим почему.

Хороший ГПСЧ должен иметь ряд свойств:

Свойство №1: ГПСЧ должен генерировать каждое новое число с примерно одинаковой вероятностью. Это называется равномерностью распределения. Если некоторые числа генерируются чаще, чем другие, то результат программы, использующей ГПСЧ, будет предсказуем! Например, предположим, вы пытаетесь написать генератор случайных предметов для игры. Вы выбираете случайное число от 1 до 10, и, если результатом будет 10, игрок получит крутой предмет вместо среднего. Шансы должны быть 1 к 10. Но, если ваш ГПСЧ неравномерно генерирует числа, например, десятки генерируются чаще, чем должны, то ваши игроки будут получать более редкие предметы чаще, чем предполагалось, и сложность, и интерес к такой игре автоматически уменьшаются.

Свойство №2: Метод, с помощью которого генерируется следующее число в последовательности, не должен быть очевиден или предсказуем. Например, рассмотрим следующий алгоритм ГПСЧ: num = num + 1 . У него есть равномерность распределения рандомных чисел, но это не спасает его от примитивности и предсказуемости!

Свойство №3: ГПСЧ должен иметь хорошее диапазонное распределение чисел. Это означает, что маленькие, средние и большие числа должны возвращаться случайным образом. ГПСЧ, который возвращает все маленькие числа, а затем все большие — предсказуем и приведет к предсказуемым результатам.

Свойство №4: Период циклического повторения значений ГПСЧ должен быть максимально большим. Все ГПСЧ являются циклическими, т.е. в какой-то момент последовательность генерируемых чисел начнет повторяться. Как упоминалось ранее, ГПСЧ являются детерминированными, и с одним значением ввода мы получим одно и то же значение вывода. Подумайте, что произойдет, когда ГПСЧ сгенерирует число, которое уже ранее было сгенерировано. С этого момента начнется дублирование последовательности чисел между первым и последующим появлением этого числа. Длина этой последовательности называется периодом.

Например, вот представлены первые 100 чисел, сгенерированные ГПСЧ с плохой периодичностью:

112 9 130 97 64
31 152 119 86 53
20 141 108 75 42
9 130 97 64 31
152 119 86 53 20
141 108 75 42 9
130 97 64 31 152
119 86 53 20 141
108 75 42 9 130
97 64 31 152 119
86 53 20 141 108
75 42 9 130 97
64 31 152 119 86
53 20 141 108 75
42 9 130 97 64
31 152 119 86 53
20 141 108 75 42
9 130 97 64 31
152 119 86 53 20
141 108 75 42 9

Несмотря на сложность разработки алгоритмов, отвечающих всем этим критериям, в этой области было проведено большое количество исследований, так как разные ГПСЧ активно используются в важных отраслях науки.

Почему rand() является посредственным ГПСЧ?

Одним из основных недостатков функции rand() является то, что RAND_MAX обычно устанавливается как 32767 (15-битное значение). Это означает, что если вы захотите сгенерировать числа в более широком диапазоне (например, 32-битные целые числа), то функция rand() не подойдет. Кроме того, она не подойдет, если вы захотите сгенерировать случайные числа типа с плавающей запятой (например, между 0.0 и 1.0 ), что часто используется в статистическом моделировании. Наконец, функция rand() имеет относительно короткий период по сравнению с другими алгоритмами.

Тем не менее, этот алгоритм отлично подходит для изучения программирования и для программ, в которых высококлассный ГПСЧ не является необходимостью.

Отладка программ, использующих случайные числа

Программы, которые используют случайные числа, трудно отлаживать, так как при каждом запуске такой программы мы будем получать разные результаты. А чтобы успешно проводить отладку программ, нужно удостовериться, что наша программа выполняется одинаково при каждом её запуске. Таким образом, мы сможем быстро узнать расположение ошибки и изолировать этот участок кода.

Поэтому, проводя отладку программы, полезно использовать в качестве стартового числа (с использованием функции srand()) определенное значение (например, 0 ), которое вызовет ошибочное поведение программы. Это будет гарантией того, что наша программа каждый раз генерирует одни и те же результаты (что значительно облегчит процесс отладки). После того, как мы найдем и исправим ошибку, мы сможем снова использовать системные часы для генерации рандомных результатов.

Рандомные числа в C++11

В C++11 добавили тонну нового функционала для генерации случайных чисел, включая алгоритм Вихрь Мерсенна, а также разные виды генераторов случайных чисел (например, равномерные, генератор Poisson и пр.). Доступ к ним осуществляется через подключение заголовочного файла random. Вот пример генерации случайных чисел в C++11 с использованием Вихря Мерсенна:

В этой статье вы увидите самые разнообразные велосипеды алгоритмы для генерации случайных чисел.

Про что статья


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

C++ rand

Первое что узнаёт начинающий программист С++ по теме получения рандома — функция rand, которая генерирует случайное число в пределах от 0 и RAND_MAX. Константа RAND_MAX описана в файле stdlib.h и равна 32'767, но этом может быть не так, например в Linux (см. коммент). Если же rand() в вашем компиляторе генерирует числа в пределах 32'767 (0x7FFF) и вы хотите получить случайное число большого размера, то код ниже можно рассматривать как вариант решения этой проблемы:

Реализация функции rand в старом C была проста и имела следующий вид:


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

С++11 STL random

Данный сорт рандома появился в C++11 и представляет из себя следующий набор классов: minstd_rand, mt19937, ranlux, knuth_b и разные их вариации.

Чтобы последовательность случайных чисел не повторялась при каждом запуске программы, задают «зерно» псевдослучайного генератора в виде текущего времени или, в случае с некоторыми ретро (и не только) играми — интервалы между нажатиями клавиш с клавиатуры/джойстика. Библиотека random же предлагает использовать std::random_device для получения зерна лучше чем от time(NULL), однако в случае с компилятором MinGW в Windows функция практически не работает так как надо. До сих пор…


Некоторые из алгоритмов в STL random могут работать быстрее чем rand(), но давать менее качественную последовательность случайных чисел.

PRNG — Pseudo-random Numbers Generator

Можете считать это название — синонимом линейного конгруэнтного метода. PRNG алгоритмы похожи на реализацию rand в C и отличаются лишь константами.


PRNG алгоритмы быстро работают и легки в реализации на многих языках, но не обладают большим периодом.

XorShift


Данный генератор очень хорош тем, что в нём вообще нет операций деления и умножения — это может быть полезно на процессорах и микроконтроллерах в которых нету ассемблерных инструкций деления/умножения (PIC16, Z80, 6502).

Z26 это эмулятор старенькой приставки Atari2600, в коде которого можно обнаружить рандом ориентированный на работу с 1-байтовыми регистрами.


Однажды мне пришлось сделать реализацию этого алгоритма для z80:

Компактный рандом для Z80 от Joe Wingbermuehle

Если вам интересно написание программ под машины с зилогом, то представляю вашему вниманию алгоритм от Joe Wingbermuehle (работает только на зилоге):

Генератор рандома в DOOM

В исходниках игры Дум есть такой интересный файл под названием m_random.c (см. код), в котором описана функция «табличного» рандома, то есть там вообще нет никаких формул и магии с битовыми сдвигами.

Приведу более компактный код наглядно показывающий работу этой функции.

Конечно же это ни какой не рандом и последовательность случайных чисел легко предугадать даже на уровне интуиции в процессе игры, но работает всё это крайне быстро. Если вам не особо важна криптографическая стойкость и вы хотите что-то быстро генерирующее «типа-рандом», то эта функция для вас. Кстати в Quake3 рандом выглядит просто — rand()&0x7FFF.

RDRAND

Некоторые современные процессоры способны генерировать случайные числа с помощью одной ассемблерной команды — RDRAND. Для использования этой функции в C++ вы можете вручную прописать нужные инструкции ассемблерными вставками или же в GCC подключить файл immintrin.h и выбрать любую из вариаций функции _rdrandXX_step, где XX означает число бит в регистре и может быть равно 16, 32 или 64.


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

Концовка

Класс std::minstd_rand из библиотеки STL random работает быстрее обыкновенного rand() и может стать его альтернативной заменой, если вас не особо волнует длинна периода в minstd. Возможны различия в работе этих функций в Windows и Unix'ах.

Что такое случайность в компьютере? Как происходит генерация случайных чисел? В этой статье мы постарались дать простые ответы на эти вопросы.

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

Определение того, что именно является случайностью, может быть довольно сложной задачей. Существуют тесты (например, колмогоровская сложность), которые могут дать вам точное значение того, насколько случайна та или иная последовательность. Но мы не будем заморачиваться, а просто попробуем создать последовательность чисел, которые будут казаться несвязанными между собой.

Часто требуется не просто одно число, а несколько случайных чисел, генерируюемых непрерывно. Следовательно, учитывая начальное значение, нам нужно создать другие случайные числа. Это начальное значение называется семенем, и позже мы увидим, как его получить. А пока давайте сконцентрируемся на создании других случайных значений.

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

Давайте поэкспериментируем с этой идеей и посмотрим, куда она нас приведёт.

Функция искажения будет принимать одно значение, а возвращать другое. Назовём её R.

Начнём с того, что R - это простая функция, которая всего лишь прибавляет единицу.

Если значение нашего семени 1, то R создаст ряд 1, 2, 3, 4, . Выглядит совсем не случайно, но мы дойдём до этого. Пусть теперь R добавляет константу вместо 1.

Если с равняется, например, 7, то мы получим ряд 1, 8, 15, 22, . Всё ещё не то. Очевидно, что мы упускаем то, что числа не должны только увеличиваться, они должны быть разбросаны по какому-то диапазону. Нам нужно, чтобы наша последовательность возвращалась в начало - круг из чисел!

Числовой круг

Посмотрим на циферблат часов: наш ряд начинается с 1 и идёт по кругу до 12. Но поскольку мы работаем с компьютером, пусть вместо 12 будет 0.

number circle

Теперь начиная с 1 снова будем прибавлять 7. Прогресс! Мы видим, что после 12 наш ряд начинает повторяться, независимо от того, с какого числа начать.

Здесь мы получаем очень важно свойство: если наш цикл состоит из n элементов, то максимальное число элементов, которые мы можем получить перед тем, как они начнут повторяться это n.

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

На этом этапе вы можете заметить, что некоторые числа не подходят для c. Если c = 4, и мы начали с 1, наша последовательность была бы 1, 5, 9, 1, 5, 9, 1, 5, 9, . что нам конечно же не подходит, потому что эта последовательность абсолютно не случайная. Становится понятно, что числа, которые мы выбираем для длины цикла и длины прыжка должны быть связаны особым образом.

Если вы попробуете несколько разных значений, то сможете увидеть одно свойство: m и с должны быть взаимно простыми.

До сих пор мы делали "прыжки" за счёт добавления, но что если использовать умножение? Умножим х на константу a.

Свойства, которым должно подчиняться а, чтобы образовался полный цикл, немного более специфичны. Чтобы создать верный цикл:

  1. (а - 1) должно делиться на все простые множители m
  2. (а - 1) должно делиться на 4, если m делится на 4

Эти свойства вместе с правилом, что m и с должны быть взаимно простыми составляют теорему Халла-Добелла. Мы не будем рассматривать её доказательство, но если бы вы взяли кучу разных значений для разных констант, то могли бы прийти к тому же выводу.

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

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

Когда мы применяем функцию к её результату несколько раз, мы получаем рекуррентное соотношение. Давайте запишем нашу формулу с использованием рекурсии:

Где начальное значение х - это семя, а - множитель, с - константа, m - оператор остатка от деления.

То, что мы сделали, называется линейным конгруэнтным методом. Он очень часто используется, потому что он прост в реализации и вычисления выполняются быстро.

В разных языках программирования реализация линейного конгруэнтного метода отличается, то есть меняются значения констант. Например, функция случайных чисел в libc (стандартная библиотека С для Linux) использует m = 2 ^ 32, a = 1664525 и c = 1013904223. Такие компиляторы, как gcc, обычно используют эти значения.

Существуют и другие алгоритмы генерации случайных чисел, но линейный конгруэнтный метод считается классическим и лёгким для понимания. Если вы хотите глубже изучить данную тему, то обратите внимание на книгу Random Numbers Generators, в которой приведены элегантные доказательства линейного конгруэнтного метода.

Генерация случайных чисел имеет множество приложений в области информатики и особенно важна для криптографии.

Вы когда-нибудь задумывались, как работает Math.random()? Что такое случайное число и как оно получается? А представьте вопрос на собеседовании — напишите свой генератор случайных чисел в пару строк кода. И так, что же это такое, случайность и возможно ли ее предсказать.

Генератор псевдослучайных чисел и генератор случайных чисел

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

Этот источник используется для накопления энтропии с последующим получением из неё начального значения (initial value, seed), которое необходимо генераторам случайных чисел (ГСЧ) для формирования случайных чисел.

Генератор ПсевдоСлучайных Чисел использует единственное начальное значение, откуда и следует его псевдослучайность, в то время как Генератор Случайных Чисел всегда формирует случайное число, имея в начале высококачественную случайную величину, которая берется из различных источников энтропии.

Энтропия — это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.

Выходит, что чтобы создать псевдослучайную последовательность нам нужен алгоритм, который будет генерить некоторую последовательность на основании определенной формулы. Но такую последовательность можно будет предсказать. Тем не менее, давайте пофантазируем, как бы могли написать свой генератор случайных чисел, если бы у нас не было Math.random()

ГПСЧ имеет некоторый алгоритм, который можно воспроизвести.
ГСЧ — это получение чисел полностью из какого либо шума, возможность просчитать который стремится к нулю. При этом в ГСЧ есть определенные алгоритмы для выравнивания распределения.

Придумываем алгоритм ГПСЧ

Генератор псевдослучайных чисел (ГПСЧ, англ. pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Мы можем взять последовательность каких-то чисел и брать от них модуль числа. Самый простой пример, который приходит в голову. Нам нужно подумать, какую последовательность взять и модуль от чего. Если просто в лоб от 0 до N и модуль 2, то получится генератор 1 и 0:

Эта функция генерит нам последовательность 01010101010101… и назвать ее даже псевдослучайной никак нельзя. Чтобы генератор был случайным, он должен проходить тест на следующий бит. Но у нас не стоит такой задачи. Тем не менее даже без всяких тестов мы можем предсказать следующую последовательность, значит такой алгоритм в лоб не подходит, но мы в нужном направлении.

А что если взять какую-то известную, но нелинейную последовательность, например число PI. А в качестве значения для модуля будем брать не 2, а что-то другое. Можно даже подумать на тему меняющегося значения модуля. Последовательность цифр в числе Pi считается случайной. Генератор может работать, используя числа Пи, начиная с какой-то неизвестной точки. Пример такого алгоритма, с последовательностью на базе PI и с изменяемым модулем:

Но в JS число PI можно вывести только до 48 знака и не более. Поэтому предсказать такую последовательность все так же легко и каждый запуск такого генератора будет выдавать всегда одни и те же числа. Но наш генератор уже стал показывать числа от 0 до 9. Кстати, так выглядит распределение по выпадению чисел при 10000 итерациях:

Распределение очень неравномерное, но мы получим генератор чисел от 0 до 9.

Мы можем взять не число Pi, а время в числовом представлении и это число рассматривать как последовательность цифр, причем для того, чтобы каждый раз последовательность не повторялась, мы будем считывать ее с конца. Итого наш алгоритм нашего ГПСЧ будет выглядеть так:

Вот это уже похоже на генератор псевдослучайных чисел. И тот же Math.random() — это ГПСЧ, про него мы поговорим чуть позже. При этом у нас каждый раз первое число получается разным.

Собственно на этих простых примерах можно понять как работают более сложные генераторы случайных числе. И есть даже готовые алгоритмы. Для примера разберем один из них — это Линейный конгруэнтный ГПСЧ(LCPRNG).

Линейный конгруэнтный ГПСЧ

Линейный конгруэнтный ГПСЧ(LCPRNG) — это распространённый метод для генерации псевдослучайных чисел. Он не обладает криптографической стойкостью. Этот метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:



где a(multiplier), c(addend), m(mask) — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа — т.е. seed. При разных значениях seed получаются различные последовательности случайных чисел. Пример реализации такого алгоритма на JavaScript:

Многие языки программирования используют LСPRNG (но не именно такой алгоритм(!)).

Как говорилось выше, такую последовательность можно предсказать. Так зачем нам ГПСЧ? Если говорить про безопасность, то ГПСЧ — это проблема. Если говорить про другие задачи, то эти свойства — могут сыграть в плюс. Например для различных спец эффектов и анимаций графики может понадобиться частый вызов random. И вот тут важны распределение значений и перформанс! Секурные алгоритмы не могут похвастать скоростью работы.

Еще одно свойство — воспроизводимость. Некоторые реализации позволяют задать seed, и это очень полезно, если последовательность должна повторяться. Воспроизведение нужно в тестах, например. И еще много других вещей существует, для которых не нужен безопасный ГСЧ.

Как устроен Math.random()

Метод Math.random() возвращает псевдослучайное число с плавающей запятой из диапазона [0, 1) , то есть, от 0 (включительно) до 1 (но не включая 1), которое затем можно отмасштабировать до нужного диапазона. Реализация сама выбирает начальное зерно для алгоритма генерации случайных чисел; оно не может быть выбрано или сброшено пользователем.

Как устроен алгоритм Math.random() — интересный вопрос. До недавнего времени, а именно до 49 Chrome использовался алгоритм MWC1616:

Именно этот алгоритм генерит нам последовательность псевдослучайных чисел в промежутке между 0 и 1.

UPD

то видим, что должны быть скобки:

Предсказываем Math.random()

В нем есть задача:

Что нужно вписать вместо вопросов, чтобы функция вернула true? Кажется что это невозможно. Но, это возможно, если вы заглядывали в спеку и видели алгоритм ГПСЧ V8. Решение этой задачи в свое время мне показал Роман Дворнов:

Этот код работал в 70% случаев для Chrome < 49 и Node.js < 5. Рома Дворнов, как всегда, показал чудеса магии, которая не что иное, как глубокое понимание внутренних механизмов браузеров. Я все жду, когда Роман сделает доклад на основе этих событий или напишет более подробную статью.

есть такой генератор. Вот что было, когда в браузере был алгоритм MWC1616:



Видите эти равномерности на левом слайде? Изображение показывает проблему с распределением значений. На картинке слева видно, что значения местами сильно группируются, а местами выпадают большие фрагменты. Как следствие — числа можно предсказать.

Выходит что мы можем отреверсить Math.random() и предсказать, какое было загадано число на основе того, что получили в данный момент времени. Для этого получаем два значения через Math.random(). Затем вычисляем внутреннее состояние по этим значениям. Имея внутреннее состояние можем предсказывать следующие значения Math.random() при этом не меняя внутреннее состояние. Меняем код так так, чтобы вместо следующего возвращалось предыдущее значение. Собственно все это и описано в коде-решении для задачи random4. Но потом алгоритм изменили (подробности читайте в спеке). Его можно будет сломать, как только у нас в JS появится нормальная работа с 64 битными числами. Но это уже будет другая история.

Новый алгоритм выглядит так:

Его все так же можно будет просчитать и предсказать. Но пока у нас нет “длинной математики” в JS. Можно попробовать через TypedArray сделать или использовать специальные библиотеки. Возможно кто-то однажды снова напишет предсказатель. Возможно это будешь ты, читатель. Кто знает ?

Сrypto Random Values

Метод Math.random() не предоставляет криптографически стойкие случайные числа. Не используйте его ни для чего, связанного с безопасностью. Вместо него используйте Web Crypto API (API криптографии в вебе) и более точный метод window.crypto.getRandomValues() .

Пример генерации случайного числа:

Но, в отличие от ГПСЧ Math.random(), этот метод очень ресурсоемкий. Дело в том, что данный генератор использует системные вызовы в ОС, чтобы получить доступ к источникам энтропии (мак адрес, цпу, температуре, etc…).

Материалы про Math.random()

Больше про random в спецификации:

Хорошая статья про работу рандомайзера

Пример реализации предсказателя с Math.random()

Кстати, следить за обновлениями и прочими материалами от меня можно в телеграм канале: @prowebit

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

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

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

Полностью случайные числа генерируются истинным генератором случайных чисел (TRNG). Их можно получить, например, бросанием кубика или доставанием шаров из урны. Так как подобных устройств нет в компьютере, то в нем можно получить только "псевдослучайные" числа.

В Python, как и во всех остальных языках программирования, используется генератор псевдослучайных чисел, который выдает как будто случайные, но воспроизводимые числа.

Чтобы понять, как работают генераторы псевдослучайных чисел, рассмотрим работу одного из первых подобных генераторов. Его алгоритм работы был разработан Нейманом. В нем первое число возводят в квадрат, а потом из полученного результата берут средние цифры. Например, первое число 281, возводим его в квадрат, получаем 78961 и берем три цифры, находящиеся в середине – 896. После этого для генерации следующего числа используем 896.

Модуль random

В модуле random реализованы различные генераторы псевдослучайных чисел. Здесь присутствуют методы, с помощью которых можно получить равномерное, Гауссовское, бета и гамма распределения и другие функции. Практически все они зависят от метода random() . В Python, в качестве основного, используется генератор псевдослучайных чисел Mersenne Twister , который выдает 53-х битные вещественные числа.

👉 Как использовать: чтобы начать использовать встроенные генераторы случайных чисел, нужно сначала подключить модуль рандом:

После этого можно вызывать методы модуля random :

В модуле random существуют методы для генерации целых чисел, с плавающей точкой, для работы с последовательностями. Кроме этого существуют функции для управления генератором и генерации различных последовательностей. Рассмотрим основные из этих методов.

Случайные целые числа (int)

Перечислим основные функции, которые есть в модуле random для выдачи случайных целых чисел.

randint Функция randint(a, b) получает на вход два целых числа и возвращает случайное значение из диапазона [a, b] (a и b входят в этот диапазон).

import random random_number = random.randint(0, 125) print(random_number) > 113

randrange В функцию randrange(start, stop[, step]) передают три целых числа:

  • start – начало диапазона (входит в последовательность);
  • stop – конец диапазона (в последовательность не входит);
  • step – шаг генерации (если на его месте написать 0, получим ошибку "ValueError").

На выходе функция выдает случайное число в заданном диапазоне.

import random random_number = random.randrange(1, 100, 2) print(random_number) > 43

Случайные вещественные числа (float)

Перечислим функции, которые выдают вещественные числа.

random Функция random() выдает вещественные числа, в диапазоне [0.0, 1.0) (включая 0.0, но не включая 1.0).

import random random_number = random.random() print(random_number) > 0.47673250896173136

uniform Сгенерировать число с плавающей точкой можно с помощью функции uniform(a, b) . При этом полученное число будет в диапазоне [a, b) или [a, b] (a входит в диапазон, а вхождение b зависит от округления).

import random random_number = random.uniform(7.3, 10.5) print(random_number) > 10.320165816501492

Случайные элементы из последовательности

В модуле random языка Python есть несколько функций, которые можно применять для работы с последовательностями.

choice С помощью функции choice(seq) можно выбрать один элемент из набора данных. В качестве единственного аргумента в функцию передаётся последовательность. Если последовательность будет пустой (то есть в ней не будет ни одного элемента), получим ошибку "IndexError".

choices С помощью функции choices(seq [, weights, cum_weights, k]) можно выбрать 1 или несколько элементов из набора данных. weights , cum_weights и k — необязательные параметры.

  • weights — список относительных весов;
  • cum_weights — список кумулятивных (совокупных) весов, например weights [10, 5, 30, 5] эквивалентен cum_weights [10, 15, 45, 50].
  • k — длина возвращаемого списка (она может быть больше длины переданной последовательности и элементы могут дублироваться).

shuffle Перемешать элементы набора данных можно с помощью функции shuffle(x[, random]) .

  • х — последовательность;
  • random (необязательный параметр) — задает метод вероятностных распределений. Этот параметр не рекомендуется использовать в версии Python 3.9, а в версии 3.11 его поддержка будет прекращена.

shuffle перемешивает переданную последовательность, и возвращает None .

sample Чтобы выбрать какое-то количество элементов из набора данных можно воспользоваться функцией sample(х, k) .

  • х — последовательность;
  • k — количество элементов новой подпоследовательности.

На выходе получаем k уникальных случайных элементов из последовательности.

Если в исходной последовательности есть неуникальные (повторяющиеся) элементы, то каждый их них может появиться в новом списке.
import random seq = [10, 11, 12, 11, 14, 11] random_seq = random.sample(seq, 4) print(random_seq) > [10, 11, 11, 14]

Управление генератором

Генерация чисел в Python не совсем случайна и зависит от состояния генератора случайных чисел. Рассмотрим функции, с помощью которых можно управлять состоянием этого генератора.

getstate Метод getstate() модуля random возвращает объект, в котором записано текущим состояние генератора случайных чисел. Его можно использовать для восстановления состояния генератора. Эта функция не имеет параметров.

import random print(random.getstate()) > (3, (2147483648, 3570748448, 2839542888, 4273933825, 4291584237, .

setstate Метод setstate(state) применяется для восстановления состояния генератора случайных чисел. Обычно его используют совместно с методом getstate() . В качестве параметра в функцию передается объект состояния генератора, полученный, например, с помощью функции getstate() .

seed Генератору случайных чисел нужно число, основываясь на котором он сможет начать генерировать случайные значения.

Задать начальное значение можно с помощью метода seed(a=None, version=2) .

  • а — начальное число, с которого начинается генерация. Этот параметр не обязательный. Если он не задан, используется текущее системное время (или доступный механизм генерации, предоставляемый ОС);
  • version — стратегия интерпретации первого аргумента. По умолчанию используется версия 2, при которой str, bytes и bytearray преобразуются в int. Версия 1 (используется для совместимости со старыми версиями Python) и в ней для str и bytes генерирует более узкий диапазон начальных значений.

Вероятностное распределение

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

Для наглядности рассмотрим самое распространенное нормальное распределение вероятностей. На рисунке ниже приведена кривая нормального распределения.

В модуле random существуют функции, которые позволяют использовать различные методы вероятностных распределений:

  • triangular(a, b, mode) — генерирует случайное вещественное число, находящееся в диапазоне от a до b. По умолчанию эти параметры равны: а = 0, b = 1. Третий параметр mode задает среднюю точку вероятности распределения. (подробнее про треугольное распределение тут ).
  • betavariate(alpha, beta) — генерирует случайные числа соответствующие параметрам бета-распределения. Возвращаемые значения лежат в диапазоне от 0 до 1.
  • expovariate(lambd) — можно получить случайные значения, соответствующие экспоненциальному распределению. Если lambd положительное, то на выходе будут значения от 0 до +∞, а если отрицательное, то от -∞ до 0.
  • gammavariate(alpha, beta) — на выходе получаются случайные числа, соответствующие гамма распределению. Параметры alpha и beta, передаваемые в функцию должны быть больше 0.
  • gauss(mu, sigma) — на выходе получаются случайные числа, которые соответствуют Гауссовому распределению. В этот метод передаются два параметра: mu — среднее значение и sigma — среднеквадратичное отклонение.
  • lognormvariate(mu, sigma) — генерирует случайные значения соответствующие логарифму нормального распределения. То есть если вычислить натуральный логарифм полученного распределения, то в результате получится нормальное распределение с параметрами mu (среднее) и sigma (среднеквадратичное отклонение).
  • normalvariate(mu, sigma) — предназначен для генерации случайных значений подчиняющихся закону нормального распределения. В качестве параметров передаются: mu — среднее распределения и sigma — стандартное отклонение.
  • vonmisesvariate(mu, kappa) — используется для возврата случайного числа с плавающей запятой с распределением фон Мизеса (или круговым нормальным распределением).
  • paretovariate(alpha) — выдает случайные числа, соответствующие распределению Парето. Параметр alpha задает форму.
  • weibullvariate(alpha, beta) — Значения, выдаваемые weibullvariate соответствуют распределению Вейбулла. Параметр alpha задает масштаб, а beta форму.
💭 Ознакомиться со всеми функциями модуля random можно на официальном сайте Python в разделе документация .

Best practices

Приведем несколько примеров использования случайных чисел.

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

💭 Для имитации действий человека можно использовать random.uniform(1, 3) — это добавит случайные миллисекунды к вашим задержкам.

Дано: веб-сайт. В базе данных 4 баннера, к каждому баннеру указан вес (приоритет к показу).

Необходимо рандомно показывать на сайте 1 баннер, в зависимости от его веса.

С помощью генератора случайных чисел можно создавать пароли. Например, сгенерировать стойкий пароль можно так:

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

Методы модуля random позволяют получить случайные данные с использованием Mersenne Twister. Однако имейте в виду, что данный способ не является криптографически безопасным (для генерирования паролей есть более надежные варианты).

Кроме модуля random , в Python существуют альтернативные модули, позволяющие получить случайное значения:

Читайте также: