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

Случайные числа

Я думаю понятие случайных чисел/величин вам знакомо: они случайны. Иногда в самодельном устройстве бывает нужна случайная величина, например для какой-нибудь игры или световых эффектов. Программный источник настоящих случайных чисел организовать весьма непросто, в отличие от аппаратного. Банально игральный кубик или лото-машина являются вполне себе хорошими источниками случайных чисел. Микроконтроллер к слову не может генерировать случайные числа, потому что он – точное вычислительное устройство, случайностей быть не может. Что делать? Использовать такое понятие, как псевдослучайные числа. Чем они отличаются от случайных? Своей природой. Псевдослучайное число получается путём различных математических действий с начальным числом, то есть имея начальное число, мы можем сгенерировать на его основе целую кучу других чисел. Но тут есть две проблемы:

  • Через какое-то количество чисел (тысяч, а может и миллиардов, а может и больше) ряд сгенерированных псевдослучайных чисел начнёт повторяться. Для наших целей это не так страшно, можно об этом не думать
  • Генератору псевдослучайных чисел нужно начальное случайное число. Вот это реально беда… Но ничего, у нашего микроконтроллера есть и аппаратные средства

Ардуино и случайные числа

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

  • random(max); – возвращает псевдослучайное число в диапазоне от 0 до ( max – 1 ). max принимает unsigned long , то есть от 0 до 4 294 967 295
  • random(min, max); – возвращает псевдослучайное число в диапазоне от min до ( max – 1 ). max принимает unsigned long , то есть от 0 до 4 294 967 295
  • randomSeed(value); – дать генератору псевдослучайных чисел новую опорную точку для отсчёта. value – любое число типа unsigned long , значит на Ардуино мы имеем 2^32 (4 294 967 295) наборов псевдослучайных чисел. На ваш век этого точно хватит!

Как правильно генерировать случайные числа, чтобы последовательность каждый раз была новая? Есть варианты:

  • При запуске программы задавать случайное число в randomSeed() . Как это сделать? Расскажу ниже
  • Если устройство как-то взаимодействует со внешним миром, или даже с пользователем, то можно при наступлении некоторых аппаратно случайных событий (нажатие кнопки, срабатывание датчика, принятие данных, и т.д.) скармливать randomSeed‘у текущее время с момента старта программы, т.е. функции millis() или micros() . Отличное решение кстати! Банально вызываем randomSeed(micros()) и всё.

Аппаратный рандом

Помните, в уроке про цифровые пины я говорил, что если пин никуда не подключен – то он ловит “из воздуха” всякие наводки. Шумы имеют природу, близкую к случайной, и было бы глупо этим не воспользоваться! Давайте посмотрим, какие значения можно получить с никуда не подключенного аналогового пина, опрашивая его обычным analogRead();

blank

Синусоида? Вполне логично, в стенах куча проводов с сетевым напряжением, вот они и наводят на микроконтроллер всякие помехи. Можно ли пользоваться сырым значением с аналогового пина в качестве “зерна” для randomSeed() ? Нужно! То есть при запуске устройства делать вот так:

Но есть ещё интересный вариант, который позволит получить гораздо более случайные числа для randomSeed() . Есть информация, что первые два бита из результата analogRead() имеют самый большой шум. Давайте на него посмотрим, выведя несколько (300) результатов в график. Получить первые два бита можно так: analogRead(A0) & 0b0000011 , или более коротко – analogRead(A0) & 3

blank

Выглядит весьма случайно, никакой закономерности не прослеживается! Но значения меняются всего от 0 до 3. Поэтому можно попробовать их перемножать и складывать, примерно так:

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

blank

График я построил в excel, чтобы более чётко видеть рассеивание полученного случайного значения Имеем практически равномерное рассеяние и огромное количество случайных значений, полученных путём перемножения и сложения “шума”. Пользуйтесь на здоровье.

Случайный bool

Иногда бывает нужен случайный флаг, то есть true / false . Делается это очень просто: в уроке про условия я рассказывал, что bool ( boolean ) принимает true при любом отличном от нуля значении. Это можно использовать для получения случайного true / false с заданной вероятностью! Просто присваиваем логической переменной результат функции random() , в которую передаём число, обратное вероятности получения false :

Переменная rndFlag получит значение false с вероятностью 1/5, то есть 20%. Если нужен true с низкой вероятностью – используем инверсию:

Теперь переменная rndFlag получит значение true с вероятностью 10%.

Видео

