Меню

Линейный генератор для псевдослучайных чисел



Генерация случайных чисел

Дата создания: 2009-05-03 15:27:38
Последний раз редактировалось: 2012-02-08 06:53:25

Очень часто при разработке программ возникает необходимость в последовательности случайных чисел. В играх, последовательность случайных чисел может использоваться в разнообразнейших ситуациях: создание монстров, генерация территории, поведение искусственного интеллекта.

Вместо использования в программах последовательности чисел, подчиняющихся какому-либо закону, во многих случаях лучше использовать случайно сгенерированные.

Генерация псевдослучайных чисел

Обычно используется генерация псевдослучайных чисел. Т.е. числа не совсем случайные. Мы уже рассматривали функцию rand(). Если Вы напишите программу использующую данную функцию, то при каждом запуске программы, rand() будет генерировать одну и ту же последовательность чисел. Последовательность сгенерированная rand() определяется начальным числом (seed). Сначала задаётся начальное число, затем, по определённой формуле вичисляются все остальные числа последовательности. Зная начальное число и формулу по которой рассчитываются числа, можно вычислить следующее число.

Такие алгоритмы называются детерминистическими (предопределёнными). Т.е. в них последовательность чисел создаётся на основе начальных данных. При этом последовательность чисел — псевдослучайная: т.е. зная начальное число, можно узнать и все следующие. Но пользователь навряд ли их узнает, числа будут казаться случайными.

Одним из предопределённых (детерминистических) алгоритмов создания случайных чисел является линейно-конгруэнтный.

Установка начального значения (для функции rand(), которую мы использовали до сих пор) выглядит примерно так:

Функция srnd устанавливает начальное значение i.

Линейный конгруэнтный (linear congruential) метод генерации случайных чисел

Существует много методов генерации случайных чисел. Линейно-конгруэнтный лишь один из них. Метод довольно старый — 1950х годов. Разработал его Деррик Лемер.

Для реализации алгоритма необходиом задать четыре параметра:

