Линейный конгруэнтный генератор

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

Два LCG по модулю 9 показывают, как разные параметры приводят к разной длине цикла. Каждая строка показывает состояние, развивающееся до тех пор, пока оно не повторится. В верхнем ряду показан генератор с m  = 9, a  = 2, c  = 0 и начальным числом 1, который создает цикл длины 6. Вторая строка представляет собой тот же генератор с начальным числом 3, который создает цикл. длины 2. Использование a  = 4 и c  = 1 (нижняя строка) дает длину цикла 9 с любым начальным числом в [0, 8].

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

Генератор определяется рекуррентным соотношением :

${\displaystyle X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}}$

где – последовательность псевдослучайных значений, а ${\displaystyle X}$

${\displaystyle m,\,0<m}$— « модуль »

${\displaystyle a,\,0<a<m}$— «множитель»

${\displaystyle c,\,0\leq c<m}$— «прибавка»

${\displaystyle X_{0},\,0\leq X_{0}<m}$— «начальное» или «начальное значение»

— целочисленные константы, определяющие генератор. Если c  = 0, генератор часто называют мультипликативным конгруэнтным генератором (MCG) или ГСЧ Лемера . Если c  ≠ 0, метод называется смешанным конгруэнтным генератором . ^{[1] : 4-}

Когда c  ≠ 0, математик назвал бы повторение аффинным преобразованием , а не линейным , но это неправильное название хорошо укоренилось в информатике. ^{[2] : 1}

История

Генератор Лемера был опубликован в 1951 году ^[3] , а линейный конгруэнтный генератор был опубликован в 1958 году У. Э. Томсоном и А. Ротенбергом. ^{[4] [5]}

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

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

Хотя LCG способны генерировать псевдослучайные числа , которые могут пройти формальные тесты на случайность , качество вывода чрезвычайно чувствительно к выбору параметров m и a . ^{[7] [1] [8] [9] [10] [2]} Например, a  = 1 и c  = 1 дают простой счетчик по модулю , который имеет длинный период, но явно неслучайен.

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

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

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

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

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

Если произведение двойной ширины недоступно и множитель выбран тщательно, можно использовать метод Шраге ^{[12] .} Для этого множим 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 , первый член строго меньше am / a  =  m . Если a выбрано так, что r  ≤  q (и, следовательно, r / q  ≤ 1), то второй член также меньше m : r ⌊ x / q ⌋ ≤ rx / q = x ( r / q ) ≤ x < m . Таким образом, оба произведения могут быть вычислены с помощью произведения одинарной ширины, а разница между ними лежит в диапазоне [1− m ,  m −1], поэтому может быть уменьшена до [0,  m −1] с помощью одного условного сложения. . ^[13]

Второй недостаток заключается в том, что сложно преобразовать значение 1 ≤  x  <  m в однородные случайные биты. Если используется простое число, меньшее степени 2, иногда недостающие значения просто игнорируются.

m степень 2, c = 0

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

Эта форма имеет максимальный период m /4, достигаемый, если a  ≡ ±3 (mod 8) и начальное состояние X ₀ нечетно. Даже в этом лучшем случае три младших бита X чередуются между двумя значениями и, таким образом, вносят в состояние только один бит. X всегда нечетно (младший бит никогда не меняется), и только один из следующих двух бит всегда изменяется. Если a  ≡ +3, X чередуется ±1↔±3, а если a  ≡ −3, X чередуется ±1↔∓3 (все по модулю 8).

Можно показать, что эта форма эквивалентна генератору с модулем m /4 и c ≠ 0. ^[1]

Более серьезная проблема с использованием модуля степени двойки заключается в том, что младшие биты имеют более короткий период, чем старшие биты. Его простота реализации обусловлена ​​тем фактом, что на биты никогда не влияют биты более высокого порядка, поэтому младшие биты такого генератора сами по себе образуют LCG по модулю 2 ^b , повторяясь с периодом 2 ^{b -2} . Только самый старший бит X достигает полного периода.

в ≠ 0

Когда c ≠ 0, правильно выбранные параметры допускают период, равный m , для всех начальных значений. Это произойдет тогда и только тогда, когда : ^{[1] : 17—19.}

1. ${\displaystyle m}$и являются относительно простыми , ${\displaystyle c}$
2. ${\displaystyle a-1}$делится на все простые множители , ${\displaystyle m}$
3. ${\displaystyle a-1}$делится на 4, если делится на 4. ${\displaystyle m}$

Эти три требования называются теоремой Халла – Добелла. ^{[14] [15]}

Эту форму можно использовать с любым m , но хорошо работает только для m со многими повторяющимися простыми множителями, например степенью 2; использование размера слова компьютера является наиболее распространенным выбором. Если бы m было целым числом без квадратов , это допускало бы только a  ≡ 1 (mod  m ), что делает ГПСЧ очень плохим; выбор возможных множителей полного периода доступен только в том случае, если m имеет повторяющиеся простые множители.

