Srand инициализация случайной величины


Содержание

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

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

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

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

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

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

Функция rand().

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

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

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

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

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

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

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

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

Рис.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) .

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

Рис.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 :

Если необходимо сгенерировать последовательность в диапазоне [M1; M2], то используется формула:

Number = rand()%(M2-M1+1) + M1;

где Number – генерируемое число. M2-M1+1 – полный диапазон представления чисел. M1 – смещение указанного диапазона относительно 0; % — остаток от деления.

Например, если требуется сгенерировать последовательность в диапазоне [-10;10], то вызов функции будет выглядеть как

В результате получения остатка от деления на 21 имеем число от 0 до 20. Вычитая из полученного числа 10, получим число в искомом диапазоне [-10;10].

Однако генерируемая функцией rand() последовательность будет иметь один и тот же вид при каждом запуске программы.

Для генерации различных последовательности при каждом запуске программы необходимо проинициализировать глобальную переменную next значением, отличным от 1. С этой целью используется функция
void srand( unsigned int seed)
< next = seed; >
Чтобы инициализация next при каждом запуске программы была различной в качестве аргумента seed чаще всего используется текущее время.

Пример Заполнить массив из 20 элементов случайными числами в диапазоне от 0 до 99.

Илон Маск рекомендует:  Что такое код asp logextfilecookie

Алгоритм перемешивания

Часто возникает задача расставить уже имеющийся набор значений в произвольном порядке. С этой целью также используется генератор псевдослучайных чисел. При этом создается массив и заполняется значениями.
Сама процедура перемешивания происходит следующим образом. Генерируется два значения индексов массива случайным образом, и значения элементов с полученными индексами меняются местами. Процедура повторяется не менее N раз, где N — количество элементов массива.
В качестве примера рассмотрим перемешивание 20 значений (от 1 до 20) и повторим процедуру 20 раз.

Реализация на Си

Алгоритм произвольного выбора

Часто возникает задача произвольного выбора ранее заданных элементов массива. Причем необходимо предусмотреть отсутствие повторений в выборе этих элементов.
Алгоритм такого выбора состоит в следующем:

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

Реализации на Си
В результате получаем новый массив b , сформированный произвольной выборкой элементов массива a .

#include
#include
#include
#define SIZE 20
int main() <
int a[SIZE];
int b[SIZE]; // результирующий массив
srand(time( NULL ));
// Заполняем массив последовательными значениями от 1 до 20
for ( int i = 0; i «%2d » , a[i]);
>

