Войти
Два LCG по модулю 9 показывают, как разные параметры приводят к разной длине цикла. Каждая строка показывает состояние, развивающееся до повторения. В верхней строке показан генератор с m = 9, a = 2, c = 0 и начальным числом 1, что дает цикл длиной 6. Вторая строка - это тот же генератор с начальным числом 3, которое создает цикл. длины 2. Использование a = 4 и c = 1 (нижняя строка) дает длину цикла 9 с любым начальным числом в [0, 8]. A линейный конгруэнтный генератор (LCG ) представляет собой алгоритм , который выдает последовательность псевдослучайных чисел, вычисленных с помощью прерывного кусочно-линейного уравнения. Метод представляет собой один из старейших и наиболее известных алгоритмов генератора псевдослучайных чисел. Теорию, лежащую в основе их, относительно легко понять, и они легко и быстро реализуются, особенно на компьютерном оборудовании, которое может обеспечивать модульную арифметику путем усечения битов памяти.
Генератор определяется рекуррентным соотношением :
где 
- это целочисленные константы, которые определяют генератор. Если c = 0, генератор часто называют мультипликативным конгруэнтным генератором (MCG) или ГСЧ Лемера. Если c ≠ 0, метод называется смешанным конгруэнтным генератором .
Когда c ≠ 0, математик назовет рекуррентность аффинное преобразование, а не линейное, но неправильное употребление названия хорошо известно в информатике.
Преимущество LCG в том, что при соответствующем выборе параметров период известен и длинный. Хотя это не единственный критерий, слишком короткий период является фатальной ошибкой в генераторе псевдослучайных чисел.
В то время как LCG способны производить псевдослучайные числа, которые могут проходить формальные тесты на случайность, качество вывода чрезвычайно чувствительно к выбору параметров m и a. Например, a = 1 и c = 1 дает простой счетчик по модулю m, который имеет большой период, но явно не случайный.
Исторически неправильный выбор a приводил к неэффективной реализации LCG. Особенно показательным примером этого является RANDU, который широко использовался в начале 1970-х и привел ко многим результатам, которые в настоящее время подвергаются сомнению из-за использования этого плохого LCG.
Есть три общих семейства выбора параметров:
Это исходная конструкция Lehmer RNG. Период равен m-1, если множитель a выбран как примитивный элемент целых чисел по модулю m. Начальное состояние должно быть выбрано от 1 до m − 1.
Одним из недостатков простого модуля является то, что для модульного сокращения требуется произведение двойной ширины и шаг явного сокращения. Часто используется простое число, меньшее степени 2 (популярны простые числа Мерсенна 2−1 и 2−1), так что сокращение по модулю m = 2 - d может быть вычислено как (ax mod 2) + d ⌊ax / 2⌋. Это должно сопровождаться условным вычитанием m, если результат слишком велик, но количество вычитаний ограничено до ad / m, которое можно легко ограничить до единицы, если d мало.
Если произведение двойной ширины недоступно, а множитель выбирается тщательно, можно использовать метод Шраге . Для этого множим множитель m = qa + r, т.е. q = ⌊m / a⌋ и r = m mod a. Затем вычислите ax mod m = a (x mod q) - r ⌊x / q⌋. Поскольку x mod q < q ≤ m/a, the first term is strictly less than am/a = m. If a is chosen so that r ≤ q (and thus r/q ≤ 1), then the second term is also less than m: r ⌊x/q⌋ ≤ rx/q = x(r/q) ≤ x < m. Thus, both products can be computed with a single-width product, and the difference between them lies in the range [1−m, m−1], so can be reduced to [0, m−1] with a single conditional add.
Второй недостаток состоит в том, что неудобно преобразовать значение 1 ≤ x < m to uniform random bits. If a prime just less than a power of 2 is used, sometimes the missing values are simply ignored.
Выбор m в качестве степень 2, чаще всего m = 2 или m = 2, дает особенно эффективный LCG, потому что это позволяет вычислить операцию модуля путем простого усечения двоичного представления. Фактически, наиболее значимые биты обычно вообще не вычисляются. Однако есть и недостатки.
Эта форма имеет максимальный период m / 4, достигаемый, если ≡ 3 или 5 (mod 8). Начальное состояние X 0 должно быть нечетным, а младшие три бита X чередуются между двумя состояниями и бесполезны. Можно показать, что эта форма эквивалентна генератору с модулем в четверть размера и c 0.
Более серьезная проблема с использованием модуля степени двойки заключается в том, что младшие биты имеют более короткий период, чем старшие биты. Бит младшего разряда X никогда не изменяется (X всегда нечетный), а следующие два бита чередуются между двумя состояниями. (Если 5 (mod 8), то бит 1 никогда не изменяется, а бит 2 чередуется. Если 3 (mod 8), то бит 2 никогда не изменяется, а бит 1 чередуется.) Бит 3 повторяется с периодом 4, бит 4 имеет период 8 и так далее. Только самый старший бит X достигает полного периода.
Когда c ≠ 0, правильно выбранные параметры допускают период, равный m, для всех начальных значений. Это произойдет тогда и только тогда, когда :
и 
являются относительно простыми,
делится на все простые множители из ,делится на 4, если делится на 4.Эти три требования называются теоремой Халла – Добелла.
Эта форма может использоваться с любым m, но хорошо работает только для m с множеством повторяющихся простых множителей, таких как степень двойки; использование компьютерного размера слова является наиболее распространенным выбором. Если бы m было целым числом без квадратов, это позволило бы только ≡ 1 (mod m), что дает очень плохой ГПСЧ; выбор возможных полнопериодных множителей доступен только тогда, когда m имеет повторяющиеся простые множители.
Хотя теорема Халла – Добелла дает максимальный период, этого недостаточно, чтобы гарантировать хороший генератор. Например, желательно, чтобы a - 1 не делилось на простые множители m больше, чем необходимо. Таким образом, если m является степенью 2, тогда a - 1 должно делиться на 4, но не делиться на 8, то есть a 5 (mod 8).
Действительно, большинство умножителей создают последовательность, которая не соответствует единице. проверка на неслучайность или что-то еще, и найти множитель, удовлетворяющий всем применимым критериям, довольно сложно. спектральный тест - один из наиболее важных тестов.
Обратите внимание, что модуль степени двойки разделяет проблему, описанную выше для c = 0: младшие биты k образуют генератор с модулем 2 и, таким образом, повторить с периодом 2; только самый старший бит достигает полного периода. Если требуется псевдослучайное число меньше r, ⌊rX / m⌋ - результат гораздо более высокого качества, чем X mod r. К сожалению, большинство языков программирования значительно упрощают написание последнего (X% r), поэтому это наиболее часто используемая форма.
Генератор нечувствителен к выбору c, пока он является относительно простым по модулю (например, если m является степенью 2, то c должно быть нечетным), поэтому значение c = 1 обычно выбирается.
Ряд, образованный другим выбором c, может быть записан как простая функция ряда, когда c = 1. В частности, если Y является прототипной серией, определяемой Y 0 = 0 и Y n + 1 = aY n +1 mod m, тогда общая серия X n + 1 = aX n + c mod m может быть записано как аффинная функция от Y:
В более общем смысле, любые две серии X и Z с одинаковым множителем и модулем связаны соотношением
В следующей таблице перечислены общие параметры LCG использование, включая встроенные функции rand () в библиотеках времени выполнения различных компиляторов. Эта таблица показывает популярность, а не примеры для подражания; многие из этих параметров плохие. Доступны таблицы хороших параметров.
| Источник | модуль. m | множитель. a | приращение. c | выходные биты начального числа в rand () или Random (L) |
|---|---|---|---|---|
| Числовые рецепты | 2³² | 1664525 | 1013904223 | |
| Borland C / C ++ | 2³² | 22695477 | 1 | бит 30..16 рандомных (), 30..0 в lrand () |
| glibc (используется GCC ) | 2³¹ | 1103515245 | 12345 | биты 30..0 |
| ANSI C : Watcom, Digital Mars, CodeWarrior, IBM VisualAge C / C ++. C90, C99, C11 : Предложение в ISO / IEC 9899, C18 | 2³¹ | 1103515245 | 12345 | бит 30..16 |
| Borland Delphi, Virtual Pascal | 2³² | 134775813 | 1 | бит 63..32 из (семя × L) |
| Turbo Pascal | 2³² | 134775813 (8088405₁₆) | 1 | |
| Microsoft Visual / Quick C / C ++ | 2³² | 214013 (343FD₁₆) | 2531011 (269EC3₁₆) | бит 30..16 |
| Microsoft Visual Basic (6 и более ранние версии) | 2²⁴ | 1140671485 (43FD43FD₁₆) | 12820163 (C39EC3₁₆) | |
| RtlUniform из Native API | 2³¹ - 1 | 2147483629 (7FFFFFED₁₆) | 21FF47FC483587₁₆ (7FFFFFED₁₆)) | |
Apple CarbonLib, C ++ 11 's minstd_rand0 | 2³¹ - 1 | 16807 | 0 | см. MINSTD |
C ++ 11 minstd_rand | 2³¹ - 1 | 48271 | 0 | см. MINSTD |
| MMIX от Дональда Кнута | 2⁶⁴ | 6364136223846793005 | 1442695040888963407 | |
| Newlib, Musl | 2⁶⁴ | 6364136223846793005 | 1 | биты 63..32 |
| VMS MTH $ RANDOM, старые версии glibc | 2³² | 69069 (10DCD₁₆) | 1 | |
| Java java.util.Random, POSIX [ln] rand48, glibc [lnhibitedrand48[_r provided | 2⁴⁸ | 25214903917 (5DEECE66D₁₆) | 11 | бит 47..16 |
| 134456 = 2³7⁵ | 8121 | 28411 |  |
| POSIX [jm] rand48, glibc [mj visiblerand48[_r provided | 2⁴⁸ | 25214903917 (5DEECE66D₁₆) | 11 | биты 47..15 |
| POSIX [de] rand48, glibc [de providedrand48[_r provided | 2⁴⁸ | 25214903917 (5DEECE66D₁₆) | 11 | биты 47..0 |
| cc65 | 2²³ | 65793 (10101₁₆) | 4282663 (415927₁₆) | биты 22..8 |
| cc65 | 2³² | 16843009 (1010101₁₆) | 826366247 (31415927₁₆) | биты 31..16 |
| Ранее распространенное: RANDU | 2³¹ | 65539 | 0 |
Как показано выше, LCG не всегда используют все биты в создаваемых ими значениях. Например, реализация Java работает с 48-битными значениями на каждой итерации, но возвращает только 32 их наиболее значимых бита. Это связано с тем, что биты более высокого порядка имеют более длительные периоды, чем биты более низкого порядка (см. Ниже). Группы LCG, использующие этот метод усечения, дают статистически лучшие значения, чем те, которые этого не делают. Это особенно заметно в сценариях, которые используют операцию мода для уменьшения диапазона; изменение случайного числа по модулю 2 приведет к чередованию 0 и 1 без усечения.
LCG быстрые и требуют минимального объема памяти (одно число по модулю m, часто 32 или 64 бита) для сохранения состояния. Это делает их ценными для моделирования нескольких независимых потоков. LCG не предназначены и не должны использоваться для криптографических приложений; использовать криптографически безопасный генератор псевдослучайных чисел для таких приложений.
Гиперплоскости линейного конгруэнтного генератора в трех измерениях. Эта структура и является тем, что измеряет спектральный тест. Хотя LCG имеют несколько специфических недостатков, многие из их недостатков происходят из-за слишком малого состояния. Тот факт, что людей на протяжении стольких лет убаюкивали, заставляя использовать их с такими маленькими модулями, можно рассматривать как свидетельство силы этой техники. LCG с достаточно большим состоянием может пройти даже строгие статистические тесты; LCG по модулю 2, который возвращает старшие 32 бита, проходит пакет SmallCrush TestU01, а 96-битный LCG передает самый строгий пакет BigCrush.
Для конкретного примера идеальный Ожидается, что генератор случайных чисел с 32-битным выходом (согласно теореме о дне рождения ) начнет дублировать более ранние выходные данные после √m ≈ 2 результатов. Любой ГПСЧ, выход которого является его полным, неотрезанным состоянием, не будет создавать дубликатов, пока не истечет его полный период, что легко обнаруживается статистической ошибкой. По связанным причинам любой ГПСЧ должен иметь период, превышающий квадрат количества требуемых выходов. С учетом скоростей современных компьютеров это означает период 2 для всех, кроме наименее требовательных приложений, и более длительный период для требовательных симуляций.
Один недостаток, характерный для LCG, заключается в том, что при использовании для выбора точек в n-мерном пространстве точки будут лежать не более чем на √n! ⋅m гиперплоскостях (, разработано Автор Джордж Марсалья ). Это связано с последовательной корреляцией между последовательными значениями последовательности X n. Неосторожно выбранные множители обычно имеют гораздо меньше и широко разнесенных плоскостей, что может привести к проблемам. Спектральный тест , который представляет собой простой тест качества LCG, измеряет этот интервал и позволяет выбрать хороший множитель.
Расстояние между плоскостями зависит как от модуля, так и от множителя. Достаточно большой модуль может уменьшить это расстояние ниже разрешения чисел двойной точности. Выбор множителя становится менее важным, когда модуль упругости велик. По-прежнему необходимо рассчитать спектральный индекс и убедиться, что множитель не плохой, но с чисто вероятностной точки зрения крайне маловероятно встретить плохой множитель, когда модуль больше примерно 2.
Еще один недостаток Специфическим для LCG является короткий период младших битов, когда m выбирается равным степени 2. Это можно уменьшить, используя модуль, превышающий требуемый выходной сигнал, и старшие значащие биты состояния.
Тем не менее, для некоторых приложений LCG может быть хорошим вариантом. Например, во встроенной системе объем доступной памяти часто сильно ограничен. Точно так же в такой среде, как игровая консоль, вполне может быть достаточно приема небольшого числа старших битов LCG. (На младшие биты LCG, когда m является степенью 2, никогда не следует полагаться на какую-либо степень случайности.) Младшие биты проходят очень короткие циклы. В частности, любая LCG полного цикла, когда m равно степени 2, будет давать поочередно нечетные и четные результаты.
LCG следует очень тщательно оценивать на предмет пригодности для некриптографических приложений, где важна высококачественная случайность. Для моделирования методом Монте-Карло LCG должен использовать модуль, больший и предпочтительно намного больший, чем куб количества требуемых случайных выборок. Это означает, например, что (хороший) 32-битный LCG можно использовать для получения около тысячи случайных чисел; 64-битный LCG подходит примерно для 2 случайных выборок (чуть более двух миллионов) и т. д. По этой причине на практике LCG не подходят для крупномасштабного моделирования методом Монте-Карло.
Ниже представлена реализация LCG в Python :
def lcg (modulus, a, c, seed): "" "Линейный конгруэнтный генератор. "" "while True: seed = (a * seed + c)% модуль yield seed
Free Pascal использует Mersenne Twister в качестве псевдослучайного числа по умолчанию генератор, тогда как Delphi использует LCG. Вот пример, совместимый с Delphi в Free Pascal, основанный на информации в таблице выше. При том же значении RandSeed он генерирует ту же последовательность случайных чисел, что и Delphi.
единица lcg_random; {$ ifdef fpc} {$ mode delphi} {$ endif} интерфейсная функция LCGRandom: extended; перегрузка; встроенный; функция LCGRandom (диапазон констант: longint): longint; перегрузка; встроенный; функция реализации IM: кардинальный; встроенный; начало RandSeed: = RandSeed * 134775813 + 1; Результат: = RandSeed; конец; функция LCGRandom: расширенная; перегрузка; встроенный; begin Результат: = IM * 2.32830643653870e-10; конец; функция LCGRandom (диапазон констант: longint): longint; перегрузка; встроенный; begin Результат: = IM * range shr 32; конец;Как и все генераторы псевдослучайных чисел, LCG должен сохранять состояние и изменять его каждый раз, когда генерирует новое число. Несколько потоков могут получить доступ к этому состоянию, одновременно вызывая состояние гонки. Реализации должны использовать разные состояния, каждое с уникальной инициализацией для разных потоков, чтобы избежать одинаковых последовательностей случайных чисел при одновременном выполнении потоков.
Существует несколько генераторов, которые являются линейными конгруэнтными генераторами в другой форме, и, следовательно, к ним можно применить методы, используемые для анализа LCG.
Один метод получения более длительного периода - это суммирование выходных данных нескольких LCG разных периодов, имеющих большое наименьшее общее кратное ; Генератор Вихмана – Хилла является примером такой формы. (Мы бы предпочли, чтобы они были полностью взаимно простыми, но простой модуль подразумевает четный период, поэтому должен быть общий множитель, по крайней мере, 2). Можно показать, что это эквивалентно одному LCG с модулем, равным произведению составляющих модулей LCG.
Марсаглия добавляет-с-переносом и вычитает-с-заимством PRNG с размером слова b = 2 и лагами r и s (r>s) эквивалентны LCG с модуль b ± b ± 1.
Умножение с переносом ГПСЧ с множителем a эквивалентны LCG с большим простым модулем ab-1 и множителем степени двойки b.
A конгруэнтный генератор с перестановками начинается с LCG степени двойки и применяет выходное преобразование для устранения проблемы короткого периода в битах младшего разряда.
Другим широко используемым примитивом для получения долгопериодических псевдослучайных последовательностей является конструкция регистра сдвига с линейной обратной связью, которая основана на арифметике в GF ( 2) [x], кольцо полиномов над GF (2). Вместо сложения целых чисел и умножения основными операциями являются исключающее ИЛИ и умножение без переноса, которое обычно реализуется как последовательность логических сдвигов. У них есть то преимущество, что все их биты полнопериодные; они не страдают от слабости младших битов, которая мешает арифметике по модулю 2.
Примеры этого семейства включают генераторы xorshift и твистер Мерсенна. Последний обеспечивает очень длительный период (2-1) и варьирует однородность, но он не проходит некоторые статистические тесты. Генераторы Фибоначчи с запаздыванием также попадают в эту категорию; хотя они используют арифметическое сложение, их период обеспечивается LFSR среди младших битов.
Структуру сдвигового регистра с линейной обратной связью легко обнаружить с помощью соответствующих тестов, таких как тест линейной сложности, реализованный в пакете TestU01 ; логическая циркулянтная матрица, инициализированная из последовательных битов LFSR, никогда не будет иметь rank выше степени полинома. Добавление нелинейной функции микширования выходного сигнала (как в конструкциях xoshiro256 ** и конгруэнтного генератора с перестановками ) может значительно улучшить производительность статистических тестов.
Другая структура PRNG - это очень простая функция повторения в сочетании с мощной функцией микширования выходного сигнала. Это включает в себя режим счетчика блочные шифры и некриптографические генераторы, такие как SplitMix64.
Структура, похожая на LCG, но не эквивалентная, является мультирекурсивным генератором: X n = (a 1Xn − 1 + a 2Xn − 2 + ··· + a kXn − k) mod m для k ≥ 2. С простым по модулю, это может генерировать периоды до m-1, поэтому это полезное расширение структуры LCG на большие периоды.
Мощный метод генерации высококачественных псевдослучайных чисел состоит в объединении двух или более ГПСЧ разной структуры; сумма LFSR и LCG (как в конструкциях KISS или xorwow ) может очень хорошо работать при некоторой потере скорости.