Хотя теорема Халла – Добелла обеспечивает максимальный период, этого недостаточно, чтобы гарантировать хороший генератор. Например, желательно, чтобы a  - 1 не делилось на простые множители m больше , чем это необходимо. Таким образом, если m — степень 2, то a  − 1 должно делиться на 4, но не делиться на 8, т. е.  a  ≡ 5 (по модулю 8). ^{[1] : §3.2.1.3}

Действительно, большинство множителей создают последовательность, которая не проходит тот или иной тест на неслучайность, и найти множитель, который удовлетворяет всем применимым критериям ^{[1] : §3.3.3} , довольно сложно. Спектральный тест является одним из наиболее важных тестов. ^[16]

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

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

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

${\displaystyle X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.}$

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

${\displaystyle {X_{n}-X_{0} \over X_{1}-X_{0}}=Y_{n}={a^{n}-1 \over a-1}={Z_{n}-Z_{0} \over Z_{1}-Z_{0}}{\pmod {m}}.}$

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

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

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

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

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

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

Гиперплоскости линейного конгруэнтного генератора в трех измерениях. Эту структуру и измеряет спектральный тест .

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

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

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

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

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

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

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

Образец кода

Код Python

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

из  коллекции.abc  Генератор импорта def  lcg ( modulus :  int ,  a :  int ,  c :  int ,  seed :  int )  ->  Генератор [ int ,  None ,  None ]: """Линейный конгруэнтный генератор.""" while True : seed = ( a * seed + в ) % модуля выхода семян              

Бесплатный Паскаль

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

единица lcg_random ; {$ifdef fpc}{$mode delphi}{$endif} интерфейс функция LCGRandom : расширенная ; перегрузка ; в соответствии ; функция LCGRandom ( const range : longint ) : longint ; перегрузка ; в соответствии ;         функция реализации IM : кардинальная ; в соответствии ; начать RandSeed := RandSeed * 134775813 + 1 ; Результат := RandSeed ; конец ;             функция LCGRandom : расширенная ; перегрузка ; в соответствии ; начать результат := IM * 2.32830643653870e-10 ; конец ;         функция LCGRandom ( const range : longint ) : longint ; перегрузка ; в соответствии ; начало результата := IM * диапазон шр 32 ; конец ;             

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

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

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

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

ГПСЧ Марсальи  со  сложением и переносом и вычитанием с заимствованием с размером слова b = 2 ^w и задержками r и s ( r  >  s ) эквивалентны LCG с модулем br ^± b ^s  ± 1. ^{[36] [37]}

ГПСЧ умножения с переносом с множителем a эквивалентны LCG с большим простым модулем ab ^r -1 и множителем степени 2 b .

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

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

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

Примеры этого семейства включают генераторы xorshift и твистер Мерсенна . Последний обеспечивает очень длительный период (2 ¹⁹⁹³⁷ −1) и вариативную однородность, но не проходит некоторые статистические тесты. ^[39] Генераторы Фибоначчи с запаздыванием также попадают в эту категорию; хотя они используют арифметическое сложение, их период обеспечивается LFSR среди младших битов.

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

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

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

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

Смотрите также

• Список генераторов случайных чисел - другие ГПСЧ, в том числе с лучшими статистическими качествами.
• Генератор ACORN - не путать с ACG, этот термин, по-видимому, использовался для вариантов генераторов LCG и LFSR.
• Перестановочный конгруэнтный генератор
• Полный цикл
• Инверсивный конгруэнтный генератор
• Умножение с переносом
• ГСЧ Лемера (иногда называемый ГСЧ Парка – Миллера)
• Комбинированный линейный конгруэнтный генератор

Примечания

