No Image

Принцип работы генератора чисел

СОДЕРЖАНИЕ
2 просмотров
11 марта 2020

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

Меня очень увлекают различные IT головоломки и задачки и генератор случайных чисел — одна из таких задачек. Обычно в своем телеграм канале я разбираю всякие головоломки и разные задачи с собеседований. Задача про генератор случайных чисел набрала большую популярность и мне захотелось увековечить ее в недрах одного из авторитетных источников информации — то бишь здесь, на Хабре.

Данный материал будет полезен всем тем фронтендерам и Node.js разработчикам, кто на острие технологий и хочет попасть в блокчейн проект/стартап, где вопросы про безопасность и криптографию, хотя бы на базовом уровне, спрашивают даже у фронтендеров.

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

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

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

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

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

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

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

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

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

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

Читайте также:  Генераторы для сварочных аппаратов

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

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

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

Мы получили генератор чисел от 0 до 9, но распределение очень неравномерное и каждый раз он будет генерировать одну и ту же последовательность.

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

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

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

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

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

Читайте также:  Смесительный узел для коллектора теплого пола

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

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

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

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

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

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

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

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

Чем это было чревато? Есть такой квест: alf.nu/ReturnTrue

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

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

Этот код работал в 70% случаев для Chrome

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

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

Читайте также:  Чем отмыть грязный линолеум на кухне

Принципы работы алгоритма

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

Что называют случайностью и как ее сгенерировать?

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

Если сформулировать более понятным языком, что следует сказать, что невозможно определить порядок или выявить зависимость между выпадающими цифрами в генераторе истинно случайных чисел. К примеру, первый бросок шестигранного игрального кубика дает шанс на выпадение цифры от 1 до 6 с абсолютно одинаковой вероятностью. Она равна 1/6 (около 16,67%). При любом последующем броске, будь то пятидесятый или тысячный, вероятность выпадения каждой цифры остается такой же.

Что называют псевдослучайностью?

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

Дата публикации: 12-02-2019

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

таких алгоритмов — море. Например, древний (и плохой) метод середины квадрата. Берут число, скажем 16 бит, возводят в квадрат, получают 32 бита, выбирают из него средние 16 -и так далее.

или стандартный конгруентный типа:
следующее = 3141592621*прошлое + 907633385;

Комментировать
2 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Строительство
0 комментариев
No Image Строительство
0 комментариев
No Image Строительство
0 комментариев
Adblock detector