Диапазон значений m, при этом m > 0.
Множитель a (0 = 2, b >= 1.

Вичислим шестой элемент с помощью этой формулы (мы ведь уже знаем пятый):

X5+1 = (a*1*X5 + (a*1-1)*c/b) % m = (2*1*5 + (2*1-1)*3/1) % 10 = 13 % 10 = 3

Всё росто, правда?

У последовательности созданной с помощью линейного конгруэнтного метода и определённой целыми параметрами m, a, c и X, период равен числу m когда выполняются следующие условия:
1.Наибольший общий делитель c и m равен 1.
2.b — кратно любому простому числу, являющемуся делителем m.
3.Если m кратно 4, тогда b также кратно 4.

Выбор m

Период не может быть больше числа m. Следовательно m должно быть довольно большим.

Примеры (x — целое число):

Очень часто для m выбирают одно из простых чисел Мерсенна [3] . Часто число 2 31 — 1 используется, когда вычисления ведутся с 32-ух битными данными.

Множитель a

Множитель нужно выбирать так, чтобы период был как можно длиннее. Существует серьёзная проблема с данным коэффициентом: при малых значениях a, если текущий элемент последовательности достаточно мал, вполне вероятно, что следующий элемент тоже будет маленьким.

Инкремент c

Данный параметр можно выбирать довольно произвольно. Очень часто его задают в виде нуля, но при этом уменьшается длина периода и X != 0.

Начальное значение (seed)

Итак, мы выяснили, что в последовательности есть период. В нашем примере период равен всего четырём элементам. В других случаях период может быть очень большим, но он всегда есть! То есть при генерации случайных чисел линейным конгруэнтным методом если нам нужна очень большая последовательность, то в ней значения будут повторяться с определённой периодичностью.

Вот так вот! Генерация последовательных чисел — это самая настоящая мистификация!

Т.е. у нас допустим есть генератор случайных чисел. Мы его используем для разных программ. Всегда, всегда этот генератор создаёт одинаковую последовательность чисел (при одинаковых начальных значениях). Мы можем только установить начальное значение.

Вообще говоря, с помощью арифметических методов нельзя построить по настоящему случайную последовательность чисел. Как невесело шутил наш друг — Джон Фон Нейман:

«Anyone who uses arithmetic methods to produce random numbers is in a state of sin.» (C) Джон Фон Нейман.

Грустно всё это. Вот так живёшь-живёшь. Находясь в состоянии неведения, думаешь: «А вот круто бы было создать генератор случайных чисел на основе линейного когнруэнтного метода!». А оказывается что по настоящему случайную последовательность таким образом создать нельзя. Крах надежд! Депрессия и вот ты уже на пороге первой стадии алкоголизма. Этот груз невозможности реализовать свои желания будет давить на тебя всю оставшуюся жизнь. Что-то я отвлёкся. Продолжим.

Реализация генерации случайных чисел

Теперь, когда мы рассмотрели теоретические вопросы, касающиеся генераторов случайных чисел, давайте посмотрим на реализацию, тем более она довольно проста.

Для последовательности рассмотренной выше, генератор будет выглядеть так:

X объявляется как глобальная переменная:

Это самый примитивный вариант генератора. В реальности такое чудовище использовать нельзя! Но мы будем это делать!

В данной реализации мы никак не отслеживаем возможность переполнения переменных. Вместо типа int используйте тип _int64 — это целый восьмибайтный тип.

Простые числа

Простые числа — числа которые можно разделить без остатка только на единицу и на само число. Например: 11, 3, 7.

Код Грея

[1] Код Грея представляет собой последовательность чисел, где следующее число отличается от предыдущей одним битом. Т.е. чтобы угадать последовательность, нужно смотреть не на десятичные числа, а на их двоичные эквиваленты.

Вот возрастающая последовательность чисел от 0 до 7 в двоичном коде:

Используя код Грея, получим такую последовательность:

Простые числа Мерсенна

[3] На данный момент известно 44 числа Мерсенна. Из названия понятно, что данные числа — простые, т.е. делятся только на единицу и на самих себя. Кроме того данные числа должны подчиняться следующей формуле:

Где n также простое число. Для первых девяти простых чисел Мерсенна n следующие: <2, 3, 5, 7, 13, 17, 19, 31, 61>.

Поразрядные логические операции

[2] Мы уже рассматривали логические операции && (И) и || (ИЛИ). Существуют также поразрядные логические операции & (поразрядное И) и | (поразрядное ИЛИ). Работате операция следующим образом:

То есть в данной операции сравниваются соответствующие позиции двух чисел и если они равны, то в результируюем числе в данной позиции пишется 1, в противном случае — ноль.

Степень числа

Другие генераторы случайных чисел

Кроме линейного конгруэнтного генератора существует множество других. Например Вихрь Мерсенна, изобретённый двумя японскими учёными (непомню как из зовут) в 1997. У него очень большой (очень большой это мягко сказано) период. Кстати, вихрь Мерсенна использует линейный конгруэнтный генератор для установления начального значения (seed).

Читайте также:  Дизель генератор cat 3406

Генераторы случайных чисел применяются при шифровании. Но здесь используются специальные генераторы — криптографически защищённые генераторы псевдослучайных чисел. Например блочный шифр (block cipher), потоковый шифр (stream cipher), который был разработан на основе шифра Вернама.

Упражнения:

Реализуйте генераторы случайных чисел на основе линейного когруэнтного метода. В качестве параметров воспользуйтесь следующими:

  • m = 2 32 ; a = 1664525; c = 1013904223. Данные параметры использовались в примере реализации генератора в одной старой книжке по Фортрану.
  • m = 2 32 ; a= 214013; c = 2531011; Данные параметры используется в реализации метода в Visual C++. При этом берутся старшие биты 30..16. Берутся именно верхние биты, т.к. в линейном конгруэнтном методе нижние биты гораздо менее случайны. Так как мы пока не умеем брать конкретные биты, можете использовать всё число.
  • В качестве m выберите одно из чисел Мерсенна. Начните с малых (2 3 -1,2 5 -1). Попробуйте подставить 2 31 -1 и 2 61 -1.

Данный материал поможет вам понять как работают генераторы случайных чисел. К этому материалу будет продолжение: мы напишем нормальный генератор и рассмотрим различные приёмы работы с генераторами псевдослучайных чисел.

Источник

Линейный конгруэнтный генератор — Linear congruential generator

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

Икс п + 1 знак равно ( а Икс п + c ) мод м <\ displaystyle X_ = \ left (aX_ + c \ right) <\ bmod >>

где — последовательность псевдослучайных значений, а Икс <\ displaystyle X>

м , 0 м <\ Displaystyle м, \, 0 — « модуль » а , 0 а м <\ Displaystyle а, \, 0 — «множитель» c , 0 ≤ c м <\ displaystyle c, \, 0 \ leq c — «приращение» Икс 0 , 0 ≤ Икс 0 м <\ Displaystyle X_ <0>, \, 0 \ leq X_ <0> — «начальное значение» или «начальное значение»

— целочисленные константы, определяющие генератор. Если c = 0, генератор часто называют мультипликативным конгруэнтным генератором (MCG) или Lehmer RNG . Если c ≠ 0, метод называется смешанным конгруэнтным генератором .

Когда c ≠ 0, математик назвал бы рекуррентное преобразование аффинным преобразованием , а не линейным , но это неправильное название хорошо известно в информатике.

СОДЕРЖАНИЕ

История

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

Продолжительность периода

Преимущество LCG в том, что при соответствующем выборе параметров период известен и длительный. Хотя это не единственный критерий, слишком короткий период является фатальной ошибкой в ​​генераторе псевдослучайных чисел.

Хотя LCG могут генерировать псевдослучайные числа, которые могут пройти формальные тесты на случайность , качество вывода чрезвычайно чувствительно к выбору параметров m и a . Например, a = 1 и c = 1 дает простой счетчик по модулю m , который имеет большой период, но, очевидно, не является случайным.

Исторически неправильный выбор a приводил к неэффективному внедрению LCG. Особенно показательным примером этого является RANDU , который широко использовался в начале 1970-х годов и привел ко многим результатам, которые в настоящее время подвергаются сомнению из-за использования этого плохого LCG.

Существует три основных семейства выбора параметров:

m простое, c = 0

Это оригинальная конструкция Lehmer RNG. Период равен m -1, если множитель a выбран как примитивный элемент целых чисел по модулю m . Начальное состояние должно быть выбрано от 1 до m -1.

Одним из недостатков простого модуля является то, что для модульного сокращения требуется произведение двойной ширины и явный шаг редукции. Часто используется простое число, меньшее степени двойки (популярны простые числа Мерсенна 2 31 −1 и 2 61 −1), так что сокращение по модулю m = 2 ed может быть вычислено как ( ax mod 2 e ) + dax / 2 e ⌋. За этим должно следовать условное вычитание m, если результат слишком велик, но количество вычитаний ограничено до ad / m , которое можно легко ограничить до единицы, если d мало.

Если продукт двойной ширины недоступен, а множитель выбран тщательно, можно использовать метод Шраге . Для этого множим множитель m = qa + r , т.е. q = ⌊ m / a ⌋ и r = m mod a . Затем вычислите ax mod m = a ( x mod q ) — rx / q ⌋ . Поскольку x mod q m степень двойки, c = 0

Выбор m в качестве степени 2 , чаще всего m = 2 32 или m = 2 64 , дает особенно эффективную LCG, потому что это позволяет вычислить операцию модуля путем простого усечения двоичного представления. Фактически, наиболее значимые биты обычно вообще не вычисляются. Однако есть и недостатки.

Эта форма имеет максимальный период m / 4, достигаемый, если a 3 или a 5 (mod 8). Начальное состояние X должно быть нечетным, а младшие три бита X чередуются между двумя состояниями и бесполезны. Можно показать, что эта форма эквивалентна генератору с модулем в четверть размера и c ≠ 0.

Более серьезная проблема с использованием модуля степени двойки заключается в том, что младшие биты имеют более короткий период, чем старшие биты. Младший бит X никогда не изменяется ( X всегда нечетный), а следующие два бита чередуются между двумя состояниями. (Если ≡ 5 ( по модулю 8), то бит 1 никогда не изменяется и бит 2 заместителей. Если ≡ 3 ( по модулю 8), а затем бит 2 никогда не меняется , и бит 1 чередуется.) Бит 3 повторяется с периодом 4, битрейт 4 имеет период 8 и так далее. Только самый старший бит X достигает полного периода.

Когда c ≠ 0, правильно выбранные параметры допускают период, равный m , для всех начальных значений. Это произойдет тогда и только тогда, когда :

  1. м <\ displaystyle m>и являются взаимно простыми , c <\ displaystyle c>
  2. а — 1 <\ displaystyle a-1>делится на все простые множители из , м <\ displaystyle m>
  3. а — 1 <\ displaystyle a-1>делится на 4, если делится на 4. м <\ displaystyle m>

Эти три требования называются теоремой Халла – Добелла.

Эта форма может использоваться с любым m , но хорошо работает только для m со многими повторяющимися простыми множителями, такими как степень двойки; использование компьютерного размера слова — наиболее распространенный выбор. Если м были бесквадратно целым числом , это позволило бы только к = 1 ( по модулю т ), что делает очень плохую PRNG; выбор возможных множителей полного периода доступен только тогда, когда m имеет повторяющиеся простые множители.

Хотя теорема Халла – Добелла дает максимальный период, этого недостаточно, чтобы гарантировать хороший генератор. Например, желательно, чтобы a — 1 не делилось на простые множители m больше, чем необходимо. Таким образом, если m является степенью 2, то a — 1 должно делиться на 4, но не делиться на 8, то есть a 5 (mod 8).

Действительно, большинство множителей создают последовательность, которая не проходит ни один тест на неслучайность, ни другой, и найти множитель, удовлетворяющий всем применимым критериям, довольно сложно. Спектральный тест является одним из наиболее важных тестов.

Обратите внимание, что модуль степени 2 разделяет проблему, описанную выше для c = 0: младшие биты k образуют генератор с модулем 2 k и, таким образом, повторяются с периодом 2 k ; только самый старший бит достигает полного периода. Если требуется псевдослучайное число меньше r , ⌊ rX / m ⌋ — результат гораздо более высокого качества, чем X mod r . К сожалению, большинство языков программирования значительно упрощают написание последнего ( X % r ), поэтому это наиболее часто используемая форма.

Генератор не чувствителен к выбору с тех пор, как это взаимно простое с модулем (например , если т является степенью 2, то с должно быть нечетным), так что значение с = 1 обычно выбирается.

Ряд, произведенный другим выбором c, может быть записан как простая функция ряда, когда c = 1. В частности, если Y — прототипный ряд, определенный как Y = 0 и Y n +1 = aY n +1 mod m, то общий ряд X n +1 = aX n + c mod m может быть записан как аффинная функция от Y :

Икс п знак равно ( Икс 0 ( а — 1 ) + c ) Y п + Икс 0 знак равно ( Икс 1 — Икс 0 ) Y п + Икс 0 ( мод м ) . <\ displaystyle X_ = (X_ <0>(a-1) + c) Y_ + X_ <0>= (X_ <1>-X_ <0>) Y_ + X_ <0 ><\ pmod >.>

В более общем смысле, любые две серии X и Z с одним и тем же множителем и модулем связаны соотношением

Икс п — Икс 0 Икс 1 — Икс 0 знак равно Y п знак равно а п — 1 а — 1 знак равно Z п — Z 0 Z 1 — Z 0 ( мод м ) . <\ Displaystyle -X_ <0>\ над X_ <1>-X_ <0>> = Y_ = -1 \ over a-1> = -Z_ <0>\ over Z_ <1>-Z_ <0>> <\ pmod >.>

Параметры в общем использовании

В следующей таблице перечислены параметры часто используемых LCG, включая встроенные функции rand () в библиотеках времени выполнения различных компиляторов . Эта таблица показывает популярность, а не примеры для подражания; многие из этих параметров плохие. Доступны таблицы хороших параметров.

Источник модуль упругости
м
множитель
а
приращение
c
выходные биты семени в rand () или Random (L)
Числовые рецепты 2³² 1664525 1013904223
Borland C / C ++ 2³² 22695477 1 биты 30..16 в rand () , 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 , Виртуальный Паскаль 2³² 134775813 1 биты 63..32 из (начальное число × L)
Турбо Паскаль 2³² 134775813 (8088405₁₆) 1
Microsoft Visual / Quick C / C ++ 2³² 214013 (343FD₁₆) 2531011 (269EC3₁₆) бит 30..16
Microsoft Visual Basic (6 и более ранние версии) 2 24 1140671485 (43FD43FD₁₆) 12820163 (C39EC3₁₆)
RtlUniform из собственного API 2³¹ — 1 2147483629 (7FFFFFED₁₆) 2147483587 (7FFFFFC3₁₆)
Apple , CarbonLib , C ++ 11 «s minstd_rand0 2³¹ — 1 16807 см. MINSTD
C ++ 11 «s minstd_rand 2³¹ — 1 48271 см. MINSTD
MMIX от Дональда Кнута 2⁶⁴ 6364136223846793005 1442695040888963407
Ньюлиб , Мусл 2⁶⁴ 6364136223846793005 1 биты 63..32
VMS «S MTH $ RANDOM , старые версии Glibc 2³² 69069 (10DCD₁₆) 1
Java java.util.Random, POSIX [ln] rand48, glibc [ln] rand48 [_r] 2⁴⁸ 25214903917 (5DEECE66D₁₆) 11 биты 47..16
134456 = 2³7⁵ 8121 28411 Икс п 134456 <\ displaystyle <\ frac > <134456>>>
POSIX [jm] rand48, glibc [mj] rand48 [_r] 2⁴⁸ 25214903917 (5DEECE66D₁₆) 11 биты 47..15
POSIX [de] rand48, glibc [de] rand48 [_r] 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

Как показано выше, LCG не всегда используют все биты в создаваемых ими значениях. Например, реализация Java работает с 48-битными значениями на каждой итерации, но возвращает только 32 их наиболее значимых бита. Это связано с тем, что биты более высокого порядка имеют более длинные периоды, чем биты более низкого порядка (см. Ниже). LCG, использующие этот метод усечения, дают статистически лучшие значения, чем те, которые этого не делают. Это особенно заметно в сценариях, которые используют операцию мода для уменьшения диапазона; изменение случайного числа по модулю 2 приведет к чередованию 0 и 1 без усечения.

Преимущества и недостатки

LCGs быстро и требуют минимальной памяти (один modulo- м число, часто 32 или 64 бит) , чтобы сохранить состояние. Это делает их ценными для моделирования нескольких независимых потоков. LCG не предназначены и не должны использоваться для криптографических приложений; использовать для таких приложений криптографически безопасный генератор псевдослучайных чисел .

Хотя у LCG есть несколько специфических недостатков, многие из их недостатков связаны с слишком маленьким государством. Тот факт, что людей так много лет убаюкивали, заставляя использовать их с такими маленькими модулями, можно рассматривать как свидетельство силы этой техники. LCG с достаточно большим состоянием может пройти даже строгие статистические тесты; LCG по модулю 2, который возвращает старшие 32 бита, проходит пакет SmallCrush TestU01, а 96-битный LCG проходит самый строгий пакет BigCrush.

В конкретном примере ожидается, что идеальный генератор случайных чисел с 32-битным выходом (по теореме о дне рождения ) начнет дублировать более ранние выходные данные после √ m ≈ 2 16 результатов. Любой ГПСЧ, выход которого является его полным, неотрезанным состоянием, не будет создавать дубликатов, пока не истечет его полный период, что легко обнаруживается статистической ошибкой. По связанным причинам любой ГПСЧ должен иметь период, превышающий квадрат количества требуемых выходов. Учитывая скорость современных компьютеров, это означает период 2 64 для всех, кроме наименее требовательных приложений, и более длительный период для требовательных симуляций.

Один недостаток, характерный для LCG, заключается в том, что, если они используются для выбора точек в n-мерном пространстве, точки будут лежать не более чем на nn ! ⋅ m гиперплоскостях ( теорема Марсальи , разработанная Джорджем Марсалья ). Это связано с последовательной корреляцией между последовательными значениями последовательности X n . Неосторожно выбранные множители обычно имеют гораздо меньше и широко разнесенных плоскостей, что может привести к проблемам. Спектральный тест , который представляет собой простой тест качества лвга, в мерах , это расстояние и позволяют хороший Умножитель быть выбран.

Расстояние между плоскостями зависит как от модуля, так и от множителя. Достаточно большой модуль может уменьшить это расстояние ниже разрешения чисел двойной точности. Выбор множителя становится менее важным, когда модуль упругости велик. По-прежнему необходимо рассчитать спектральный индекс и убедиться, что множитель не плохой, но чисто вероятностно становится крайне маловероятным встретить плохой множитель, когда модуль больше, чем примерно 2 64 .

Другой недостаток, характерный для LCG, — это короткий период младших битов, когда m выбирается равным степени 2. Это можно смягчить, используя модуль, превышающий требуемый выходной сигнал, и используя наиболее значимые биты состояния.

Тем не менее, для некоторых приложений LCG может быть хорошим вариантом. Например, во встроенной системе объем доступной памяти часто сильно ограничен. Точно так же в такой среде, как игровая приставка , вполне может хватить небольшого количества старших битов LCG. (Младшие биты LCG, когда m является степенью двойки, никогда не следует полагаться на какую-либо степень случайности.) Младшие биты проходят очень короткие циклы. В частности, любая LCG полного цикла, когда m является степенью 2, будет давать поочередно нечетные и четные результаты.

LCG следует очень тщательно оценивать на предмет пригодности для некриптографических приложений, где важна качественная случайность . Для моделирования методом Монте-Карло LCG должен использовать модуль, больший и предпочтительно намного больший, чем куб количества требуемых случайных выборок. Это означает, например, что (хороший) 32-битный LCG можно использовать для получения около тысячи случайных чисел; 64-битный LCG подходит примерно для 2 21 случайных выборок (чуть более двух миллионов) и т. д. По этой причине на практике LCG не подходят для крупномасштабного моделирования методом Монте-Карло.

Пример кода Python

Ниже представлена ​​реализация LCG на Python :

Пример кода Free Pascal

Free Pascal использует Mersenne Twister в качестве генератора псевдослучайных чисел по умолчанию, тогда как Delphi использует LCG. Вот пример, совместимый с Delphi в Free Pascal, основанный на информации в таблице выше. При том же значении RandSeed он генерирует ту же последовательность случайных чисел, что и Delphi.

Как и все генераторы псевдослучайных чисел, LCG необходимо сохранять состояние и изменять его каждый раз, когда генерирует новое число. Несколько потоков могут получить доступ к этому состоянию, одновременно вызывая состояние гонки. Реализации должны использовать разные состояния, каждое с уникальной инициализацией для разных потоков, чтобы избежать одинаковых последовательностей случайных чисел при одновременном выполнении потоков.

Производные LCG

Есть несколько генераторов, которые являются линейными конгруэнтными генераторами в другой форме, и поэтому к ним можно применить методы, используемые для анализа LCG.

Один из методов получения более длительного периода состоит в суммировании выходных данных нескольких LCG разных периодов, имеющих наибольшее наименьшее общее кратное ; Вихманн-Хилл генератор является примером этой формы. (Мы бы предпочли, чтобы они были полностью взаимно простыми , но простой модуль подразумевает четный период, поэтому должен быть общий множитель, по крайней мере, 2). Можно показать, что это эквивалентно одному LCG с модулем, равным произведение компонентных модулей LCG.

ГПСЧ «сложение с переносом и вычитание с заимствованием» Марсальи с размером слова b = 2 w и запаздыванием r и s ( r > s ) эквивалентны LCG с модулем b r ± b s ± 1.

Умножение-с-переноской PRNGs с множителем эквивалентны LCGs с большим простым модулем аб г -1 и мощность из-2 множителя б .

Переставляются конгруэнтный генератор начинается с включения питания из-2-модуля LCG и применяет выходное преобразование , чтобы устранить проблему короткий период в битах низкого порядка.

Сравнение с другими ГПСЧ

Другой широко используемый примитив для получения долгопериодических псевдослучайных последовательностей — это конструкция регистра сдвига с линейной обратной связью , которая основана на арифметике в GF (2) [ x ], кольце многочленов над GF (2) . Вместо сложения целых чисел и умножения основными операциями являются умножение с использованием исключающего ИЛИ и без переноса , которое обычно реализуется как последовательность логических сдвигов . У них есть то преимущество, что все их биты являются полнопериодными; они не страдают от слабости младших разрядов, от которой страдает арифметика по модулю 2 k .

Примеры этого семейства включают генераторы xorshift и твистер Мерсенна . Последний обеспечивает очень длинный период (2 19937 −1) и варьирует однородность, но не проходит некоторые статистические тесты. Отстающие генераторы Фибоначчи также попадают в эту категорию; хотя они используют арифметическое сложение, их период обеспечивается LFSR среди младших битов.

Структуру сдвигового регистра с линейной обратной связью легко обнаружить с помощью соответствующих тестов, таких как тест линейной сложности, реализованный в наборе TestU01 ; логическая циркулянтная матрица, инициализированная из последовательных битов LFSR, никогда не будет иметь ранг выше степени полинома. Добавление нелинейной функции микширования выходного сигнала (как в xoshiro256 ** и конструкциях конгруэнтного генератора с перестановками ) может значительно улучшить производительность статистических тестов.

Другая структура PRNG — это очень простая функция повторения в сочетании с мощной функцией микширования выходного сигнала. Сюда входят блочные шифры в режиме счетчика и некриптографические генераторы, такие как SplitMix64 .

Структура, аналогичная LCG, но не эквивалентная, представляет собой множественный рекурсивный генератор: X n = ( a 1 X n −1 + a 2 X n −2 + ··· + a k X nk ) mod m для k ≥ 2. При простом модуле это может генерировать периоды до m k −1, поэтому это полезное расширение структуры LCG на более крупные периоды.

Мощный метод генерации высококачественных псевдослучайных чисел состоит в объединении двух или более ГПСЧ разной структуры; сумма LFSR и LCG (как в конструкциях KISS или xorwow ) может очень хорошо работать с некоторой ценой в скорости.

Источник