for ( int i = 0; i int ind = rand() % 20; // выбираем произвольный индекс
while (a[ind] == -1) // пока элемент «выбран»
<
ind++; // двигаемся вправо
ind %= 20; // если дошли до правой границы, возвращаемся в начало
>
b[i] = a[ind]; // записываем следующий элемент массива b
a[ind] = -1; // отмечаем элемент массива a как «выбранный»
>
printf( «\n» );
// Выводим получившийся массив
for ( int i = 0; i «%2d » , b[i]);
getchar();
return 0;
>

IT Памятка

Чтобы не забыть и впоследствии освежить память

Генерация случайного числа в С++

Генерация случайного числа

Для генерации случайных чисел используется стандартная функция, которая генерирует случайные числа в С — rand() ;

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

Для получения любого диапазона случайных чисел A до B, можно использовать вот такой код

Инициализация генератора псевдослучайных чисел

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

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

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

mt_srand — Переинициализирует генератор случайных чисел mt

(PHP 4, PHP 5, PHP 7)

mt_srand — Переинициализирует генератор случайных чисел mt

Описание

Переинициализирует генератор случайных чисел параметром seed или случайным числом, если seed не указан.

Замечание: Начиная с PHP 4.2.0, больше нет необходимости инициализировать генератор случайных чисел функциями srand() или mt_srand() , поскольку теперь это происходит автоматически.


Список параметров

Необязательное значение параметра переинициализации

Возвращаемые значения

Эта функция не возвращает значения после выполнения.

Список изменений

Версия Описание
5.2.1 Реализация Mersenne Twister в PHP теперь использует новый алгоритм переинициализации, разработанный Richard Wagner. При том же параметре последовательность значений будет отличатся от последовательности, сгенерированной в предыдущих версиях PHP. (Ранее при одинаковых параметрах последовательность была одинаковой). Это поведение более не планируется изменять, но тем не менее, полагаться на это небезопасно.

Примеры

Пример #1 Пример использования mt_srand()

Смотрите также

  • mt_rand() — Генерирует случайное значение методом mt
  • mt_getrandmax() — Показывает максимально возможное значение случайного числа
  • srand() — Изменяет начальное число генератора псевдослучайных чисел

C++: Инициализация srand?

Как лучше всего инициализировать srand в С++?

Я всегда использовал srand( time(NULL) ), но этот метод не работает когда программа запускается много раз в одну и ту же секунду.

Для примера, если взять такую программу

и запустить скрипт

можно увидеть что почти все значения одинаковые.

Как лучше всего генерировать случайные числа в С++ если программа запускается 40-50 раз в секунду?

  • Вопрос задан более трёх лет назад
  • 11282 просмотра

Еще варианты:
1. На Linux можно считать первые четыре байта из /dev/urandom
2. На x86/x64 можно воспользоваться командой ‘rdtsc’ — возвращает количество тактов процессора с старта системы. Код для GCC:

Так и делаю, когда пишу генераторы тестов к задачам для стресс-тестирования.

Srand инициализация случайной величины

  • srand(…) вызывается для того, чтобы при каждом новом запуске программы значения генерировались разными.

Новички часто забывают написать srand(time(0)) , а потом ломают голову, отчего числа получаются одинаковыми.
srand(…) можно использовать и для генерации одних и тех же значений многократно.

time (0) — это функция, отдающая системное время, представленное в секундах, прошедшее с 1 января 1970 года.

  • srand(…) называют функцией-семенем для rand().
  • Сначала нужно инициализировать rand(). Говорят, что нужно засеять rand() семенем. Делается это с помощью srand(…).
  • Начало последовательности чисел определяется значением, уходящим в srand(…). Если в srand(…) уходят разные значения, последовательность чисел получается разной, при неизменном значении последовательность будет одинаковой.


  • Динамически изменяющиеся значения подбираются из системного времени, они как раз и используются для случайности значений на каждый новый запуск программы: srand(time(0));
  • Диапазон выпадающих значений определяется с помощью операции взятия остатка: % .
  • Сдвиг диапазонов выпадающих значений определяется сложением или вычитанием + или — .
  • Свойствами настоящей уникализации rand() не обладает.
  • rand() ограничивается значением RAND_MAX.

12 комментариев: Генератор случайных значений

(инклуды тут обрезаются)

ну, я когда сомневался что инициализация сбрасывалась, делал так:

Автор сайта отвечает :
чтобы код отобразился верно, нужно его написать между тегами
[ php]Исходный код[/php ]

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

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

В вашем примере «А вот так делал я. Только положительные шестизначные числа» числа не настолько рандомны, как нужно — у всех на конце по два нуля от умножения в коде на 100. Код, например, генерировать , пока рандомное число не станет ХХХХ10, будет генерировать бесконечно �� Может быть, ваше число «double а» умножать не на 100, а на рандомное b, которое b>=100. ?

Автор сайта отвечает :
Можно просто генерировать еще одно число в диапазоне 0-99 и прибавлять это число к моему и следить, чтоб число не превысило нужное
Это моя ошибка , но как-то внимания не обратил. Давно очень описывал эту тему.

как заполнить массив рандомными символами?

Использую библиотеку , и все что написанно тут перепробовал, но вот что меня смущает, рандомностью тут чето и не пахнет, если запускать (srand(time(o)); cout Автор сайта отвечает :
Это генератор псевдослучайных чисел. Слово “псевдо” обозначает, что они случайными не являются, так уж устроена функция rand(), она зависит от времени. Настоящие генераторы случайных чисел появляются с С++11, но даже там имеется зависимость от оборудования. #include

Но то, что Вы написали, где написали, что число слегка нарастает и потом всё сначала — это чушь.
Вот небольшой (и неэффективный) пример, который генерирует убывающие последовательности. Будет работать с компиляторов, поддерживающих С++11

Здесь просто показано, что Ваше изречение на самом деле чушь, и rand() генерирует разные числа, вплоть до обратносказанного.

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

Автор сайта отвечает :
Не пригодится, есть готовые решения. Ваш генератор такой же генератор случайных чисел каким он и был, когда было просто rand(), только Вы усложнили всё.

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

Автор сайта отвечает :
Я не понял вопрос. Я не понял зачем изобретать свой random.

Ну изобретать что то свое это только +(пускай что то похожее уже есть), развивает мышление и находчивость. А числовой диапазон… рассмотрим тип long double, он имеет 38 значений после запятой(если мне не изменяет память) из них только около 12 предел точности(если мне не изменяет память), соответственно в нашем распоряжении 26 значное число, сомневаюсь что кому то нужен рандом превышающий данный диапазон. Отсюда следует что можно указывать свой диапазон в рамках данного диапазона. И вуаля, мы получим самый рандомный рандом а не все те псевдорандомы что нам прелогают.

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

Начиная с С++11 идёт не генератор псевдослучайных чисел чисел, хотя и становится генератором псевдослучайных при определённом стечении обстоятельств (каких именно сказать не могу).

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

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

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

На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора. Основная цель — получить feedback и поделиться знаниями.


Введение

Генераторы случайных чисел — ключевая часть веб-безопасности. Небольшой список применений:

  • Генераторы сессий(PHPSESSID)
  • Генерация текста для капчи
  • Шифрование
  • Генерация соли для хранения паролей в необратимом виде
  • Генератор паролей
  • Порядок раздачи карт в интернет казино

Как отличить случайную последовательность чисел от неслучайной?

Пусть есть последовательность чисел: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 . Является ли она случайной? Есть строгое определение для случайной величины. Случайная величина — это величина, которая принимает в результате опыта одно из множества значений, причём появление того или иного значения этой величины до её измерения нельзя точно предсказать. Но оно не помогает ответить на наш вопрос, так как нам не хватает информации для ответа. Теперь скажем, что данные числа получились набором одной из верхних строк клавиатуры. «Конечно не случайная» — воскликните Вы и тут же назовете следующие число и будете абсолютно правы. Последовательность будет случайной только если между символами, нету зависимости. Например, если бы данные символы появились в результате вытягивания бочонков в лото, то последовательность была бы случайной.

Чуть более сложный пример или число Пи

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

Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)

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

Уязвимости ГПСЧ

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

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

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

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

Для выбора коэффициентов имеются свойства позволяющие максимизировать длину периода(максимальная длина равна m), то есть момент, с которого генератор зациклится [1].

Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений

Решив эту систему, можно определить коэффициенты a, c, m. Как утверждает википедия [8], эта система имеет решение, но решить самостоятельно или найти решение не получилось. Буду очень признателен за любую помощь в этом направлении.

Предсказание результатов линейно-конгруэнтного метода

Основным алгоритмом предсказания чисел для линейно-конгруэнтного метода является Plumstead’s — алгоритм, реализацию, которого можно найти здесь [4](есть онлайн запуск) и здесь [5]. Описание алгоритма можно найти в [9].
Простая реализация конгруэнтного метода на Java.

Отправив 20 чисел на сайт [4], можно с большой вероятностью получить следующие. Чем больше чисел, тем больше вероятность.

Взлом встроенного генератора случайных чисел в Java

Многие языки программирования, например C(rand), C++(rand) и Java используют LСPRNG. Рассмотрим, как можно провести взлом на примере java.utils.Random. Зайдя в исходный код(jdk1.7) данного класса можно увидеть используемые константы

Метод java.utils.Randon.nextInt() выглядит следующим образом (здесь bits == 32)

Результатом является nextseed сдвинутый вправо на 48-32=16 бит. Данный метод называется truncated-bits, особенно неприятен при black-box, приходится добавлять ещё один цикл в brute-force. Взлом будет происходить методом грубой силы(brute-force).

Пусть мы знаем два подряд сгенерированных числа x1 и x2. Тогда необходимо перебрать 2^16 = 65536 вариантов oldseed и применять к x1 формулу:

до тех пор, пока она не станет равной x2. Код для brute-force может выглядеть так

Вывод данной программы будет примерно таким:

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

И теперь в исходном коде заменим
crackingSeed.set(seed);
на
crackingSeed.set(getPreviousSeed(seed));

И всё, мы успешно взломали ГПСЧ в Java.

Взлом ГПСЧ Mersenne twister в PHP

Рассмотрим ещё один не криптостойкий алгоритм генерации псевдослучайных чисел Mersenne Twister. Основные преимущества алгоритма — это скорость генерации и огромный период 2^19937 − 1, На этот раз будем анализировать реализацию алгоритма mt_srand() и mt_rand() в исходном коде php версии 5.4.6.

Можно заметить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)). В бинарном представление операция выглядит так:

