Как работает рандом в программировании

Функция random — генератор псевдослучайных чисел

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

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

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

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

var a, b: real; begin randomize; a := random(); writeln(a:6:4); b := random(); writeln(b:4:2); end.

0.5023 0.15

Если в скобках функции random() указан параметр, то она возвращает целое число от 0 до указанного в скобках (не включая само значение). Так выражение random(10) говорит о том, что будет получено любое число в диапазоне [0, 10).

var a, b: integer; begin randomize; a := random(10); writeln(a); b := random(-20); writeln(b); end.

7 -14

Если требуется получать значения в каком-либо другом диапазоне (не от нуля), то прибегают к математической хитрости. Например, чтобы получить случайное число от -100 до 100 достаточно записать такое выражение: random(200) — 100 . В результате его выполнения сначала будет получено число из диапазона [0, 199], а затем из него будет вычтена сотня. И если случайное число было меньше 100, то результат выражения будет отрицательным.

В программе ниже сначала с помощью процедуры randomize инициализируется датчик случайных чисел. Далее переменной n присваивается случайное значение в диапазоне [5, 12). Значение n используется для определения количества повторов цикла for. В цикле for генерируются случайные числа в диапазоне [-50, 49) и выводятся на экран.

var n, i, x: integer; begin randomize; n := random(7) + 5; for i := 1 to n do begin x := random(100) - 50; write(' ', x) end; writeln; end.

 0 38 23 -34 -13 -42 47

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

• min_i, max_i — минимальная и максимальная границы диапазона для целого числа;
• n_i — случайное целое число;
• min_f, max_f — минимальная и максимальная границы диапазона для вещественного числа;
• n_f — случайное вещественное число;
• first_c, last_c — первый и последний символ диапазона, в котором должен быть сгенерирован случайный символ;
• min_c, max_c — коды-числа, соответствующие указанным символам;
• n_c — случайное число, которое будет переведено в символ по таблице ASCII.

Программа на языке Паскаль:

var min_i, max_i, n_i: integer; min_f, max_f, n_f: real; first_c, last_c: char; min_c, max_c, n_c: byte; begin randomize; write('Minimum integer: '); readln(min_i); write('Maximum integer: '); readln(max_i); n_i := random(max_i-min_i+1) + min_i; writeln(n_i); write('Minimum float: '); readln(min_f); write('Maximum float: '); readln(max_f); n_f := random() * (max_f-min_f) + min_f; writeln(n_f:5:2); write('First char: '); readln(first_c); write('Last char: '); readln(last_c); min_c := ord(first_c); max_c := ord(last_c); n_c := random(max_c-min_c+1) + min_c; writeln(chr(n_c)); end.

Пример выполнения программы:

Minimum integer: -100 Maximum integer: 100 -46 Minimum float: 0.23 Maximum float: 0.85 0.53 First char: k Last char: q p

Случайные числа в языке C

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

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

#include #include int main() { int a = rand(); printf("%d\n", a); }

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

int a = RAND_MAX; printf("%d\n", a); // 2147483647

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

for (int i = 1; i  50; i++) { printf("%15d", rand()); if (i % 5 == 0) printf("\n"); }

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

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

Инициирующее значение можно запрашивать у пользователя с помощью scanf() и передавать его в srand() .

scanf("%d", &n); srand(n);

Однако чаще всего это не является полноценным выходом из ситуации. Поэтому инициализирующее значение привязывают к какому-либо процессу, протекающему в операционной системе, например, к часам. Время (учитывая не только время суток, но и дату) никогда не бывает одинаковым. Значит значение для 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. Будьте внимательны: если, например, требуется, чтобы указанный в задаче максимум не входил в диапазон, то единицу прибавлять не надо или надо вычитать единицу из максимума.

Следующее выражение выведет на экране случайное число от 0 до 99 включительно:

printf("%d\n", rand() % 100);

Итак, мы знаем формулу получения длины диапазона: 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] выглядит так:

rand() % длина_диапазона + сдвиг

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

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

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

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

rand() % 35 - 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.

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

#include #include #define N 500 int main () { int i; int arr[5] = {0}; srand(time(NULL)); for (i=0; i  N; i++) switch (rand() % 5) { case 0: arr[0]++; break; case 1: arr[1]++; break; case 2: arr[2]++; break; case 3: arr[3]++; break; case 4: arr[4]++; break; } for (i=0; i  5; i++) printf("%d - %.2f%%\n", i, ((float) arr[i] / N) * 100); }

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

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

Курс с решением задач:
pdf-версия

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

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

