У цьому пості мова піде про застосування лінійного конгруентного методу для отримання псевдовипадкових чисел розрядності 64 і 128 біт з поясненням принципу роботи і підбору параметрів.
Якщо для вас тягарем користуватися ГСЧ зі стандартної бібліотеки, у вас до нього нестандартні вимоги або просто полювання тримати під контролем весь процес генерації випадкових чисел в своєму додатку, ласкаво просимо під кат.
Геть стандартний генератор!
Все досить поширені мови програмування мають функції для генерації випадкових (або, якщо бути гранично точним, псевдовипадкових) чисел. Однак іноді виникає необхідність реалізувати свій власний генератор випадкових чисел (ГВЧ). Хоча ГСЧ «з коробки» зазвичай досить хороший для застосування в більшості випадків, але буває і так, що занадто крутий генератор начебто і не потрібен, але вбудований ГСЧ все одно не подобається.
Причини можуть бути різні і неочевидні на перший погляд. По-перше, варто відзначити, що проблема генерації випадкових чисел часто включає в себе пошук балансу між швидкістю роботи і якістю результату. Іноді потрібно зробити трохи швидше або трохи складніше.
По-друге, ГСЧ - не просто каша з арифметичних операцій, а строго детермінований алгоритм, характеристики якого можуть сильно варіюватися. У деяких наукових експериментах необхідно повністю описувати умови тестів для гарантії можливості їх відтворення. Сюди відносяться алгоритм і параметри ГВЧ. В цьому випадку краще мати свою реалізацію.
Може виникнути завдання, в якій необхідна одночасна робота різних ГСЧ. Саме різних, а вбудований генератор зазвичай один. Можна, звичайно, запустити кілька копій з різних початковим зерном, проте в цьому випадку генератори будуть видавати елементи однієї і тієї ж послідовності (яка циклічно повторюється) просто почавши з різних місць. Довжина циклу величезна, але теоретично це може створити проблеми.
У моєму випадку потрібно було генерувати 128-розрядні числа. У C ++ немає функції, яка повертала хоча б 64-бітові. Після тривалого гугленія я виявив плутанину в rand () і RAND_MAX в різних компіляторах, набір милиць для генерації 64 біт, і вирішив відмовитися від вбудованого ГВЧ. Написання свого генератора здалося мені елементарним завданням - за пару ітерацій лінійного конгруентного генератора отримати два 64-розрядних числа, а потім склеїти їх. Це виявилося не так просто. Але про все по порядку.
Отже, приступимо до створення ГСЧ. За основу візьмемо простий і популярний лінійний конгруентний метод, який працює за формулою:
де xi. xi + 1 - поточний і наступний випадкові числа; a. c і m - деякі константи; mod - оператор знаходження залишку від ділення.
Константу m часто беруть рівною 2 32 або 2 64 щоб уникнути поділу в програмній реалізації. Щоб в результаті виходили 64-бітові залишки, я використовував m = 2 64. Але де ж взяти константи a і c. У Вікіпедії була знайдена наступна пара: a = 6364136223846793005 і c = 1442695040888963407. Недовго думаючи, я написав генератор, який використовує ці параметри, і почав тестувати свій генетичний алгоритм. Однак він швидко зациклювався. Підозри впали на ГСЧ. Виявляється, кілька молодших розрядів у отриманої послідовності 64-бітових «випадкових» чисел демонстрували аж ніяк не випадкове поводження. Значення деяких двійкових розрядів поспіль чисел зображені у вигляді монохромних картинок:
Значення молодших 5-го, 15-го і 20-го розрядів (нумерація з нуля)
Приблизно 20-24 молодших двійкових розряди виявляються не придатні для використання. Зі збільшенням номера розряду підвищується його випадковість. Таким чином, щоб отримати одне 64-бітове випадкове число, необхідні дві ітерації лінійного конгруентного генератора. Результат виходить конкатенацией двох 32-бітних фрагментів:
Наприклад, в java.util.Random використовується такий же принцип, хоча через те, що m = 2 48. там відкидаються тільки 16 молодших розрядів при генерації int і long. Це, зрозуміло, негативно впливає на якість випадкових чисел.
Ось приклад послідовності 64-бітових чисел, яка виходить при a = 6364136223846793005, c = 1442695040888963407, m = 2 64. x0 = 0 описаним на малюнку способом:
1442695037175000593
11166244415259155177
7076646891078057782
1459328390042580878
8905969149530007863
11682375496967736740
897247724006084730
Наскільки випадкові ці числа? Приблизно на рівні ГСЧ зі стандартної бібліотеки Java, можливо навіть трохи краще. Розрахунок кожного числа вимагає всього дві операції множення.
Якщо потрібні кілька різних генераторів, слід вибрати інші значення констант a і c. розраховані на m = 2 64. У статті за цим посиланням наведено приклади трьох констант з «хорошими якостями»:
c - непарне, m = 2 64