10110111010111100111111001110010 s1
00000000000000000010110111010111100111111001110010 s1 >> 18
10110111010111100101001110100101 s1 ^ (s1 >> 18)
Видно, что первые 18 бит (выделены жирным) остались без изменений.
Напишем две функции для инвертирования битового сдвига и xor

Тогда код для инвертирования последних строк функции php_mt_rand() будет выглядеть так

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

Область для взлома


Если вы думаете, что уже нечего ломать, то Вы глубоко заблуждаетесь. Одним из интересных направлений является генератор случайных чисел Adobe Flash(Action Script 3.0). Его особенностью является закрытость исходного кода и отсутствие задания seed’а. Основной интерес к нему, это использование во многих онлайн-казино и онлайн-покере.
Есть много последовательностей чисел, начиная от курса доллара и заканчивая количеством времени проведенным в пробке каждый день. И найти закономерность в таких данных очень не простая задача.

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

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

Треугольное распределение

Приведем пример генерации случайной величины с треугольным распределением [7] на языке C99.

В данном случае мы берем случайную величину rand() и задаем ей распределение, исходя из функции треугольного распределения. Для параметров a = -40, b = 100, c = 50 график 10000000 измерений будет выглядеть так

Экспоненциальное распределение

Пусть требуется получить датчик экспоненциально распределенных случайных величин. В этом случае F(x) = 1 – exp(-lambda * x). Тогда из решения уравнения y = 1 – exp(-lambda * x) получаем x = -log(1-y)/lambda.
Можно заметить, что выражение под знаком логарифма в последней формуле имеет равномерное распределение на отрезке [0,1), что позволяет получать другую, но так же распределённую последовательность по формуле: x = -log(y)/lambda, где y есть случайная величина(rand()).