Введение

Сразу стоит сказать, что есть смысл генерировать случайные числа только с равномерным законом распределения, т.к. все остальные распределения можно получить из равномерного путём преобразований, известных из теории вероятности.
Для тех, кто забыл или пока не изучал теорию вероятности, напомню, что в равномерно распределённой последовательности нулей и единиц нули в среднем(!) будут встречаться в 50% случаев. Но это вовсе не значит, что в последовательности из 1000 цифр будет ровно 500 нулей. Более того, в последовательности из 1000 цифр может быть 999 нулей, и вероятность того, что тысячный элемент будет равен нулю по-прежнему остаётся равной 0.5. На первый взгляд это кажется парадоксальным, но важно понимать, что все последовательности равновероятны. Если же мы будем рассматривать достаточно большую совокупность таких последовательностей, то в среднем(!) в каждой из них будет 500 нулей.
Немного вспомнив теорию, мы перейдём к истории. В докомпьютерные времена случайные числа получали, вытаскивая разноцветные мячи из мешков, вытягивая карты, бросая кости. Понятно, что серьёзные исследования так проводить было нельзя, поэтому в 1927 года Типпетт опубликовал первую таблицу случайных чисел. Чуть позже люди попытались как-то автоматизировать этот процесс. Начали появляться машины, генерирующие случайные числа. Сейчас такие устройства тоже используются и называются источниками (генераторами) энтропии. Стоит заметить, что только такие устройства могут давать по-настоящему случайные числа. Но, к сожалению, генераторы энтропии довольно дороги, и не представляется возможным установить их в каждый ПК. Именно поэтому и возникла необходимость в алгоритмах получения случайных чисел.

Первая попытка получения ПСП

Некоторые люди думают, что получать случайные числа легко. По их мнению для этого достаточно делать случайные сложные математические действия над исходным числом. Если мы откроем второй том всем известного Кнута, то узнаем, что в 1959 Кнут тоже пробовал построить генератор, основанный на такой идее. Его алгоритм выглядел так:
К1. [Выбрать число итераций.] Присвоить Y наибольшую значащую цифру Х. (Мы выполним шаги К2-К13 точно Y+1 раз, т. е. применим рандомизированные преобразования случайное число раз.)
К2. [Выбрать случайный шаг] Присвоить следующую наибольшую значащую цифру X. Переходим к шагу К(3 + Z), т. е. к случайно выбранному шагу в программе.
КЗ. [Обеспечить > 5 х 109] Если X < 5000000000, присвоить X значение X + 5000000000.
К4. [Средина квадрата.] Заменить X серединой квадрата X.
К5. [Умножить.] Заменить X числом (1001001001 X) mod 1010.
К6. [Псевдодополнение.] Если X < 100000000, то присвоить X значение X + 9814055677; иначе присвоить X значение 1010- X.
К7. [Переставить половины.] Поменять местами пять младших по порядку знаков со старшими.
К8. [Умножить.] Выполнить шаг К5.
К9. [Уменьшить цифры.] Уменьшить каждую не равную нулю цифру десятичного представления числа X на единицу.
К10. [Модифицировать на 99999.] Если А’ < 105, присвоить X значение — X 2 +99999; иначе присвоить X значение X — 99999.
К11. [Нормировать.] (На этом шаге А’ не может быть равным нулю.) Если X К12. [Модификация метода средин квадратов.] Заменить Х на средние 10 цифр числа Х(Х — 1).
К13. [Повторить?] Если Y > 0, уменьшить У на 1 и возвратиться к шагу К2. Если Y = 0, алгоритм завершен. Значение числа X, полученное на предыдущем шаге, и будет желаемым «случайным» значением.
Несмотря на кажущуюся сложность, этот алгоритм быстро сошёлся к числу 6065038420, которое через небольшое число шагов преобразовалось в себя же. Мораль этой истории в том, что нельзя использовать случайный алгоритм для получения случайных чисел.

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