1. Кнут, Дональд (1997). Получисловые алгоритмы . Искусство компьютерного программирования . Том. 2 (3-е изд.). Ридинг, Массачусетс: Addison-Wesley Professional. стр. 10–26.
2. Стил, Гай ; Винья, Себастьяно (15 января 2020 г.). «Простые в вычислениях, спектрально хорошие множители для конгруэнтных генераторов псевдослучайных чисел». arXiv : 2001.05304 [cs.DS]. На данный момент маловероятно, что ставшие традиционными названия будут исправлены. Математика вычислений (в печати). Соответствующие данные доступны по адресу https://github.com/vigna/CPRNG.
3. Лемер, Деррик Х. (1951). «Математические методы в больших вычислительных устройствах». Материалы 2-го симпозиума по крупномасштабной цифровой вычислительной технике : 141–146.
4. Томсон, МЫ (1958). «Модифицированный метод сравнения для генерации псевдослучайных чисел». Компьютерный журнал . 1 (2): 83. дои : 10.1093/comjnl/1.2.83 .
5. Ротенберг, А. (1960). «Новый генератор псевдослучайных чисел». Журнал АКМ . 7 (1): 75–77. дои : 10.1145/321008.321019 . S2CID  16770825.
6. Л'Экуйер, Пьер (13 июля 2017 г.). Чан, WKV; Д'Амброджио, А.; Захаревич Г.; Мустафи, Н.; Вайнер, Г.; Пейдж, Э. (ред.). История генерации унифицированных случайных чисел (PDF) . Материалы Зимней конференции по моделированию 2017 г. (будут опубликованы). Лас-Вегас, США. hal-01561551.
7. Марсалья, Джордж (сентябрь 1968 г.). «Случайные числа падают в основном в плоскостях» (PDF) . ПНАС . 61 (1): 25–28. Бибкод : 1968PNAS...61...25M. дои : 10.1073/pnas.61.1.25 . ПМЦ 285899 . ПМИД  16591687. 
8. Парк, Стивен К.; Миллер, Кейт В. (октябрь 1988 г.). «Генератор случайных чисел: хорошие найти трудно» (PDF) . Коммуникации АКМ . 31 (10): 1192–1201. дои : 10.1145/63039.63042. S2CID  207575300.
9. Хёрманн, Вольфганг; Дерфлингер, Герхард (1993). «Портативный универсальный генератор случайных чисел, хорошо подходящий для метода отклонения» (PDF) . Транзакции ACM в математическом программном обеспечении . 19 (4): 489–495. CiteSeerX 10.1.1.52.3811 . дои : 10.1145/168173.168414. S2CID  15238956. Множитель размером примерно √ m выдает случайные числа с плохим одномерным распределением. 
10. L'Ecuyer, Пьер (январь 1999 г.). «Таблицы линейных конгруэнтных генераторов разных размеров и хорошей решетчатой ​​структуры» (PDF) . Математика вычислений . 68 (225): 249–260. Бибкод : 1999MaCom..68..249L. CiteSeerX 10.1.1.34.1024 . дои : 10.1090/S0025-5718-99-00996-5.  Обязательно прочтите также «Ошибки».
11. Press, Уильям Х.; и другие. (1992). Числовые рецепты на Фортране 77: Искусство научных вычислений (2-е изд.). ISBN 978-0-521-43064-7.
12. Джайн, Радж (9 июля 2010 г.). «Анализ производительности компьютерных систем, глава 26: Генерация случайных чисел» (PDF) . стр. 19–20 . Проверено 31 октября 2017 г.
13. Фенерти, Пол (11 сентября 2006 г.). «Метод Шраге» . Проверено 31 октября 2017 г.
14. Халл, TE; Добелл, Арканзас (июль 1962 г.). «Генератор случайных чисел» (PDF) . Обзор СИАМ . 4 (3): 230–254. Бибкод : 1962SIAMR...4..230H. дои : 10.1137/1004061. hdl : 1828/3142 . Проверено 26 июня 2016 г.
15. Северанс, Фрэнк (2001). Системное моделирование и симуляция . Джон Вили и сыновья, ООО с. 86. ИСБН 978-0-471-49694-6.
16. Остин, Дэвид (март 2008 г.). «Случайные числа: ничего не оставлено на волю случая». Американское математическое общество.
17. Реализация в версии glibc-2.26. См. код после теста «TYPE_0»; Функция rand() библиотеки GNU C в stdlib.h использует простой (с одним состоянием) линейный конгруэнтный генератор только в том случае, если состояние объявлено как 8 байт. Если состояние больше (массив), генератор становится аддитивным генератором обратной связи (инициализируется с помощью minstd_rand0), и период увеличивается. Посмотрите упрощенный код, воспроизводящий случайную последовательность из этой библиотеки.
18. К. Энтачер (21 августа 1997 г.). Коллекция избранных генераторов псевдослучайных чисел с линейной структурой. CiteSeerX 10.1.1.53.3686 . Проверено 16 июня 2012 г. 
19. «Последний проект общественного комитета от 12 апреля 2011 г.» (PDF) . п. 346ф . Проверено 21 декабря 2014 г.
20. Доманн, Биргит; Фальк, Майкл; Лессенич, Карин (август 1991 г.). «Генератор случайных чисел семейства Turbo Pascal». Вычислительная статистика и анализ данных . 12 (1): 129–132. дои : 10.1016/0167-9473(91)90108-E.
21. «Как Visual Basic генерирует псевдослучайные числа для функции RND» . Майкрософт. 24 июня 2004 г. Архивировано из оригинала 17 апреля 2011 г. Проверено 17 июня 2011 г.
22. Несмотря на документацию в MSDN, RtlUniform использует LCG, а не алгоритм Лемера, реализации до Windows Vista имеют недостатки, поскольку результат умножения сокращается до 32 бит перед применением по модулю.
23. «Поиск идентификатора источника WINE: RtlUniform» . Проверено 13 января 2024 г.
24. «ISO/IEC 14882:2011». ИСО. 2 сентября 2011 года . Проверено 3 сентября 2011 г.
25. «Создание и управление потоком случайных чисел». Матворкс . Проверено 7 июня 2021 г.
26. «ранд, сранд — псевдослучайные числа». Git-репозиторий Newlib . Проверено 13 января 2024 г.
27. "Научная библиотека GNU: gsl_rng_vax" .
28. Стивен Дж. Чепмен. «Пример 6.4 – Генератор случайных чисел». «Программирование MATLAB для инженеров». 2015. С. 253–256.
29. Стивен Дж. Чепмен. «Пример 6.4 – Генератор случайных чисел». «Программирование MATLAB с приложениями для инженеров». 2012. С. 292–295.
30. С. Дж. Чепмен. случайный0. 2004.
31. Стивен Дж. Чепмен. «Введение в Фортран 90/95». 1998. стр. 322–324.
32. У-тин Цай. «Модуль: основная особенность современного Фортрана». Архивировано 24 февраля 2021 г. в Wayback Machine . стр. 6–7.
33. Базовые спецификации открытой группы, выпуск 7 IEEE Std 1003.1, издание 2013 г.
34. Кадот, Сидни. "ранд.с". cc65 . Проверено 8 июля 2016 г.
35. О'Нил, Мелисса Э. (5 сентября 2014 г.). PCG: семейство простых быстрых и статистически эффективных алгоритмов генерации случайных чисел (PDF) (технический отчет). Колледж Харви Мадда . стр. 6–7. HMC-CS-2014-0905.
36. Тэдзука, Шу; Л'Экуйер, Пьер (октябрь 1993 г.). О решетчатой ​​структуре генераторов случайных чисел «сложение с переносом» и «вычитание с заимствованием» (PDF) . Семинар по стохастическим числам. Киотский университет.
37. Тэдзука, Ши; Л'Экуйер, Пьер (декабрь 1992 г.). Анализ генераторов сложения с переносом и вычитания с заимствованием (PDF) . Материалы зимней конференции по моделированию 1992 года. стр. 443–447.
38. Гершенфельд, Нил (1999). «Раздел 5.3.2: Линейная обратная связь». Природа математического моделирования (первое изд.). Издательство Кембриджского университета. п. 59. ИСБН 978-0-521-57095-4.
39. Мацумото, Макото; Нисимура, Такудзи (январь 1998 г.). «Твистер Мерсенна: 623-мерный равнораспределенный равномерный генератор псевдослучайных чисел» (PDF) . ACM-транзакции по моделированию и компьютерному моделированию . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . дои : 10.1145/272991.272995. S2CID  3332028. Архивировано из оригинала (PDF) 7 ноября 2017 г. 
40. Истлейк, Дональд Э. 3-й; Шиллер, Джеффри И.; Крокер, Стив (июнь 2005 г.). «Традиционные псевдослучайные последовательности». Требования случайности для безопасности. IETF . сек. 6.1.3. дои : 10.17487/RFC4086 . BCP 106. RFC 4086.{{citation}}: CS1 maint: numeric names: authors list (link)