Тесты ГПСЧ

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

Одним из известных тестов является тест на следующий бит — тест, служащий для проверки генераторов псевдослучайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью большей ½.

В теории криптографии отдельной проблемой является определение того, насколько последовательность чисел или бит, сгенерированных генератором, является случайной. Как правило, для этой цели используются различные статистические тесты, такие как DIEHARD или NIST. Эндрю Яо в 1982 году доказал, что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
В интернете [10] можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.

Псевдослучайные числа

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

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

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

Задание
Напишите программу, в которой целочисленной переменной присваивается результат выполнения функции rand() . Выведите значение переменной на экран.

Функция rand() возвращает целое число от 0 до значения присвоенного константе RAND_MAX. Значение RAND_MAX зависит от системы и определено в заголовочном файле stdlib.h. Так, например, оно может быть равно 32767 (двухбайтовое целое) или 2147483647 (четырехбайтовое целое).

Задание
Определите значение RAND_MAX в вашей системе. Для этого не забудьте подключить к файлу исходного кода заголовочный файл stdlib.h.

Код ниже выводит на экран 50 случайных чисел:

В теле цикла осуществляется переход на новую строку после каждых выведенных на экран пяти чисел. Для этого используется выражение, в котором находится остаток от деления i на 5, результат сравнивается с 0. Чтобы после первого числа не происходил переход на новую строку, iсначала присваивается единица, а не ноль (т.к. 0 делится на 5 без остатка).

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

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

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

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

Текущее время можно узнать с помощью функции time() , прототип которой описан в файле time.h. Передав time() в качестве параметра NULL, мы получим целое число, которое можно передать в srand() :
srand(time(NULL));

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

Получение целых случайных чисел в заданных диапазонах

