Тести - спрощена генерація випадкових чисел

У цій статті я покажу, як генерувати випадкові числа з допомогою чотирьох різних алгоритмів: алгоритму Лемера (Lehmer), лінійного конгруентного алгоритму (linear congruential algorithm), алгоритму Вічмана-Хілла (Wichmann-Hill) і алгоритму Фібоначчі з запізнюваннями (lagged Fibonacci algorithm) .

Але навіщо обтяжувати себе створенням власного генератора випадкових чисел (random number generator, RNG), коли в Microsoft .NET Framework вже є ефективний і простий у використанні клас Random? Існує два сценарії, де вам може знадобитися створити свій RNG. По-перше, в різні мови програмування вбудовані різні алгоритми генерації випадкових чисел, а значить, якщо ви пишете код, який буде переноситися на кілька мов, можна створити власний RNG, щоб реалізувати його в усіх потрібних вам мовами. По-друге, деякі мови, зокрема R, мають лише глобальний RNG, тому, якщо ви захочете створити кілька генераторів, вам доведеться писати свій RNG.

Хороший спосіб отримати уявлення про те, куди я хилю в цій статті, - поглянути на демонстраційну програму на рис. 1. Демонстраційна програма починає зі створення дуже простого RNGЮ використовуючи алгоритм Лемера. Потім за допомогою RNG генерується 1000 випадкових цілих чисел між 0 і 9 включно. За лаштунками записуються лічильники для кожного з згенерованих цілих чисел, які потім відображаються на екрані. Цей процес повторюється для лінійного конгруентного алгоритму, алгоритму Вічмана-Хілла і алгоритм Фібоначчі з запізнюваннями.

Мал. 1. Демонстрація спрощеної генерації випадкових чисел

У цій статті передбачається, що ви вмієте програмувати хоча б на середньому рівні, але нічого не знаєте про генерації випадкових чисел. Демонстраційна програма написана на C #, але, оскільки один з основних випадків використання власної генерації випадкових чисел - написання портіруемость коду, ця програма розроблена так, щоб її можна було легко транслювати на інші мови.

алгоритм Лемера

Найпростіший прийнятний метод генерації випадкових чисел - алгоритм Лемера. (Для простоти я використовую термін «генерація випадкових чисел» замість більш точного терміну «генерація псевдовипадкових чисел».) Виражений в символьному вигляді, алгоритм Лемера є наступною:

На словах це звучить так: «нове випадкове число є старим випадковим числом, множимо на константу a, після чого над результатом виконується операція по модулю константи m». Наприклад, припустимо, що в якийсь момент поточний випадкове число дорівнює 104, a = 3 і m = 100. Тоді нове випадкове число буде дорівнює 3 * 104 mod 100 = 312 mod 100 = 12. Начебто просто, але в реалізації цього алгоритму багато хитромудрих деталей.

Щоб створити демонстраційну програму, я запустив Visual Studio, вибрав шаблон C # Console Application і назвав проект RandomNumbers. У цій програмі немає значущих залежностей від .NET Framework, тому підійде будь-яка версія Visual Studio.

Мал. 2. Реалізація алгоритму Лемера

Проблема реалізації в тому, щоб запобігати арифметичне переповнення. Алгоритм Лемера використовує спритний алгебраїчний трюк. Значення q є результатом m / a (цілочисельне ділення), а значення r одно m% a (m по модулю a).

При ініціалізації RNG Лемера початковим (зародковим) значенням можна використовувати будь-яке ціле число в діапазоні [1, int.MaxValue - 1]. Багато RNG мають конструктор без параметрів, який отримує системні дату і час, перетворює їх в ціле число і використовує в якості початкового значення.

RNG Лемера викликається в методі Main демонстраційної програми:

Кожен виклик методу Next повертає значення в діапазоні [0,0, 1.0) - більше або дорівнює 0.0 і строго менше 1.0. Шаблон (int) (hi - lo) * Next + lo) буде повертати ціле число в діапазоні [lo, hi-1].

