Генерація рандомних чисел в С++ / aCode

Можливість генерувати випадкові числа дуже корисна в деяких видах програм, зокрема в іграх, програмах наукового або статистичного моделювання. Візьмемо, наприклад, гру без рандомних (або “випадкових”) подій — монстри завжди атакуватимуть вас однаково, ви завжди знаходитимете одні й ті ж предмети/артефакти, макети темниць і підземель ніколи не змінюватимуться тощо. Загалом, сюжет такої гри не дуже цікавий і навряд чи ви довго будете в неї грати.

Зміст:

Генератор псевдорандомних чисел
Функції srand() і rand()
Стартове число і послідовність в ГПРЧ
Генерація рандомних чисел у визначеному діапазоні
Який ГПРЧ є хорошим?
Чому rand() є посереднім ГПРЧ?
Відлагодження програм, які використовують рандомні числа
Рандомні числа в C++11

Генератор псевдорандомних чисел

Так як же генерувати випадкові числа? У реальному житті ми часто підкидаємо монетку (орел/решка), кидаємо кості або перетасовуємо карти. Ці події включають в себе таку велику кількість фізичних змінних (наприклад, сила тяжіння, тертя, опір повітря тощо), що вони стають майже неможливими для прогнозування/контролю і видають результати, які у всіх сенсах є випадковими.

Проте комп’ютери не призначені для використання фізичних змінних — вони не можуть підкинути монетку, кинути кості або перетасувати реальні карти. Комп’ютери живуть в контрольованому електричному світі, де є тільки два значення (true і false), чогось середнього між ними немає. За своєю природою комп’ютери призначені для отримання прогнозованих результатів. Коли ми говоримо комп’ютеру порахувати, скільки буде 2 + 2, то ми завжди хочемо, щоб відповіддю було 4 (а не 3, і не 5).

Отже, комп’ютери не здатні генерувати випадкові числа. Замість цього вони можуть імітувати випадковість, що досягається за допомогою генераторів псевдорандомних чисел.

Генератор псевдорандомих чисел (або “ГПРЧ”) — це програма, яка приймає стартове/початкове значення і виконує з ним певні математичні операції, щоб конвертувати його в інше число, яке зовсім не пов’язане зі стартовим. Потім програма використовує нове згенероване значення і виконує з ним ті ж математичні операції, що і з початковим числом, щоб конвертувати його в ще в одне нове число — уже третє по рахунку, яке не пов’язане ні з першим, ні з другим числом. Застосовуючи цей алгоритм до останнього згенерованого значення, програма може генерувати цілий ряд нових чисел, які здаватимуться випадковими (за умови, що алгоритм буде досить складним).

Насправді, написати простий ГПРЧ не так вже і складно. Ось невелика програма, яка генерує 100 випадкових чисел:

#include <iostream>
 
unsigned int PRNG()
{
    // Наше стартове число - 4 541
    static unsigned int seed = 4541;
 
    // Беремо стартове число і з його допомогою генеруємо нове значення.
    // Через використання дуже великих чисел (і переповнення) вгадати наступне число, виходячи з попереднього - дуже складно
    seed = (8253729 * seed + 2396403);
 
    // Беремо стартове число і повертаємо значення в діапазоні від 0 до 32 767
    return seed  % 32768;
}
 
int main()
{
    // Виводимо 100 рандомних чисел
    for (int count=0; count < 100; ++count)
    {
        std::cout << PRNG() << "\t";
 
        // Якщо вивели 5 чисел, то вставляємо символ нового рядка
        if ((count+1) % 5 == 0)
            std::cout << "\n";
	}
}

#include <iostream>

unsigned int PRNG()

{

// Наше стартове число - 4 541

static unsigned int seed = 4541;

// Беремо стартове число і з його допомогою генеруємо нове значення.

// Через використання дуже великих чисел (і переповнення) вгадати наступне число, виходячи з попереднього - дуже складно

seed = (8253729 * seed + 2396403);

// Беремо стартове число і повертаємо значення в діапазоні від 0 до 32 767

return seed % 32768;

}

int main()

{

// Виводимо 100 рандомних чисел

for (int count=0; count < 100; ++count)

{

std::cout << PRNG() << "\t";

// Якщо вивели 5 чисел, то вставляємо символ нового рядка

if ((count+1) % 5 == 0)

std::cout << "\n";

}

Результат виконання програми:

18256 4675 32406 6217 27484 975 28066 13525 25960 2907 12974 26465 13684 10471 19898 12269 23424 23667 16070 3705 22412 9727 1490 773 10648 1419 8926 3473 20900 31511 5610 11805 20400 1699 24310 25769 9148 10287 32258 12597 19912 24507 29454 5057 19924 11591 15898 3149 9184 4307 24358 6873 20460 2655 22066 16229 20984 6635 9022 31217 10756 16247 17994 19069 22544 31491 16214 12553 23580 19599 3682 11669 13864 13339 13166 16417 26164 12711 11898 26797 27712 17715 32646 10041 18508 28351 9874 31685 31320 11851 9118 26193 612 983 30378 26333 24688 28515 8118 32105

Кожне число вважається випадковим по відношенню до попереднього. Але примітивність цього алгоритму є його недоліком.

Функції srand() і rand()

Мови Cі та C++ мають свої власні вбудовані генератори випадкових чисел. Вони реалізовані в двох окремих функціях, які знаходяться в заголовковому файлі cstdlib:

Функція srand() встановлює передане користувачем значення в якості стартового. srand() слід викликати тільки один раз — на початку програми (зазвичай у верхній частині функції main()).

Функція rand() генерує наступне випадкове число в послідовності. Воно знаходитиметься в діапазоні від 0 до RAND_MAX (константа в cstdlib, значенням якої є 32767).

Ось приклад програми, яка використовує обидві ці функції:

#include <iostream>
#include <cstdlib> // для функцій rand() і srand()
 
int main()
{
    srand(4541); // встановлюємо стартове значення - 4 541
 
    // Виводимо 100 рандомних чисел
    for (int count=0; count < 100; ++count)
    {
        std::cout << rand() << "\t";
 
        // Якщо вивели 5 чисел, то вставляємо символ нового рядка
        if ((count+1) % 5 == 0)
            std::cout << "\n";
	}
}

#include <iostream>

#include <cstdlib> // для функцій rand() і srand()

int main()

{

srand(4541); // встановлюємо стартове значення - 4 541

// Виводимо 100 рандомних чисел

for (int count=0; count < 100; ++count)

{

std::cout << rand() << "\t";

// Якщо вивели 5 чисел, то вставляємо символ нового рядка

if ((count+1) % 5 == 0)

std::cout << "\n";

}

Результат виконання програми:

14867 24680 8872 25432 21865 17285 18997 10570 16397 30572 22339 31508 1553 124 779 6687 23563 5754 25989 16527 19808 10702 13777 28696 8131 18671 27093 8979 4088 31260 31016 5073 19422 23885 18222 3631 19884 10857 30853 32618 31867 24505 14240 14389 13829 13469 11442 5385 9644 9341 11470 189 3262 9731 25676 1366 24567 25223 110 24352 24135 459 7236 17918 1238 24041 29900 24830 1094 13193 10334 6192 6968 8791 1351 14521 31249 4533 11189 7971 5118 19884 1747 23543 309 28713 24884 1678 22142 27238 6261 12836 5618 17062 13342 14638 7427 23077 25546 21229

Стартове число і послідовність в ГПРЧ

Якщо ви запустите вищенаведену програму (генерація випадкових чисел) декілька разів, то помітите, що в результатах завжди знаходяться одні й ті ж самі числа! Це означає, що, хоча кожне число в послідовності здається випадковим щодо попереднього, вся послідовність не є випадковою взагалі! А це, в свою чергу, означає, що наша програма повністю передбачувана (одні і ті ж вхідні значення призводять до одних і тих же вихідних значень). Бувають випадки, коли це може бути корисно або навіть бажано (наприклад, якщо ви хочете, щоб наукова симуляція повторювалася, або ви проводите відлагодження збою вашого генератора рандомних підземель).

Але в більшості випадків це не зовсім те, що нам потрібно. Якщо ви пишете гру типу Hi-Lo (де у користувача є 10 спроб вгадати число, а комп’ютер повідомляє йому, наскільки його припущення близькі або далекі від реального числа), ви б не хотіли, щоб програма вибирала одні й ті ж самі числа кожного разу. Тому давайте більш детально розглянемо, чому це відбувається і як це можна виправити.

Пам’ятайте, що кожне нове число в послідовності ГПРЧ генерується виходячи з попереднього певним способом. Таким чином, при будь-якому початковому числі ГПРЧ завжди генеруватиме одну і ту ж саму послідовність! У вищенаведеній програмі послідовність чисел завжди однакова, так як стартове число завжди дорівнює 4541.

Щоб це виправити нам потрібен спосіб вибрати стартове число, яке не буде фіксованим значенням. Перше, що спадає на думку — це використати рандомне число! Це слушна думка, але якщо нам потрібно випадкове число для генерації випадкових чисел, то це якесь замкнуте коло, вам не здається? Виявляється, нам не обов’язково використовувати випадкове стартове число — нам просто потрібно вибрати щось, що змінюватиметься кожен раз при новому запуску програми. Потім ми зможемо використовувати наш ГПРЧ для генерації унікальної послідовності рандомних чисел виходячи з унікального стартового числа.

Загальноприйнятим рішенням є використання системного годинника. Кожен раз, при запуску програми, час буде інший. Якщо ми будемо використовувати значення часу в якості стартового числа, то наша програма завжди генеруватиме різну послідовність чисел при кожному новому запуску!

У мові Cі є функція time(), яка повертає в якості часу загальну кількість секунд від півночі 1 січня 1970 року і до сьогоднішнього часу. Щоб скористатися цією функцією, нам просто потрібно підключити заголовок ctime, а потім ініціалізувати функцію srand() викликом функції time(0).

Ось вищенаведена програма, але вже з використанням функції time() в якості стартового числа:

#include <iostream>
#include <cstdlib> // для функцій rand() і srand()
#include <ctime> // для функції time()
 
int main()
{
    srand(static_cast<unsigned int>(time(0))); // встановлюємо значення системного годинника в якості стартового числа
 
    for (int count=0; count < 100; ++count)
    {
        std::cout << rand() << "\t";
 
        // Якщо вивели 5 чисел, то вставляємо символ нового рядка
        if ((count+1) % 5 == 0)
            std::cout << "\n";
	}
}

#include <iostream>

#include <cstdlib> // для функцій rand() і srand()

#include <ctime> // для функції time()

int main()

{

srand(static_cast<unsigned int>(time(0))); // встановлюємо значення системного годинника в якості стартового числа

for (int count=0; count < 100; ++count)

{

std::cout << rand() << "\t";

// Якщо вивели 5 чисел, то вставляємо символ нового рядка

if ((count+1) % 5 == 0)

std::cout << "\n";

}

Тепер наша програма генеруватиме різні послідовності випадкових чисел! Спробуйте самі.

Генерація випадкових чисел у визначеному діапазоні

У більшості випадків нам не потрібні рандомні числа між 0 і RAND_MAX — нам потрібні числа між двома іншими значеннями: min і max. Наприклад, якщо нам потрібно зімітувати підкидання грального кубика, то діапазон значень буде невеликий: від 1 до 6.

Ось невелика функція, яка конвертує результат функції rand() в потрібний нам діапазон значень:

// Генеруємо рандомне число між значеннями min і max.
// Припускається, що функцію srand() вже викликали
int getRandomNumber(int min, int max)
{
    static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0); 
    // Рівномірно розподіляємо рандомне число в нашому діапазоні
    return static_cast<int>(rand() * fraction * (max - min + 1) + min);
}

// Генеруємо рандомне число між значеннями min і max.

// Припускається, що функцію srand() вже викликали

int getRandomNumber(int min, int max)

{

static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);

// Рівномірно розподіляємо рандомне число в нашому діапазоні

return static_cast<int>(rand() * fraction * (max - min + 1) + min);

}

Щоб зімітувати підкидання грального кубика, викличемо функцію getRandomNumber(1, 6).

Який ГПРЧ є хорошим?

Як ми вже говорили, генератор випадкових чисел, який ми написали вище, є не дуже хорошим. Зараз розглянемо чому.

Хороший ГПРЧ повинен мати ряд властивостей:

Властивість №1: ГПРЧ повинен генерувати кожне нове число з приблизно однаковою ймовірністю. Це називається рівномірністю розподілу. Якщо деякі числа генеруються частіше, ніж інші, то результат програми, що використовує ГПРЧ — передбачуваний! Наприклад, припустимо, що ви намагаєтеся написати генератор випадкових предметів для гри. Ви вибираєте випадкове число від 1 до 10, і, якщо результатом буде 10, гравець отримає крутий предмет замість посереднього. Шанси будуть 1 до 10. Але, якщо ваш ГПРЧ не рівномірно генерує числа, наприклад, десятки генеруються частіше, ніж повинні, то ваші гравці отримуватимуть більш рідкісні предмети частіше, ніж передбачалося, і складність разом з інтересом до такої гри автоматично зменшиться.

Створити ГПРЧ, який би генерував рівномірні результати — складно, і це одна з головних причин, через яку ГПРЧ, який ми написали на початку цього уроку, є не дуже хорошим.

Властивість №2: Метод, за допомогою якого генерується наступне число в послідовності, не повинен бути очевидним чи передбачуваним. Наприклад, розглянемо наступний алгоритм ГПРЧ: num = num + 1. У нього є рівномірність розподілу рандомних чисел, але це не рятує його від примітивності і передбачуваності!

Властивість №3: ГПРЧ повинен мати хороший діапазон розподілу чисел. Це означає, що маленькі, середні і великі числа повинні повертатися випадковим чином. ГПРЧ, який повертає всі маленькі числа, а потім всі великі — передбачуваний і призведе до передбачуваних результатів.

Властивість №4: Період циклічного повторення значень ГПРЧ повинен бути максимально великим. Всі ГПРЧ є циклічними, тобто в якийсь момент послідовність згенерованих чисел почне повторюватися. Як згадувалося раніше, ГПРЧ є детермінованим, і з одним вхідним значенням ми отримаємо одне і те ж вихідне значення. Подумайте, що станеться, коли ГПРЧ згенерує число, яке вже раніше було згенеровано. З цього моменту почнеться дублювання послідовності чисел між першою і наступною появою цього числа. Довжина цієї послідовності називається періодом.

Наприклад, ось представлені перші 100 чисел, згенеровані ГПРЧ з поганим періодом:

112 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9

Помітили, що він згенерував 9 як друге число, а потім як шістнадцяте? ГПРЧ застряє, генеруючи послідовність між цими двома 9-ми: 9-130-97-64-31-152-119-86-53-20-141-108-75-42- (повтор).

Хороший ГПРЧ повинен мати довгий період для всіх стартових чисел. Розробка алгоритму, який задовольняє цю властивість, може бути надзвичайно складною — більшість ГПРЧ мають довгі періоди для одних початкових чисел і короткі для інших. Якщо користувач вибрав початкове число, яке має короткий період, то і результати будуть відповідні.

Незважаючи на складність розробки алгоритмів, що відповідають всім цим критеріям, в цій області було проведено велику кількість досліджень, тому що різні ГПРЧ активно використовуються в важливих галузях науки.

Чому rand() є посереднім ГПРЧ?

Алгоритм, який використовується для реалізації rand(), може варіюватися в різних компіляторах, і, відповідно, результати також можуть бути різними. У більшості реалізацій rand() використовується Лінійний Конгруентний Метод (скор. “ЛКМ”). Якщо ви подивитеся на перший приклад цього уроку, то помітите, що там використовується ЛКМ, хоч і з навмисно підібраними поганими константами.

Одним з основних недоліків функції rand() є те, що RAND_MAX зазвичай встановлюється як 32767 (15-бітне значення). Це означає, що якщо ви захочете згенерувати числа в більш широкому діапазоні (наприклад, 32-бітні цілі числа), то функція rand() не підійде. Крім того, вона не підійде, якщо ви захочете згенерувати випадкові числа типу з плаваючою крапкою (наприклад, між 0.0 і 1.0), що часто використовується в статистичному моделюванні. Нарешті, функція rand() має відносно короткий період у порівнянні з іншими алгоритмами.

Проте цей алгоритм відмінно підходить для вивчення програмування і для програм, в яких висококласний ГПРЧ не є необхідністю.

Для програм, де необхідний висококласний ГПРЧ, рекомендується використовувати алгоритм Вихор Мерсенна (англ. “Mersenne Twister“), який генерує відмінні результати і відносно простий у використанні.

Відлагодження програм, які використовують рандомні числа

Програми, які використовують рандомні числа, важко відлагоджувати, оскільки при кожному запуску такої програми ми отримуватимемо різні результати. А щоб успішно проводити відлагодження програм, потрібно впевнитися, що наша програма виконується однаково при кожному її запуску. Таким чином, ми зможемо швидко дізнатися розташування помилки і ізолювати цю ділянку коду.

Тому, проводячи відлагодження програм, корисно використовувати в якості стартового числа (з використанням функції srand()) певне значення (наприклад, 0), яке викличе помилкове поведінку програми. Це гарантуватиме, що наша програма кожен раз генерує одні і ті ж результати (що значно полегшить процес відлагодження). Після того, як ми знайдемо і виправимо помилку, ми зможемо знову використовувати системний годинник для генерації рандомних результатів.

Рандомні числа в C++11

У C++11 додали тонну нового функціоналу для генерації випадкових чисел, включаючи алгоритм Вихор Мерсенна, а також різні види генераторів рандомних чисел (наприклад, рівномірні, генератор Poisson тощо). Доступ до них здійснюється через підключення заголовку random. Ось приклад генерації випадкових чисел в C++11 з використанням Вихора Мерсенна:

#include <iostream>
// #include <ctime> // розкоментуйте, якщо використовуєте Code::Blocks
#include <random> // для std::random_device і std::mt19937
 
int main()
{
    std::random_device rd; 
    std::mt19937 mersenne(rd()); // ініціалізуємо Вихор Мерсенна випадковим стартовим числом
 
// Примітка: Через один баг в компіляторі Code::Blocks (якщо ви використовуєте Code::Blocks в Windows) - видаліть два рядка коду вище і розкоментуйте наступний рядок:
// std::mt19937 mersenne(static_cast<unsigned int>(time(0))); // ініціалізуємо Вихор Мерсенна випадковим стартовим числом
 
    // Виводимо декілька випадкових чисел
    for (int count = 0; count < 48; ++count)
    {
        std::cout << mersenne() << "\t";
 
        // Якщо вивели 5 чисел, то вставляємо символ нового рядка
        if ((count + 1) % 5 == 0)
            std::cout << "\n";
    }
}

#include <iostream>

// #include <ctime> // розкоментуйте, якщо використовуєте Code::Blocks

#include <random> // для std::random_device і std::mt19937

int main()

{

std::random_device rd;

std::mt19937 mersenne(rd()); // ініціалізуємо Вихор Мерсенна випадковим стартовим числом

// Примітка: Через один баг в компіляторі Code::Blocks (якщо ви використовуєте Code::Blocks в Windows) - видаліть два рядка коду вище і розкоментуйте наступний рядок:

// std::mt19937 mersenne(static_cast<unsigned int>(time(0))); // ініціалізуємо Вихор Мерсенна випадковим стартовим числом

// Виводимо декілька випадкових чисел

for (int count = 0; count < 48; ++count)

{

std::cout << mersenne() << "\t";

// Якщо вивели 5 чисел, то вставляємо символ нового рядка

if ((count + 1) % 5 == 0)

std::cout << "\n";

}

Вихор Мерсенна генерує випадкові 32-бітні цілі числа unsigned (а не 15-бітні цілі числа, як у випадку з rand()), що дозволяє використовувати набагато ширший діапазон значень. Існує також версія (std::mt19937_64) для генерації 64-бітних цілих чисел unsigned!

Примітка для користувачів Visual Studio: Реалізація функції rand() в Visual Studio має один істотний недолік — перше згенероване випадкове число не дуже відрізняється від стартового. Це означає, що при використанні функції time() для генерації стартового числа, перше число не буде сильно відрізнятися/змінюватися від стартового і при наступних запусках. Є просте рішення: викличте функцію rand() один раз і скиньте результат. Потім ви зможете використовувати rand() як зазвичай у вашій програмі.

Оцінити статтю:

(68 оцінок, середня: 4,93 з 5)

Завантаження...

Коментарів: 3

Іван :

5 Червня 2023 о 12:48 pm

Вітаю. Особисто для мене це дуже корисний урок, але є одне питання. Як можна задати діапазон чисел, які генеруються за допомогою вихору Мерсенна? Дякую.

Відповіcти
Артем Вікторович :

6 Березня 2023 о 6:06 pm

Підкажіть будьласка таку річ, в чому може бути проблема. Вивчаю самостійно програмування мікроконтролерів на СІ. Стикнувся з таким явищем, при використанні функції rand(). Якщо у файлі stdlib.h вручну змінити максимальну межу RAND_MAX це не дає ніякого результату. Функція rand() все одно генерує значення більші, ніж вказано вручну.
Проблему вирішено простим математичним перетворенням, але цікаво все ж таки з чим це може бути пов’язано.

Відповіcти
1. Віктор :
  
  1 Квітня 2023 о 1:07 am
  
  В уроці сказано, що RAND_MAX це константа. Тому її значення не можна змінити
  
  Відповіcти

Урок №74. Генерація рандомних чисел

Генератор псевдорандомних чисел

Функції srand() і rand()

Стартове число і послідовність в ГПРЧ

Генерація випадкових чисел у визначеному діапазоні

Який ГПРЧ є хорошим?

Чому rand() є посереднім ГПРЧ?

Відлагодження програм, які використовують рандомні числа

Рандомні числа в C++11

Коментарів: 3

Залишити відповідь Скасувати коментар