Рекомендации

• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 7.1.1. Немного истории», Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8, заархивировано из оригинала 11 августа 2011 г. , получено 10 августа 2011 г.
• Нежный, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло , 2-е издание, Springer, ISBN 0-387-00178-6 . 
• Джоан Бояр (1989). «Вывод последовательностей, созданных генераторами псевдослучайных чисел» (PDF) . Журнал АКМ . 36 (1): 129–141. дои : 10.1145/58562.59305. S2CID  3565772.(в этой статье приведены эффективные алгоритмы вывода последовательностей, созданных некоторыми генераторами псевдослучайных чисел).

Внешние ссылки

• Линейный конгруэнтный генератор моделирования визуализирует корреляции между псевдослучайными числами при манипулировании параметрами.
• Безопасность генерации случайных чисел: аннотированная библиография
• Сообщение о линейных конгруэнтных генераторах на sci.math
• Проект компьютерного искусства «Смерть искусства» компании Goldstein Technologies LLC использует LCG для создания 33 554 432 изображений.
• П. Л'Экуйер и Р. Симард, «TestU01: Библиотека AC для эмпирического тестирования генераторов случайных чисел», май 2006 г., исправлено в ноябре 2006 г., Транзакции ACM в математическом программном обеспечении , 33, 4, статья 22, август 2007 г.
• Статья о другом способе взлома LCG