Что такое ГСЧ – как работает генератор случайных чисел

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

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

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

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

Истинный ГСЧ против псевдо ГСЧ

Есть два типа генераторов случайных чисел: истинные и псевдо.

  • Алгоритм истинного генератора случайных чисел создаётся с помощью аппаратного устройства, которое использует очень крошечные физические процессы для генерации случайных чисел. Так как алгоритм не написан; следовательно, истинный ГСЧ не может быть взломан для предсказания. Он обычно используется в системах, ориентированных на безопасность, по всему миру и в некоторых формах шифрования.
  • Алгоритм генератора псевдослучайных чисел используется в областях, где нет проблем с безопасностью, а случайность используется, чтобы избежать повторений и сделать что-то более интересное для конечного пользователя. Реализовать технологию дешевле и быстрее, поскольку она не требует оборудования и может быть легко встроена в программный код. Хотя этот процесс не является полностью случайным и определяется на основе алгоритма, он больше подходит для игр и программ.

Какие приложения используют ГСЧ

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

  • Азартные игры: бинго, карточные игры, лотереи и подобные игры.
  • Игры со сбором добычи: все игры, требующие от игроков сбора добычи для использования в игровом процессе, например, PubG, Diablo и Borderlands используют ГСЧ. Возможность получать лучшую добычу каждый раз – вот причина, по которой люди становятся зависимыми от них.
  • Приключенческие игры: такие игры, как Марио и Покемон Го используйте алгоритм генератора случайных чисел, чтобы определить, какие предметы будут добавлены, и каждый раз вы встречайтесь с новым претендентом на покемона.
  • Процедурно-сгенерированные игры: все игры, в которых нет предварительно разработанных карт и уровней, но которые были разработаны в игре с использованием процедурного программирования, таких как Minecraft и Civilization. Это помогает создать всю игру с использованием алгоритма.
  • Соревновательные игры: некоторые соревновательные игры, например, Counter-Strike используйте алгоритм генератора случайных чисел, чтобы регулировать, как пули поражают цели.

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

Манипуляции с ГСЧ

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

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

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

Почему геймеры ненавидят ГСЧ

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

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

Кто такой RNGesus?

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

Игроки, которые проигрывают, часто винят в своих поражениях злой ГСЧ, который выгоден их противникам. Там где зло, должен быть Бог – RNGesus.

Среди геймеров во всем мире появился новый термин, RNGesus, который больше соответствует игре слов с «Иисусом». Поскольку Иисус Христос считается нашим спасителем в реальном мире, RNGesus – это вообразимая сущность, созданная для спасения игроков от пагубных последствий ГСЧ. Это нигде не доказывается, но началось как миф, а теперь распространилось по игровому сообществу, как лесной пожар.

Окончательный вердикт по ГСЧ – хорошо или плохо?

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

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

Читайте также  Бензиновый генератор в бауцентре

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

K. Генератор случайных чисел

Криптография и случайность имеют тесную связь . В «F. Теория информации» , Теория информации , мы упоминали, что совершенная секретность может быть достигнута, если ключ алгоритма шифровки — действительно случайное число. Есть два подхода к получению длинного потока случайных битов.

  1. Использование естественного случайного процесса, такого как многоразовое бросание монеты и интерпретация результата «орел» или «решка», как значения битов 0 или 1 .
  2. Использование детерминированного процесса с информацией обратной связи.

Первый подход назван истинным генератором случайных чисел (TRNG — True Random Number Generator).

Второй назван псевдослучайным генератором числа (PRNG — Pseudorandom Number Generator) . Рисунок K.1 показывает эти два подхода.

K.1. Истинный генератор случайных чисел (TRNG)

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

K.2. Генератор псевдослучайных чисел (PRNG)

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

Конгруэнтные генераторы

Несколько методов используют некоторые конгруэнтные отношения.

Линейный конгруэнтный генератор

В информатике самая общая методика для того, чтобы производить псевдослучайные числа, — линейный конгруэнтный метод, введенный Лехмером (Lehmer). Рисунок K.2 показывает этот метод, который рекурсивно создает последовательность псевдослучайных чисел, используя линейное конгруэнтное уравнение xi+1 = (axi + b) mod n , где x называется начальным числом (seed) — это число между 0 и n — 1 .

Последовательность является периодической, где период зависит от того, как тщательно выбраны коэффициенты a и b . Идеально период должен быть такого размера, как модуль n .

