Введение

Алгоритм генерации псевдослучайных чисел

Линейный конгруэнтный генератор (ЛКГ) — это алгоритм, который выдает последовательность псевдослучайных чисел, вычисляемых с помощью кусочно-линейного уравнения. Этот метод является одним из старейших и наиболее известных алгоритмов генераторов псевдослучайных чисел. Теория, лежащая в его основе, относительно проста для понимания, и он легко реализуется и работает быстро, особенно на компьютерном оборудовании, способном выполнять модульную арифметику посредством усечения битов хранения. Генератор определяется рекуррентным соотношением:

где — последовательность псевдослучайных значений, а

— "модуль"
— "множитель"
— "приращение"
— "начальное значение" или "затравка"

— целые константы, определяющие генератор. Если c = 0, генератор часто называют мультипликативным конгруэнтным генератором (МКГ) или генератором Лемера. Если c ≠ 0, метод называется смешанным конгруэнтным генератором. При c ≠ 0 математик назвал бы это рекуррентное соотношение аффинным преобразованием, а не линейным, но это неверное название прочно закрепилось в информатике.

История

Генератор Лемера был опубликован в 1951 году, а линейный сравнительный генератор — в 1958 году У. Э. Томсоном и А. Ротенбергом.

m простые числа, c = 0

Это оригинальная конструкция РНГ Лемера. Период равен m−1, если множитель a выбран как примитивный элемент по модулю m. Начальное состояние должно быть выбрано между 1 и m−1. Одним из недостатков использования простого модуля является то, что модульное приведение требует произведения двойной точности и явного шага приведения. Часто используется простое число, немного меньшее степени 2 (популярны простые числа Мерсенна 231−1 и 261−1), так что приведение по модулю m = 2e − d можно вычислить как (ax mod 2e) + d. За этим должно следовать условное вычитание m, если результат слишком велик, но количество вычитаний ограничено ad/m, которое можно легко ограничить единицей, если d мало. Если произведение двойной точности недоступно, а множитель выбран тщательно, можно использовать метод Шраге. Для этого разложите m = qa+r, то есть и 1=r = m mod a. Затем вычислите ax mod m = Поскольку x mod q < q ≤ m/a, первый член строго меньше am/a = m. Если a выбрано таким образом, что r ≤ q (и, следовательно, r/q ≤ 1), то второй член также меньше m: r ≤ rx/q = x(r/q) ≤ x < m. Таким образом, оба произведения можно вычислить с использованием произведения одинарной точности, а разница между ними лежит в диапазоне [1−m, m−1], поэтому её можно привести к диапазону [0, m−1] с помощью одного условного сложения. Вторым недостатком является то, что преобразование значения 1 ≤ x < m в равномерные случайные биты является затруднительным. Если используется простое число, меньшее степени 2, то иногда недостающие значения просто игнорируются.

m a в степени 2, c = 0

Выбор m в качестве степени двойки, чаще всего m = 232 или m = 264, приводит к созданию особенно эффективного LCG, поскольку это позволяет вычислять операцию взятия по модулю, просто усекая двоичное представление. Фактически, наиболее значимые биты обычно вообще не вычисляются. Однако существуют и недостатки. Эта форма имеет максимальный период m/4, который достигается при выполнении условия a ≡ ±3 (mod 8) и нечетного начального состояния X0. Даже в этом наилучшем случае, младшие три бита X чередуются между двумя значениями и, следовательно, вносят только один бит в состояние. X всегда нечетный (бит наименьшего разряда никогда не меняется), и только один из следующих двух битов когда-либо меняется. Если a ≡ +3, то X чередуется между ±1 и ±3, а если a ≡ −3, то X чередуется между ±1 и ∓3 (все по модулю 8). Можно показать, что эта форма эквивалентна генератору с модулем m/4 и c ≠ 0. Более серьезной проблемой при использовании модуля, являющегося степенью двойки, является то, что младшие биты имеют период меньше, чем старшие биты. Простота реализации обусловлена тем, что биты никогда не зависят от битов более высокого порядка, поэтому младшие b битов такого генератора сами по себе образуют LCG по модулю 2b, повторяющийся с периодом 2b−2. Только старший бит X достигает полного периода.

Деривативы LCG

Существует несколько генераторов, которые представляют собой линейные конгруэнтные генераторы в иной форме, и поэтому методы, используемые для анализа LCG, могут быть применены и к ним. Один из способов достижения более длинного периода – суммировать выходные данные нескольких LCG с разными периодами, имеющими большое наименьшее общее кратное; генератор Вихмана-Хилла является примером такой реализации. (Было бы предпочтительнее, чтобы они были взаимно простыми, но использование простых модулей подразумевает чётный период, поэтому общий множитель 2 будет присутствовать как минимум.) Можно показать, что это эквивалентно одному LCG с модулем, равным произведению модулей составляющих LCG. Генераторы Марсальи с добавлением с переносом и вычитанием с заимствованием, с размером слова b=2w и запаздываниями r и s (r > s), эквивалентны LCG с модулем br ± bs ± 1. Генераторы с умножением с переносом и множителем a эквивалентны LCG с большим простым модулем abr−1 и множителем, равным степени двойки b. Пермутированный конгруэнтный генератор начинается с LCG с модулем, являющимся степенью двойки, и применяет преобразование выходных данных для устранения проблемы короткого периода в младших битах.

Сравнение с другими PRNG

Другим широко используемым примитивом для получения псевдослучайных последовательностей с большим периодом является конструкция линейного рекурсивного сдвигового регистра, основанная на арифметике в GF(2)[x], полиномиальном кольце над GF(2). Вместо сложения и умножения целых чисел, основными операциями являются исключающее ИЛИ и умножение без переноса, которое обычно реализуется как последовательность логических сдвигов. Они имеют преимущество в том, что все их биты имеют полный период; они не страдают от недостатка в младших битах, который присущ арифметике по модулю 2k. Примерами этого семейства являются генераторы xorshift и Mersenne Twister (круговорот Мерсена). Последний обеспечивает очень большой период (219937−1) и вариативную равномерность, но не проходит некоторые статистические тесты. Генераторы Фибоначчи с запаздыванием также относятся к этой категории; хотя они используют арифметическое сложение, их период обеспечивается LFSR среди наименее значащих битов. Структуру линейного рекурсивного сдвигового регистра легко обнаружить с помощью соответствующих тестов, таких как тест на линейную сложность, реализованный в пакете TestU01; булева циркулянтная матрица, инициализированная последовательными битами LFSR, никогда не будет иметь ранга, превышающего степень полинома. Добавление нелинейной функции перемешивания выходных данных (как в конструкциях xoshiro256** и пермутационного конгруэнтного генератора) может значительно улучшить результаты статистических тестов. Другая структура для PRNG – это очень простая рекуррентная функция в сочетании с мощной функцией перемешивания выходных данных. Это включает в себя блочные шифры в режиме счетчика и некриптографические генераторы, такие как SplitMix64. Структура, аналогичная LCG, но не эквивалентная ей, – это генератор множественной рекурсии: Xn = (a1Xn−1 + a2Xn−2 + ··· + akXn−k) mod m для k ≥ 2. При простом модуле это может генерировать периоды до mk−1, что является полезным расширением структуры LCG для больших периодов. Эффективным методом для генерации высококачественных псевдослучайных чисел является объединение двух или более PRNG с различной структурой; сумма LFSR и LCG (как в конструкциях KISS или xorwow) может работать очень хорошо, но с некоторой потерей скорости.