1. Модуль m (m>0);
2. Множитель a (0 <=a
3. Приращение c (0 <=c
4. Начальное значение X₀ (00

1. Числа m,a,c, X₀ не должны быть случайными;
2. Линейный конгруэнтный метод даёт нам повторяющиеся последовательности.

1. Числа c и m взаимно простые;
2. a-1 кратно p для каждого простого p, являющегося делителем m;
3. Если m кратно 4, то и a-1 должно быть кратно 4.

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

В основе алгоритма, который мы сейчас рассмотрим, лежит операция исключающего ИЛИ (сумма по модулю два). На всякий случай, напомню, как выглядит таблица истинности для данной функции:

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

Рассмотрим, как будут изменяться значения в этих регистрах при начальном значении 001:

Оба регистра начинают работу с одного и того же значения, но потом значения, генерируемые регистрами начинают быстро расходиться. Но через 6 шагов, оба регистра возвращаются в исходное состояние.
Легко показать, что оба этих регистра сгенерировали максимально длинную последовательность, которая содержит все комбинации, кроме нулевой. Т.е. при разрядности регистра m, можно получить последовательность длинной 2 m -1.
Полиномиальный счётчик любой разрядности имеет ряд комбинаций отводов, которые обеспечат последовательность максимальной длины, использование неверных комбинаций приведёт к генерации коротких последовательностей. Отдельная и довольно сложная задача – поиск этих комбинаций отводов.
Стоит заметить, что эти комбинации не всегда уникальны. К примеру, для 10-битного счётчика их существует две: [6;9] и [2;9], для шестиразрядного счётчика таких комбинаций двадцать восемь.
Для того, чтобы найти эти комбинации, необходимо представить счётчик в виде полинома. Счётчики из примера будут иметь следующий вид: x 2 XOR 1 и x 2 XOR x XOR 1.

• Характеристический полином нельзя представить в виде произведения полиномов более низкой степени;
• Характеристический полином является делителем полинома z δ XOR 1, при(δ=2 m -1, и не является делителем при любых других значениях δ

Надеюсь, эта статья была полезной для вас.

• случайные числа
• генерация

Алгоритмы рандома

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

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

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

C++ rand

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

int64_t A = rand(); A  

static unsigned long int next = 1; int rand() < next = next * 1103515245 + 12345; return (unsigned int)(next / 65536) % 32768; >

// пример, как это использовать: #include #include std::mt19937 engine; // mt19937 как один из вариантов engine.seed(std::time(nullptr)); /* на случай, если у вас UNIX-чё-то или компилятор не MinGW std::random_device device; engine.seed(device()); */ int val = engine(); // так получать рандом 

unsigned PRNG() < static unsigned seed = 1; // зерно не должно быть 0 seed = (seed * 73129 + 95121) % 100000; return seed; >

struct seed_t < unsigned x = 1; // начальные значения могут быть любыми unsigned y = 123; unsigned z = 456; unsigned w = 768; >; unsigned XorShift128() < static seed_t s; unsigned t = s.x^(s.x<<11); s.x = s.y; s.y = s.z; s.z = s.w; s.w = (s.w^(s.w>>19)) ^ (t^(t>>8)); return s.w; > 

// P2_sreg - static uint8_t void P2_Read_Random() < P2_sreg = (((((P2_sreg & 0x80) >> 7) ^ ((P2_sreg & 0x20) >> 5)) ^ (((P2_sreg & 0x10) >> 4) ^ ((P2_sreg & 0x08) >> 3))) ^ 1) | (P2_sreg

; рандом с эмулятора z26 ; a - output ; rdseed - 1 байт зерно randz26: exx ld a,(rdseed) and 20h sra a sra a sra a sra a sra a ld h, a ld a,(rdseed) and 80h sra a sra a sra a sra a sra a sra a sra a xor h ld l, h ld a,(rdseed) and 08h sra a sra a sra a ld h, a ld a,(rdseed) and 10h sra a sra a sra a sra a xor h ld h, a ld a, l xor h xor 1 ld h, a ld a,(rdseed) sla a or h ld (rdseed),a exx ret 

; By Joe Wingbermuehle ; a res 1 byte - out val ; rdseed res 1 byte - need for rand. != 0 rand8: exx ld hl,(rdseed) ld a,r ld d,a ld e,(hl) add hl,de add a,l xor h ld (rdseed),hl exx ret 

const uint8_t random_map[] = < 4, 1, 63, 3, 64, 22, 54, 2, 0, 52, 75, 34, 89, 100, 23, 84 >; uint8_t get_random() < static uint8_t index = 0; index = (index + 1) & 0xF; // 0xF, потому что столько значений в random_map return random_map[index]; >

; табличный рандом (как в DOOM) ; rand_table - ссылка на начало массива. Желательно подключить ; бинарный файл размера 256 байт со случайными цифрами. ; a - output num randtab: exx ; index ld a, (rdseed) inc a ;and filter ; for crop array index ld (rdseed), a ; calc array address ld hl, rand_table ld d, 0 ld e, a add hl, de ld a, (hl) ; get num from arr exx ret 

#include unsigned val; _rdrand32_step(&val);