Предположим a = 4 , b = 5 , n = 17 и xi0 = 7 . Последовательность — 16, 1, 9, 7, 16, 1, 9, 7.. ., которая есть явно неудовлетворительная псевдослучайная последовательность; её период — только 4 .

Критерии. Для приемлемого генератора псевдослучайных чисел ( PRNG ) в течение прошлых нескольких десятилетий были разработаны несколько критериев.

  1. Период должен быть равен n (модулю). Это означает, что прежде чем целые числа в последовательности начинают повторяться, должны быть сгенерированы все целые числа между 0 и n — 1 .
  2. Последовательность в каждый период должна быть случайна.
  3. Процесс генерации должен быть удобен для реализации на компьютере. Большинство компьютеров сегодня эффективно, когда применяется арифметика, использующая слова по 32 бита.

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

  1. Оптимальный выбор модуля, n , — это наибольшее простое число, близкое к размеру слова, используемого в компьютере. Рекомендуется использовать тридцать первое простое число Мерсенны как модуль: n = M 31 = 2 31 — 1 .
  2. Чтобы создавать период, равный значению модуля, значение первого коэффициента, a , должно быть первообразным корнем главного модуля. Хотя целое число 7 — первообразный корень M31 , рекомендуют использовать 7 k , где k — целое число, взаимно-простое с ( M31 — 1 ). Некоторые рекомендованные значения для k — это 5 и 13 . Это означает, что ( a = 7 5 ) или ( a = 7 13 ).
  3. Вторая рекомендация: для эффективного использования компьютера значение второго коэффициента b должно быть нулевым.

Линейный конгруэнтный генератор:

xi+1 = axi mod n , где n = 2 31 — 1 и a = 7 5 или a = 7 13

Безопасность. Последовательность, сгенерированная линейным конгруэнтным уравнением, показывает приемлемую случайность (если следовать предыдущим рекомендациям). Последовательность полезна в некоторых приложениях, где требуется только случайность (таких как моделирование); она бесполезна в криптографии, где желательны и случайность, и безопасность. Поскольку число n общедоступно, последовательность может быть атакована Евой с использованием одной из двух стратегий:

  • Если Ева знает значение начального числа ( x ) и коэффициент a , она может легко восстановить целую последовательность;
  • Если Ева не знает значение x и a , она может перехватить первые два целых числа и использовать следующие два уравнения, чтобы найти x и a :
Генератор квадратичных вычетов

Чтобы получить менее предсказуемую псевдослучайную последовательность, был введен генератор квадратичных вычетов (см. «A. ASCII» ), xi+1 = xi 2 mod n , где x называют начальным числом, — число между 0 и n -1 .

Генератор Blum Blum Shub

Простой, но эффективный метод создания генератора псевдослучайных чисел назван Blum Blum Shub (BBS) по имени его трех изобретателей.

BBS использует уравнение квадратичного вычета, но это — псевдослучайный генератор бит вместо генератора псевдослучайных чисел ; он генерирует последовательность битов ( 0 или 1 ).

Рисунок K.3 показывает идею этого генератора.

Ниже приведены шаги генерации:

  1. Найдите два больших простых числа p и q в форме 4k + 3 , где k — целое число ( p и q являются конгруэнтными 3 mod 4 ) .
  2. Выберите модуль n = p x q .
  3. Выберите случайное целое число r , которое является взаимно-простым с n .
  4. Вычислите начальное число как x = r 2 mod n .
  5. Генерировать последовательность xi+1 = xi 2 mod n.
  6. Взять самый младший бит сгенерированного случайного целого числа ( LSB — Least Significant Bit) как случайный бит.

Безопасность. Может быть доказано, что если p и q известны, i -тый бит в последовательности может быть найден как самый младший бит:

Это означает, что если Ева знает значение p и q , она может найти значение i -того бита, пробуя все возможные значения n (значение n обычно общедоступно). Тем самым сложность у этого генератора — та же самая, как у разложения на множители n. Если n является достаточно большим, последовательность безопасна (непредсказуема). Было доказано, что при очень большом n Ева не может предсказать значение следующего бита в последовательности, даже если она знает значения всех предыдущих битов. Вероятность каждого принятия значений для каждого бита, 0 или 1, — очень близка к 50 процентам.

Генераторы на основе криптографической системы

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

ANSI X9.17 генератор псевдослучайных чисел (PRNG)