Функция rand() выдает случайное число от 0 до значения RAND_MAX. Что делать, если требуется получать случайные числа в иных диапазонах, например, от 100 до 999?

Сначала рассмотрим более простую ситуацию: получить случайные числа от 0 до 5. Если любое целое число попытаться разделить на 5 нацело, то можно получить как 0 (когда число делится на 5 без остатка), так и 1, 2, 3, 4. Например, rand() вернула число 283. Применяя к этому числу операцию нахождения остатка от деления на 5, получим 3. Т.е. выражение rand() % 5 дает любое число в диапазоне [0, 5).

Однако, что если надо, чтобы число 5 так же входило в диапазон, т.е. диапазон имеет вид [0, 5]? Логично предположить, что следует найти остаток от деления на 6. При этом более грамотным будет следующее рассуждение: надо находить остаток от деления на размер диапазона. В данном случае он равен шести значениям: 0, 1, 2, 3, 4, 5. Чтобы найти размер диапазона надо из допустимого максимума вычесть допустимый минимум и прибавить единицу: max — min + 1. Будьте внимательны: если, например, требуется, чтобы указанный в задаче максимум не входил в диапазон, то единицу прибавлять не надо или надо вычитать единицу из максимума.

Задание
Напишите программу, выдающую 50 случайных чисел от 0 до 99 включительно.

Итак, мы знаем формулу получения длины диапазона: max — min + 1. Если требуется получить число от 6 до 10 включительно, то длина диапазона будет равна 10 — 6 + 1 = 5. Выражение rand()% 5 даст любое число от 0 до 4 включительно. Но нам надо от 6 до 10. В таком случае достаточно к полученному случайному остатку прибавить 6, т.е. минимум. Другими словами, надо выполнить сдвиг. Действительно для приведенного примера:

  • если остаток был равен 0, то добавляя 6, получаем 6;
  • остаток 1, добавляем 6, получаем 7;
  • остаток 4, прибавляем 6, получаем 10;
  • остатка больше 4 не может быть.

В таком случае формула для получения случайного числа в диапазоне [a, b] выглядит так:

где длина_диапазона вычисляется как b — a + 1, сдвиг является значением a.

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

Задание
Выведите на экран ряд случайных чисел, принадлежащих диапазону от 100 до 299 включительно.

С таким же успехом можно получать случайные отрицательные числа. Действительно, если диапазон задан как [-35, -1], то его длина будет равна -1 — (-35) + 1 = 35, что соответствует действительности; выражение получения случайного числа будет выглядеть так:

Так, если остаток от деления составил 0, то мы получим -35, а если 34, то -1. Остальные остатки дадут значения в промежутке от -35 до -1.

Задание
Выведите на экран ряд случайных чисел, принадлежащих диапазону от -128 до 127 включительно.

Получение вещественных случайных чисел

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

Поясним вторую причину. Допустим диапазон задан как [2.50, 5.30]. Он состоит не из определенного количества чисел (как в случае целых), а из неопределенного (можно сказать, бесконечного) числа значений, т.к. вещественные числа можно представлять с различной степенью точности. Позже выполняя округление все равно будет шанс получить максимальную границу диапазона, поэтому для вычисления длины диапазона достаточно из максимума вычесть минимум.

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

(float) rand() / RAND_MAX * (max — min) + min

Задание
Заполните массив случайными числами в диапазоне от 0.51 до 1.00. Выведите значение элементов массива на экран.

Равновероятные случайные числа

Функция rand() генерирует любое случайное число от 0 до RAND_MAX с равной долей вероятности. Другими словами, у числа 100 есть такой же шанс выпасть, как и у числа 25876.

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

В приведенной программе массив из пяти элементов сначала заполняется нулями. Случайные числа генерируются от 0 до 4 включительно. Если выпадает число 0, то увеличивается значение первого элемента массива, если число 1, то второго, и т.д. В конце на экран выводится процент выпадения каждого из чисел.

Задание
Спишите данную программу. Посмотрите на результат ее выполнения при различных значениях N: 10, 50, 500, 5000, 50000. Объясните увиденное.

Инициализация генератора псевдослучайных чисел

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

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

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

Илон Маск рекомендует:  Что такое код imagecopyresampled
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL