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

  Юрій  | 

  Оновл. 7 Вер 2021  | 

 522

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

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

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

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

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

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

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

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

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).

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

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

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() в якості стартового числа:

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

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

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

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

Щоб зімітувати підкидання грального кубика, викличемо функцію 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 з використанням Вихора Мерсенна:

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

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

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

1 Зірка2 Зірки3 Зірки4 Зірки5 Зірок (5 оцінок, середня: 5,00 з 5)
Loading...

Залишити відповідь

Ваш E-mail не буде опублікований. Обов'язкові поля відмічені *