Алгоритм Лемера вельми ефективний, і в простих сценаріях я зазвичай вибираю саме його. Але зауважте, що жоден алгоритм з представлених в цій статті не володіє надійністю криптографічного рівня і що їх слід застосовувати тільки в ситуаціях, де не потрібно статичної строгості (statistical rigor).

Алгоритм Вічмана-Хілла

Цей алгоритм датується тисячі дев'ятсот вісімдесят два роком. Ідея Вічмана-Хілла полягає в генерації трьох попередніх результатів і подальшого їх об'єднання в один фінальний результат. Код, який реалізує алгоритм Вічмана-Хілла, представлений на рис. 3. Демонстраційний код заснований на статті Б. А. Вічмана (B. A. Wichmann) і А. Д. Хілла (I. D. Hill) «Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator».

Мал. 3. Реалізація алгоритму Вічмана-Хілла

Оскільки алгоритм Вічмана-Хілла використовує три різних генеруючих рівняння, він вимагає трьох початкових значень. У цьому алгоритмі три m-значення рівні 30269, 30307 і 30323, тому вам знадобляться три початкових значення в діапазоні [1, 30000]. Ви могли б написати конструктор, що приймає ці три значення, але тоді ви отримали б кілька дратівливий програмний інтерфейс. У демонстрації застосовується параметр з одним початковим значенням, генеруючим три робочих зародка.

Виклик RNG Вічмана-Хілла здійснюється за тим же шаблоном, що і інших демонстраційних RNG:

Алгоритм Вічмана-Хілла лише трохи важче в реалізації, ніж алгоритм Лемера. Перевага першого над другим в тому, що алгоритм Вічмана-Хілла генерує довшу послідовність (більше 6 000 000 000 000 значень) до того, як почне повторюватися.

Лінійний конгруентний алгоритм

Виявляється, і алгоритм Лемера, і алгоритм Вічмана-Хілла можна вважати особливими випадками так званого лінійного конгруентного алгоритму (linear congruential, LC). Виражений у вигляді рівняння, LC виглядає так:

Це точно відповідає алгоритму Лемера з додаванням додаткової константи c. Включення c надає універсального LC-алгоритму трохи кращі статистичні властивості в порівнянні з алгоритмом Лемера. Демонстраційна реалізація LC-алгоритму показана на рис. 4. Код заснований на стандарті POSIX (Portable Operating System Interface).

Мал. 4. Реалізація лінійного конгруентного алгоритму

LC-алгоритм використовує кілька бітових операцій. Тут ідея в тому, щоб в базових математичних типах працювати не з цілим типом (32 біта), а з довгим цілим (64 біта). Після закінчення 32 з цих бітів (з 16-го по 47-й включно) витягуються і перетворюються в ціле число. Цей підхід дає більш якісні результати, ніж при використанні просто 32 молодших або старших бітів, але за рахунок деякого ускладнення кодування.

У демонстрації генератор випадкових чисел LC викликається так:

Демонстраційний код використовує попередні випадкові числа X (i-7) і X (i-10) для генерації наступного випадкового числа. У науково-дослідній літературі з цієї тематики значення (7, 10) зазвичай позначаються (j, k). Існують інші пари (j, k), які можна застосовувати для алгоритму Фібоначчі з запізнюваннями. Кілька значень, рекомендованих в добре відомій книзі «Art of Computer Programming» (Addison-Wesley, 1968), - (24,55), (38,89), (37,100), (30,127), (83,258), (107,378) .

Щоб форматувати (j, k) в RNG Фібоначчі з запізнюваннями, ви повинні попередньо заповнити список значеннями k. Це можна зробити декількома способами. Однак найменше з початкових значень k обов'язково має бути непарною. У демонстрації застосовується грубий метод копіювання значення параметра seed для всіх початкових значень k з подальшим видаленням перші 1000 згенерованих значень. Якщо значення параметра seed парне, тоді перше з значень k виставляється рівним 11 (безпідставного непарному числу).

Щоб запобігти арифметичне переповнення, метод Next використовує тип long для обчислень і математичне властивість: (a + b) mod n = [(a mod n) + (b mod n)] mod n.

висновок

Висловлюю подяку за рецензування статті експертам Microsoft Крісу Лі (Chris Lee) і Кірку Олініку (Kirk Olynyk).