ANSI X9.17 определяет криптографически сильный генератор псевдослучайных чисел , использующий тройной 3DES с двумя ключами (шифрация — дешифрация — шифрация), рисунок рис. K.4 иллюстрирует этот проект. Обратите внимание, что первое псевдослучайное число это 64-битовое начальное число, используемое как инициирующий вектор (IV); остальная часть псевдослучайных чисел использует начальное число, показанное как следующие IV. Тот же самый ключ засекречивания на 112 битов ( K1 и K2 в 3DES ) применяется для всех трех 3DES-шифров.

На рис. K.4 конфигурация — режим сцепления блоков шифрованного текста ( CBC ), который мы описали согласно рис. 8.3 в «Безопасность на сетевом уровне: IP SEC» . Режим X9.17 применяет два каскада формирования цепочки блока. Исходный текст для каждого каскада поступает от выхода первого 3DES, который использует дату и время как исходный текст на 64 бита. Зашифрованный текст, созданный вторым 3DES, — случайное число; зашифрованный текст, созданный третьим 3DES, — следующий инициирующий вектор IV для следующего случайного числа.

Строгость X9.17 определяется следующими фактами.

  1. Ключ — 112 (2 56) бит.
  2. Ввод даты и времени на 64 бита обеспечивает хорошую метку времени, предотвращающую атаку воспроизведения.
  3. Система обеспечивает превосходный эффект рассеивания и перемешивания с помощью шести шифрований и трех дешифрований.

PGP генератор псевдослучайных чисел (PRNG)

PGP (очень хорошая конфиденциальность) берет ту же самую идею, что и X9.17 с несколькими изменениями. Сначала PGP PRNG использует семь каскадов вместо двух. Второе: шифр является или IDEA, или CAST 128 (не рассмотренный в этой книге). Третье: ключ — обычно 128 битов. PGP PRNG создает три случайных числа на 4 бита: первое используется как инициирующий вектор IV секретности (для связи, работающей с PGP, но не для PRNG ), второй и третий конкатенируются, чтобы создать секретный ключ 128 битов (для связи, работающей PGP). Рисунок K.5 показывает эскиз PGP PRNG . Строгость PGP PRNG задана в размере его ключа и в том, что оригинал IV (начальное число) и ключ засекречивания на 128 битов могут быть сгенерированы от 24-байтовой истинно случайной переменной.

masterok

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

Вот вам история из 90-х:

Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com — новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.

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

Проблема в том, что секретные ключи, которые использовал Netscape, были недостаточно случайными. Их длина составляла всего 40 бит, что означает около триллиона возможных комбинаций. Это кажется большим числом, но хакерам удалось взломать эти коды, даже на компьютерах 1990-х годов, примерно за 30 часов. Якобы случайное число, которое Netscape использовал для генерации секретного ключа, базировалось всего на трёх значениях: времени суток, идентификационном номере процесса и идентификационном номере материнского процесса — все они являются предсказуемыми. Из-за этого злоумышленник имел возможность сократить количество вариантов для перебора и найти нужный ключ гораздо раньше, чем предполагали в Netscape.

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

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

Читайте также  Бензиновый генератор navigator npg7000

И вот группа ученых из МГУ разработала и сконструировала компактный высокоскоростной квантовый генератор истинно случайных чисел.

«Развитие современных квантовых технологий открыло новые перспективы для создания систем защищенной связи. Наиболее яркий пример — квантовая криптография. Для распределения секретных ключей в системах квантовой криптографии требуется большое количество случайных последовательностей 0 и 1. Для этих целей используются квантовые генераторы случайных чисел», — поясняет Сергей Кулик, доктор физико-математических наук, профессор кафедры квантовой электроники физического факультета МГУ.

Учёные МГУ разработали и сконструировали такой генератор, последовательности чисел которых можно считать истинно случайными. Дело в том, что в основе действия новой разработки лежат законы релятивистской, а не классической физики. Исследователям удалось оптимально выбрать и сгруппировать фотоотсчёты для исходной последовательности и добиться скорости генерации случайной последовательности скоростью в 64 Мбит/с, 75 Мбит/с и 100 Мбит/с. Сгенерированные последовательности успешно прошли статистические тесты NIST на случайность.

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

Случайные числа широко используются в различных областях науки и техники, например, при вычислении многомерных интегралов, моделировании различных процессов методом Монте-Карло. Наиболее широкое применение случайные числа находят в криптографии. Случайные последовательности используются для секретных ключей в системах симметричного шифрования, генерации паролей, PIN кодов для различных типов пластиковых карт, кодов аутентификации, вероятностных алгоритмов и систем квантового распределения ключей. Практически для всех упомянутых применений требуются случайные числа, полученные исключительно с физических генераторов.

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

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

Реализует несколько типов генераторов псевдослучайных чисел.

Модуль random предоставляет быстрый генератор псевдослучайных чисел на основе алгоритма Mersenne Twister . Первоначально разработанный для создания входных данных для моделирования методом Монте-Карло, Mersenne Twister генерирует числа с почти равномерным распределением и большим периодом, что делает его пригодным для широкого круга приложений.

Генерация случайных чисел

Функция random () возвращает следующее случайное значение с плавающей запятой из сгенерированной последовательности. Все возвращаемые значения попадают в диапазон 0 n <1.0 .

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

Чтобы сгенерировать числа в определенном числовом диапазоне, используйте вместо этого uniform () .

Передайте минимальное и максимальное значения, и uniform () настроит возвращаемые значения из random () , используя формулу min + (max — min) * random () .

Посев

random () выдает разные значения каждый раз при вызове и имеет очень большой период перед повторением любых чисел. Это полезно для получения уникальных значений или вариаций, но иногда бывает полезно иметь один и тот же набор данных, который можно обрабатывать разными способами. Один из способов – использовать программу для генерации случайных значений и сохранения их для обработки на отдельном этапе. Однако это может оказаться непрактичным для больших объемов данных, поэтому random включает функцию seed () для инициализации генератора псевдослучайных чисел, чтобы он генерировал ожидаемый набор значений.

Начальное значение управляет первым значением, созданным формулой, используемой для создания псевдослучайных чисел, и, поскольку формула является детерминированной, она также устанавливает полную последовательность, полученную после изменения начального числа. Аргументом для seed () может быть любой хешируемый объект. По умолчанию используется зависящий от платформы источник случайности, если он доступен. В противном случае используется текущее время.

Состояние сохранения

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

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

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

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

Аргументы для randint () – это концы включающего диапазона значений. Числа могут быть положительными или отрицательными, но первое значение должно быть меньше второго.

randrange () – это более общая форма выбора значений из диапазона.

randrange () поддерживает аргумент step в дополнение к значениям start и stop, поэтому он полностью эквивалентен выбору случайного значения из диапазона (start, stop, шаг) . Это более эффективно, потому что диапазон фактически не строится.

Выбор случайных предметов

Генераторы случайных чисел часто используют для выбора случайного элемента из последовательности пронумерованных значений, даже если эти значения не являются числами. random включает функцию choice () для выполнения случайного выбора из последовательности. В этом примере имитируется подбрасывание монеты 10 000 раз, чтобы подсчитать, сколько раз выпадает орел, а сколько решка.

Допускаются только два результата, поэтому вместо использования чисел и их преобразования в choice () используются слова «орла» и «решка». Результаты заносятся в таблицу с использованием имен результатов в качестве ключей.

Перестановки

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

Карты представлены в виде строк с номиналом и буквой, обозначающей масть. Сданные «руки» создаются путем добавления по одной карте в каждый из четырех списков и удаления ее из колоды, чтобы ее нельзя было раздать снова.

Отбор проб

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

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

Несколько одновременных генераторов

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

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

SystemRandom

Некоторые операционные системы предоставляют генератор случайных чисел, который имеет доступ к большему количеству источников энтропии, которые могут быть введены в генератор. random предоставляет эту функцию через класс SystemRandom , который имеет тот же API, что и Random , но использует os.urandom () для генерации значений, которые составляют основу всех других алгоритмов.

Последовательности, созданные SystemRandom , не воспроизводятся, поскольку случайность исходит от системы, а не от состояния программного обеспечения (фактически, seed () и setstate () не имеют никакого эффекта).

Неравномерные распределения

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

Нормальный

нормальное распределение обычно используется для неоднородных непрерывных значений, таких как классы, высота, веса и т. Д. Кривая, полученная с помощью распределения, имеет характерную форму, которая привела к тому, что ее называют “колоколообразной кривой”. ” random включает две функции для генерации значений с нормальным распределением, normalvariate () и немного более быструю gauss () (нормальное распределение также называется распределение Гаусса).

Связанная функция lognormvariate () создает псевдослучайные значения, в которых логарифм значений распределяется нормально. Логнормальные распределения полезны для значений, которые являются продуктом нескольких случайных величин, которые не взаимодействуют.

Приближение

треугольное распределение используется как приблизительное распределение для небольших выборок. «Кривая» треугольного распределения имеет низкие точки при известных минимальных и максимальных значениях и максимальную точку в режиме, который оценивается на основе «наиболее вероятного» результата (отраженного аргументом режима в triangular () ).

Экспоненциальный

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

Распределение Парето, или степенной закон, соответствует многим наблюдаемым явлениям и было популяризировано изданием Длинный хвост Криса Андерсона. Функция paretovariate () полезна для моделирования распределения ресурсов между людьми (богатство людям, спрос на музыкантов, внимание к блогам и т. Д.).

Угловой

Распределение фон Мизеса, или круговое нормальное распределение (создается с помощью vonmisesvariate () ), используется для вычисления вероятностей циклических значений, таких как углы, календарные дни и время.

Размеры

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

Гамма-распределение, создаваемое gammavariate () , используется для моделирования размеров таких вещей, как время ожидания, количество осадков и вычислительные ошибки.

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

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

Пожалуйста, приостановите работу AdBlock на этом сайте.

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

Пример: Определение победителя в конкурсе репостов.

Имеется список из 53 человек. Необходимо выбрать из них победителя. Если вы выберете его самостоятельно, то вас могут обвинить в предвзятости. Поэтому вы решили написать программу. Она будет работать следующим образом. Вы вводите количество участников N , после чего программа выводит одно число – номер победителя.

Как получить число от игрока, вам уже известно. А вот как заставить компьютер загадать случайное число? В этом уроке вы этому научитесь.

Функция rand().

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

Функция rand() определена в заголовочном файле stdlib.h . Поэтому, если хотите использовать rand в своей программе, не забудьте подключить этот заголовочный файл. Константа RAND_MAX тоже определена в этом файле. Вы можете найти этот файл у себя на компьютере и посмотреть её значение.

Читайте также  Бен 10 генератор рекс по русски

Давайте посмотрим на эту функцию в действии. Запустим следующий код:

Должно получиться что-то вроде этого.

Рис.1 Пять случайных чисел, сгенерированных функцийе rand

Но нам бы хотелось получить числа от 1 до 53 , а не всё подряд. Ниже описано несколько трюков, позволяющих наложить ограничения на функцию rand() .

Ограничить случайные числа сверху.

Кто в школе ждал момента, когда ему пригодится математика, приготовьтесь. Этот момент наступил. Чтобы ограничить сверху случайные числа, можно воспользоваться операцией получения остатка от деления, которую вы изучили в прошлом уроке. Наверное вы знаете, что остаток от деления на числа K всегда меньше числа K . Например, при делении на 4 могут получиться остатки 0, 1, 2 и 3 . Поэтому если вы хотите ограничить сверху случайные числа числом K , то просто возьмите остаток от деления на K . Вот так:

Пять случайных чисел меньше 100

Рис.2 Пять случайных чисел меньше 100

Ограничить числа снизу.

Функция rand возвращает случайные числа из отрезка [0, RAND_MAX] . А что если нам нужны только числа большие числа M (например, 1000 )? Как быть? Всё просто. Просто прибавим к тому, что вернула функция rand, наше значение M . Тогда если функция вернёт 0 , итоговый ответ будет M , если 2394 , то итоговый ответ будет M + 2394 . Этим действием мы как бы сдвигаем все числа на M единиц вперёд.

Задать границы функции rand сверху и снизу.

Например, получить числа от 80 до 100 . Кажется, нужно просто объединить два способа, которые приведены выше. Получим что-то вроде этого:

Попробуйте запустить эту программу. Удивлены?

Да, такой способ работать не будет. Давайте прокрутим эту программу руками, чтобы убедиться в том, что мы допустили ошибку. Допустим rand() вернула число 143 . Остаток от деления на 100 равен 43 . Дальше 80 + 43 = 123 . Значит такой способ не работает. Подобная конструкция выдаст числа от 80 до 179 .

Давайте разберём по действиям наше выражение. rand()%100 может выдать числа от 0 до 99 включительно. Т.е. из отрезка [0; 99] .
Операция + 80 сдвигает наш отрезок на 80 единиц вправо. Получаем [80; 179] .
Как видим, проблема у нас заключается в правой границе отрезка, она сдвинута вправо на 79 единиц. Это наше исходное число 80 минус 1 . Давайте наведём порядок и сдвинем правую границу назад: 80 + rand()%(100 — 80 + 1) . Тогда всё должно сработать как надо.

В общем случае если нам нужно получить числа из отрезка [A;B] , то необходимо воспользоваться следующей конструкцией:
A + rand()%(B-A+1) .

Согласно этой формуле перепишем нашу последнюю программу:

Случайные числа из диапазона [80;100]

Рис.3 Случайные числа из диапазона [80;100]

Ну вот, теперь вы можете решить исходную задачу урока. Сгенерировать число из отрезка [1; N] . Или не можете?

Но прежде ещё немного полезной информации. Запустите последнюю программу три раза подряд и записывайте себе случайные числа, которые она генерирует. Заметили?

Функция srand().

Да, каждый раз появляются одни и те же одинаковые числа. «Так себе генератор!» – скажете вы. И будете не совсем правы. Действительно, генерируются всё время одинаковые числа. Но мы можем на это повлиять, для этого используется функция srand() , которая также определена в заголовочном файле stdlib.h . Она инициализирует генератор случайных чисел начальным числом.

Скомпилируйте и запустите несколько раз вот эту программу:

Теперь поменяйте аргумент функции srand() на другое число (надеюсь вы ещё не забыли, что такое аргумент функции?) и снова скомпилируйте и запустите программу. Последовательность чисел должна измениться. Как только мы меняем аргумент в функции srand – меняется и последовательность. Не очень практично, не правда ли? Чтобы изменить последовательность, нужно перекомпилировать программу. Вот бы это число туда подставлялось автоматически.

И это можно сделать. Например, воспользуемся функцией time() , которая определена в заголовочном файле time.h . Данная функция, если ей в качестве аргумента передать NULL , возвращает количество секунд, прошедших c 1 января 1970 года . Вот посмотрите, как это делается.

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

Практика

Решите предложенные задачи. Для удобства работы сразу переходите в полноэкранный режим

Исследовательские задачи для хакеров:

  1. В каких ситуациях ещё может пригодиться генерация случайных чисел? Напишите ваши варианты в комментарии к этому уроку.
  2. Напишите программу, которая выводит на экран значение целочисленной константы RAND_MAX. Найдите файл stdlib.h на вашем компьютере, найдите значение этой константы в этом файле.
  3. Найдите в интернете описание функций, которые определены в заголовочном файле time.h Вы, конечно, ещё не сможете ими пользоваться, но знать, что такие функции есть, всё равно нужно. Ведь когда-то настанет момент, когда ваших знаний будет достаточно для их использования.
  4. Числа, генерируемые функцией rand(), имеют равномерное распределение. Это значит, что если запускать функцию rand очень много раз и каждый раз записывать, какое число выпало, то количество выпадения различных чисел будет одинаковым. Например, если генерировать только числа 0 и 1, то через 100 запусков примерно 50 раз выпадет ноль и 50 раз единичка. Обратите внимание, что я говорю примерно. Может быть, например, 49 и 51, или 53 и 47. Если рассматривать это в отношении к общему числу запусков, получим (49/100 и 51/100 или 53/100 и 47/100 соответственно). Но чем больше экспериментов мы проведём, тем ближе отношение количество единичек к количеству испытаний будет стремиться к 1/2. Проведите самостоятельно эксперимент с 10, 50 и 100 запусками. Это муторно и долго, если делать руками, но что поделать? В будущем мы напишем программу, чтобы проверить свойство равномерности распределения наших случайных чисел.

Дополнительные материалы

    определённые в заголовочном файле stdlib.h
  1. Хотя я и употребляю везде словосочетание «случайные числа», но на самом деле получить действительно случайные числа – сложная задача. И в компьютерах обычно используются псевдослучайные числа. Подробнее об этом можно прочитать здесь.
  2. Если не терпится узнать хоть что-то про NULL, то почитайте вот этот урок.
  3. Дата 1 января 1970 года особенная. С неё начинается отсчёт эры UNIX. Подробнее об этом и проблемах, которые нас ожидают.

Оставить комментарий

Чтобы код красиво отображался на странице заключайте его в теги [code] здесь писать код [/code]

Комментарии

1 задача. Например, используя генератор случайных чисел можно сделать игральный кубик или подобие игрового автомата.
4 задача. Я постарался сделать, но на 30 остановился. У меня получились следующие результаты:
10 генераций: 0-2, 1-8
20 генераций: 0-12, 1-8
30 генераций: 0-15, 1-15

Т.е. 30 попыток достаточно?

1 задача. Да! Очень хорошие примеры.

4 задача. Нет, 30 попыток недостаточно. То, что у вас получилось 15/15 это совпадение. Я провёл 5 опытов по 30 раз, вот результаты:
1. 15/15
2. 11/19
3. 15/15
4. 17/13
5. 12/18

Здравствуйте! Мой комментарий по поводу формулы расчета диапазона случайных чисел, мы тут посовещались и признали ее не совсем верной. Ваща формула: A + rand()%(B-A+1), при условии которое дано в задаче Введите максимально число, которое может быть сгенерировано следующей конструкцией: int rand_a = 66 + rand()%601; выдает максимальное число в 536. Верная формула: max (a + rand() %b) = a + b — 1 = 666

Человек который мне помогает изучать язык Си, написал тест, для сравнения Вашей формулы, которая дается на сайте и верной формулы.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void sleep (float);
void print_symbol (int);

int main (void)
<
// A + rand()%(B-A+1)
// 66+rand()%601
// 600-66+1 = 535, а правильный ответ оказался 666
int a, b;
a = 66;
b = 601;

printf("a = %dn", a);
printf("b = %dnn", b);
printf(" 33[32;22m");
printf("верная формула: 33[0mn");
printf("max (a + rand() %%b) = a + b — 1 = %dnn", a+b-1);
printf(" 33[33;22m");
printf("а вот ваша формула: 33[0mn");
printf("max (a + rand() %%b)");
printf(" = b — a + 1 = %dnn", b-a+1);

int i, z, max = 0;
int s = 0, count = 0;
for (i=0; i<1000000; i++)
<
z = a + rand() %b;
if (z>max)max = z;
if (++count > 2000)
<
count = 0;
if (++s > 3) s = 0;
print_symbol(s); // строку на экран
fflush (stdout); // обновляем вывод
sleep (0.03); // временная задержка
>
>
printf("nnmax = %dn", max); //max = a+b-1
exit(0);
>
//————————————————

Подождите-подождите. Почему вы за A и B берёте значения 66 и 601. А и B это начало и конец промежутка из которого вы хотите генерировать числа же.

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

Всё-таки вы не правы.
Ищем нижнюю и верхнюю границы диапазона.

1 способ.
rand()%601 может сгенерировать любое число от 0 до 600. Максимально 600. К нему прибавляется 66. Итого получается 666.

2 способ.
Используем формулу из урока:
A + rand()%(B-A+1)

В задаче имеем
66 + rand()%601

Сопоставим их
A = 66
B-A+1 =601

Подставим вместо А значение 66. Получим
B — 66 +1 = 601

Отсюда B = 601-1+66 = 666. Итого верхняя граница диапазона 666.

У вас ошибка. Вы почему-то считаете, что B = 601. Хотя B вам надо найти. Разберите внимательно 2 способ.

И все таки мы с вами не согласны:)
У нас с вами получается разный подход к вопросу у вас со стороны математики, у нас со стороны информатики.

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

В общем случае команда выглядит так:

где
a — получившееся случайное число;
b — минимальное значение диапазона случайных чисел;
n — смещение для команды rand();

т.е. сначала выполняется rand() %n, а затем полученный результат
прибавляется к b, и получившаяся сумма записывается в a.

Каким образом работает rand() ?

Она всегда генерирует число, начиная с 0 с заданным смещением, при
этом число 0 тоже учитывается в смещении.

Допустим у нас задано смещение 1:

смещение: 1
число num: 0

т.е. команда a = rand() %1;

всегда будет давать результат 0

Допустим, у нас задано другое смещение 5:

смещение: 1 2 3 4 5
число num: 0 1 2 3 4

т.е. команда a = rand() %5;

будет генерировать число >= 0 и <=4.

Т.е. из-за этой особенности максимальное число, которое генерирует
rand(), всегда на 1 меньше, чем заданное смещение.

Если смещение 25, максимальный результат всегда 24.
Если смещение 100, максимальный результат всегда 99.

И как теперь посчитать максимум?

И если b = 66 и n = 601, максимум всегда будет:
66 + (601 — 1) = 66 + 600 = 666.

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

(смещение) n: 1 2 3 4 5 6 7 8 9

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

По-моему мы говорим об одном и том же, но только разными словами. Я не призываю заучивать формулы для отрезка, я призываю разобраться в том, как это работает, используя для примера конкретную задачу.) В любом случае спасибо за неравнодушие и дискуссию!

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: