Как сделать рандомайзер

Обновлено: 05.07.2024

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При разработке приложений часто нужно генерировать случайные числа. Java предоставляет для этого классы java.lang.Math и java.util.Random . В этой статье я расскажу о нескольких способах генерации случайных чисел и приведу конкретные примеры реализации.

Генерация случайных чисел с помощью класса Math

Чтобы сгенерировать случайное число Java предоставляет класс Math, доступный в пакете java.util. Этот класс содержит статичный метод Math.random(), предназначенный для генерации случайных чисел типа double .

Метод random( ) возвращает положительное число большее или равное 0,0 и меньшее 1,0. При вызове данного метода создается объект генератора псевдослучайных чисел java.util.Random.

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

Пример использования Math.random():

Метод getRandomNumber( ) использует Math.random() для возврата положительного числа, которое больше или равно 0,0 или меньше 1,0 .

Результат выполнения кода:

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

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

Разобьем это выражение на части:

Сначала умножаем диапазон значений на результат, который генерирует метод random().Math.random() * (max — min)возвращает значение в диапазоне [0 , max- min], где max не входит в заданные рамки. Например, выражение Math.random()*5 вернет значение в диапазоне [0 , 5], в который 5 не входит.
Расширяем охват до нужного диапазона. Это делается с помощью минимального значения.

Но выражение по-прежнему не охватывает максимальное значение.

Чтобы получить максимальное значение, прибавьте 1 к параметру диапазона (max — min). Это вернет случайное число в указанном диапазоне.

Существуют различные способы реализации приведенного выше выражения. Рассмотрим некоторые из них.

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

По умолчанию метод Math.random() при каждом вызове возвращает случайное число типа double . Например:

Вы можете вызвать предыдущий метод из метода main, передав аргументы, подобные этому.

Случайное целое число в заданном диапазоне

Пример генерации случайного целочисленного значения в указанном диапазоне:

Метод getRandomIntegerBetweenRange() создает случайное целое число в указанном диапазоне. Так как Math.random() генерирует случайные числа с плавающей запятой, то нужно привести полученное значение к типу int. Этот метод можно вызвать из метода main, передав ему аргументы следующим образом:

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

Генерация случайных чисел с помощью класса Random

Класс java.util.Random можно применять для генерации случайных чисел различных типов: int, float, double, long и boolean .

Для этого сначала создайте экземпляр класса Random, а затем вызовите один из методов генератора случайных значений: nextInt( ), nextDouble( ) или nextLong( ).

Метод nextInt( ) класса Random принимает граничное целое число и возвращает случайное значение int от 0 (включительно) до указанного предела (не включая).

Пример использования метода nextInt( ):

Пример использования метода nextInt ( ) для генерации целого числа в заданном диапазоне:

Методы nextFloat ( ) и nextDouble( ) позволяют генерировать числа с плавающей запятой, а также значения типа double в диапазоне от 0,0 до 1,0.

Код для использования обоих методов:

Генерируем случайное число в Java 8 — особенности

В Java 8 был представлен новый метод класса java.util.Random — ints(). Он возвращает неограниченный поток псевдослучайных значений int. Данный метод позволяет указать диапазон чисел, задав минимальное и максимальное значения.

Пример использования метода Random.ints() для генерации случайных целочисленных значений в указанном диапазоне:

Метод getRandomNumberInts( ) генерирует поток случайных целых чисел от min(включительно) и до max (не входит в диапазон).

Метод ints( ) создает IntStream, поэтому будет вызвана функция findFirst( ). Она возвращает объект OptionalInt , который описывает первый элемент этого потока. Затем код вызывает метод getAsInt( ), чтобы вернуть значение int в OptionalInt.

Пример использования метода Random.ints() для генерации потока случайных целочисленных значений:

Код для вызова предыдущего метода:

Пример использования метода Random.ints() для генерации потока из диапазона случайных целочисленных значений:

Код для вызова приведенного выше метода:

Кроме ints( ) существует еще несколько методов, которые были добавлены к классу Random в Java 8. Они могут возвращать последовательный поток случайных чисел. Это:

LongStream longs( );
DoubleStream doubles( ).

Заключение

Класс java.util.Random реализует линейный конгруэнтный генератор (LCG). Он отличается быстротой работы. Но при этом он не подходит для использования в режиме реального времени. Например, для генерации уникального идентификатора сессии на сервере, в научных экспериментах, криптографии лотереях и розыгрышах.

Пожалуйста, оставьте свои комментарии по текущей теме материала. Мы крайне благодарны вам за ваши комментарии, отклики, дизлайки, лайки, подписки!

Пожалуйста, оставляйте ваши отзывы по текущей теме материала. За комментарии, отклики, лайки, дизлайки, подписки огромное вам спасибо!

Вы когда-нибудь задумывались, как работает 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

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

Выходит что мы можем отреверсить 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

Основы

Каждый человек ежедневно сталкивается со случайностью. Википедия нам говорит: случайность — это результат маловероятного или непредсказуемого события. Непредсказуемого. Стоит отметить, что, чем сложнее система, тем ниже возможность прогнозировать (предсказывать) её будущие состояния. Мир сложен и именно по-этому случайность встречается столь часто. Можно сказать, что случайностью мы называем все события, которые не можем предугадать. Таким образом, разговор о случайном – это разговор о нехватке информации. Но эту нехватку человек научился использовать себе на пользу. К примеру, случайные величина широко применяются в криптографии.

В языке Python есть удобные инструменты для работы со случайными значениями. Речь о модуле стандартной библиотеки под названием random (и не только о нём). Давайте знакомиться!

Как использовать модуль random в Python

Для начала модуль надо импортировать.

Python функции модуля random

Случайное целое число — randint() функция random

Самое частое применение данного модуля — генерация случайных чисел. Самая популярная функция для этого — randint().

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

Генерация случайного целого числа — randrange()

Функция randrange() используется для генерации случайного целого числа в пределах заданного диапазона. Отличие от randint() заключается в том, что здесь есть третий параметр – шаг, по умолчанию равный единице.

Выбор случайного элемента из списка choice()

Функция sample()

random.sample() применяется, когда надо выбрать несколько элементов из заданной коллекции. Она возвращает список уникальных элементов, выбранных из исходной последовательности. Количество элементов, которое вернёт функция, задаётся аргументом k.

Случайные элементы из списка — choices()

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

Метод seed() используется для инициализации генератора псевдослучайных чисел в Python. Вот что это означает: для генерации псевдослучайных чисел необходимо какое-то исходное число и именно это число можно установить данным методом. Если значение seed не установлено, тогда система будет отталкиваться от текущего времени.

Перемешивание данных — shuffle()

Метод random.shuffle() применяется для расстановки элементов последовательности в случайном порядке. Представьте коробку в которой лежат какие-то предметы. Встряхните её 🙂

Генерации числа с плавающей запятой — uniform()

random.uniform() похожа на randint(), но применяется для генерации числа с плавающей запятой в указанном диапазоне.

Функция triangular()

Функция random.triangular() позволяет управлять вероятностью – она возвращает случайное число с плавающей запятой, которое соответствует заданному диапазону, а также уточняющему значению mode. Этот параметр дает возможность взвешивать возможный результат ближе к одному из двух других значений параметров. По умолчанию он находится посередине диапазона.

Криптографическая зашита генератора случайных данных

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

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

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

Самый простой способ задать массив со случайными элементами — использовать функцию sample (или random, или random_sample, или ranf — это всё одна и та же функция).

Без аргументов возвращает просто число в промежутке [0, 1), с одним целым числом — одномерный массив, с кортежем — массив с размерами, указанными в кортеже (все числа — из промежутка [0, 1)).

Генерация случайного n-мерного массива вещественных чисел

numpy.random.rand()применяется для генерации массива случайных вещественных чисел в пределах заданного диапазона.

Также можно генерировать числа согласно различным распределениям (Гаусса, Парето и другие). Чаще всего нужно равномерное распределение, которое можно получить с помощь функции uniform.

Для начала необходимо установить Numpy.

Генерация случайного n-мерного массива целых чисел

С помощью функции randint или random_integers можно создать массив из целых чисел. Аргументы: low, high, size: от какого, до какого числа (randint не включает в себя это число, а random_integers включает), и size — размеры массива.

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

Генерация случайных универсальных уникальных ID

Эта библиотека генерирует уникальные идентификаторы на основе системного времени и сетевого адреса компьютера. Объект UUID неизменяем и содержит некоторые функции для создания различных уникальных идентификаторов.

UUID Python, сгенерированный с помощью функции uuid4(), создается с использованием истинно случайного или псевдослучайного генератора. Поэтому вероятность повторения двух гуидов невелика. Когда UUID необходимо сгенерировать на отдельных машинах или мы хотим сгенерировать безопасные UUID, используйте UUID4 (). Он также используется для генерации криптографически безопасных случайных чисел.

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