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

‹Приведенный ниже шаблон ( необходим эксперт ) рассматривается для удаления. См. Шаблоны для обсуждения, чтобы помочь достичь консенсуса. ›

Эта статья требует внимания специалиста-математика . Добавьте причину или параметр обсуждения в этот шаблон, чтобы объяснить проблему со статьей. WikiProject Mathematics может помочь нанять эксперта. ( Ноябрь 2008 г. )

В информатике , множественно-с-переноса (КТМ) представляет собой метод , изобретенный Джордж Marsaglia ^[1] для генерации последовательности случайных чисел на основе начального набора от двух до многих тысяч случайно выбранных исходных значений. Основные преимущества метода MWC заключаются в том, что он вызывает простую компьютерную целочисленную арифметику и приводит к очень быстрой генерации последовательностей случайных чисел с огромными периодами, от примерно до . ${\ displaystyle 2 ^ {60}}$ ${\ displaystyle 2 ^ {2000000}}$

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

Общая теория [ править ]

Генератор MWC - это особая форма генератора случайных чисел Лемера, которая позволяет эффективно реализовать простой модуль, намного превышающий размер машинного слова. ${\ displaystyle x_ {n} = bx_ {n-1} {\ bmod {p}}}$ ${\ displaystyle p}$

Обычные реализации генератора Лемера выбирают модуль, близкий к размеру машинного слова. Генератор MWC вместо этого поддерживает свое состояние в базе , поэтому умножение на выполняется неявно путем сдвига одного слова. База обычно выбирается равной размеру слова компьютера, так как это делает арифметику по модулю тривиальной. Это может варьироваться от для микроконтроллера к . (В этой статье используются примеры.) ${\ displaystyle b}$ ${\ displaystyle b}$ ${\ displaystyle b}$ ${\ displaystyle b}$ ${\ displaystyle b = 2 ^ {8}}$ ${\ displaystyle b = 2 ^ {64}}$ ${\ displaystyle b = 2 ^ {32}}$

Значения начального состояния ("seed") произвольны, за исключением того, что они не должны быть ни нулевыми, ни максимально допустимыми значениями ( и ). (Обычно это делается путем выбора между 1 и .). Тогда последовательность MWC представляет собой последовательность пар, определяемую ${\ displaystyle x_ {0} = b-1}$ ${\ displaystyle c_ {0} = а-1}$ ${\ displaystyle c_ {0}}$ ${\ displaystyle a-2}$ ${\ displaystyle x_ {n}, c_ {n}}$

{\ displaystyle x_ {n} = (ax_ {n-1} + c_ {n-1}) \, {\ bmod {\,}} b, \ c_ {n} = \ left \ lfloor {\ frac {ax_ {n-1} + c_ {n-1}} {b}} \ right \ rfloor}

Это называется последовательностью MWC с задержкой-1. Иногда предпочтительна нечетная база, и в этом случае можно использовать, что почти так же просто реализовать. Последовательность запаздывания является обобщением последовательности запаздывания-1, допускающей более длительные периоды ^[2] . Последовательность лаг- MWC тогда представляет собой последовательность пар (для ), определяемых ${\ displaystyle b = 2 ^ {k} -1}$ ${\ displaystyle r}$ ${\ displaystyle r}$ ${\ displaystyle x_ {n}, c_ {n}}$ ${\ displaystyle n> r}$

{\ displaystyle x_ {n} = (ax_ {nr} + c_ {n-1}) \, {\ bmod {\,}} b, \ c_ {n} = \ left \ lfloor {\ frac {ax_ {nr } + c_ {n-1}} {b}} \ right \ rfloor}

а выходной сигнал генератора MWC - это последовательность символов, ${\ displaystyle x}$

{\ displaystyle x_ {r}, x_ {r + 1}, x_ {r + 2}, ...}

В этом случае значения начального состояния («семя») не должны быть ни нулем, ни и . ${\ displaystyle x_ {0} = b-1}$ ${\ displaystyle c_ {r-1} = а-1}$

Множитель и задержка MWC определяют модуль . На практике выбирается так, чтобы модуль был простым, а последовательность имела длинный период. Если модуль простой, то период генератора запаздывающих MWC равен порядку в мультипликативной группе чисел по модулю . Хотя теоретически можно выбрать непростой модуль, простой модуль исключает возможность того, что начальное начальное число имеет общий делитель с модулем, что уменьшит период генератора. $a$ $r$ $p=ab^{r}-1$ $a$ $r$ $b$ $p$

Поскольку 2 является квадратичным вычетом чисел формы , не может быть примитивным корнем из . Таким образом, генераторы MWC с базой имеют параметры, выбранные так, чтобы их период был ( ab ^r −1) / 2. Это одна из трудностей, которые преодолевает использование b = 2 ^k - 1. $8k\pm 1$ $b=2^{k}$ $p=ab^{r}-1$ $2^{k}$

Базовая форма генератора MWC имеет параметры a , b и r , а также r +1 слов состояния. Состояние состоит из r вычетов по модулю b

0 ≤ x ₀ , x ₁ , x ₂ , ..., x _{r −1} <b,

и перенос c _{r −1} < a .

Хотя теория генераторов MWC допускает a > b , a почти всегда выбирается меньшим для удобства реализации.

Функция преобразования состояния генератора MWC - это один шаг редукции Монтгомери по модулю p . Состояние - это большое целое число со старшим словом c _{n −1} и младшим значащим словом x _{n - r} . Каждый шаг x _{n - r} · ( ab ^r −1) добавляется к этому целому числу. Это делается в двух частях: −1 · x _{n - r} добавляется к x _{n - r} , в результате чего младшее значащее слово равно нулю. Во-вторых, a · x _{n -r} добавляется к переносу. Это увеличивает длину целого числа на одно слово, создавая два новых наиболее значимых слова x _n и c _n .

До сих пор это просто добавляло к состоянию число, кратное p , что приводило к другому представителю того же класса остатка по модулю p . Но, наконец, состояние сдвигается на одно слово вниз, делится на b . Это отбрасывает наименее значащее слово нуля (которое на практике никогда не вычисляется вообще) и эффективно умножает состояние на b ⁻¹ (mod p ).

Таким образом, генератор умножения с переносом - это генератор Лемера с модулем p и множителем b ⁻¹ (mod p ). Это то же самое, что и генератор с множителем b , но выдает выходной сигнал в обратном порядке, что не влияет на качество получаемых псевдослучайных чисел.

Кутюр и L'Ecuyer ^[3] доказали удивительный результат: решетка, связанная с генератором умножения с переносом, очень близка к решетке, связанной с генератором Лемера, который он моделирует. Таким образом, математические методы, разработанные для генераторов Лемера (такие как спектральный тест ), могут быть применены к генераторам с умножением с переносом.

Эффективность [ править ]

Линейный конгруэнтный генератор с основанием Ь = 2 ³² реализован в виде

x_{n+1}=(ax_{n}+c)\ {\bmod {\,}}2^{32},

где c - постоянная. Если a ≡ 1 (mod 4) и c нечетно, результирующая конгруэнтная последовательность по основанию 2 ³² будет иметь период 2 ³² . ^[4]

Это можно вычислить, используя только младшие 32 бита произведения a и текущего x . Однако многие микропроцессоры могут вычислить полный 64-битный продукт почти за то же время, что и младшие 32 бита. Действительно, многие вычисляют 64-битное произведение, а затем игнорируют старшую половину.

Генератор умножения с переносом с запаздыванием-1 позволяет нам сделать период примерно ²⁶³ с использованием почти тех же компьютерных операций, за исключением того, что верхняя половина 64-битного произведения не игнорируется после вычисления произведения. Вместо этого вычисляется 64-битная сумма, и верхняя половина используется как новое значение переноса c, а не фиксированная аддитивная константа стандартной конгруэнтной последовательности: вычислить ax + c в 64 битах, затем использовать верхнюю половину как новую c , а нижняя половина - как новый x .

Выбор множителя [ править ]

Если задан множитель a , каждая пара входных значений x , c преобразуется в новую пару,

x\leftarrow (ax+c)\,{\bmod {\,}}2^{32},\ \ c\leftarrow \left\lfloor {\frac {ax+c}{2^{32}}}\right\rfloor .

Если x и c не равны нулю, то период результирующей последовательности умножения с переносом будет иметь порядок b = 2 ³² в мультипликативной группе вычетов по модулю ab ^r - 1 , то есть наименьшее n такое, что b ⁿ ≡ 1 (mod ab ^r - 1).

Если р = абы ^г - 1 простой, то малая теорема Ферма гарантирует , что порядок любого элемент должен делить р - 1 = аб ^г - 2, так что один из способов обеспечения большого заказа должен выбрать таким образом, что р является " безопасное простое число ", то есть p и ( p - 1) / 2 = ab ^r / 2 - 1 простые числа. В таком случае для b = 2 ³² и r = 1 период будет ab ^r / 2 - 1, приближаясь к 2 ⁶³, что на практике может быть достаточно большим подмножеством числа возможных 32-битных пар ( x , c ).

Более конкретно, в таком случае порядок любого элемента делит p - 1, и есть только четыре возможных делителя: 1, 2, ab ^r / 2 - 1 или ab ^r - 2. Первые два применимы только к элементы 1 и -1, а аргументы квадратичной взаимности показывают, что четвертый вариант не может применяться к b , поэтому остается только третий вариант.

Ниже приведены некоторые максимальные значения a для компьютерных приложений, которые удовлетворяют вышеуказанному безопасному условию простого числа, для генераторов lag-1:

Биты в а	б	Максимум a такой, что ab −1 - безопасное простое число	Период
15	2 ¹⁶	2 ¹⁵ −50 = 32 718	1 072 103 423
16	2 ¹⁶	2 ¹⁶ −352 = 65 184	2 135 949 311
31 год	2 ³²	2 ³¹ −563 = 2 147 483 085	4 611 684 809 394 094 079
32	2 ³²	2 ³² −178 = 4 294 967 118	9 223 371 654 602 686 463
64	2 ⁶⁴	2 ⁶⁴ −742 = 18 446 744 073 709 550 874	2 ⁶³ (2 ⁶⁴ −742) −1 ≈ 1.701 × 10³⁸^
128	2 ¹²⁸	2 ¹²⁸ −10 408	2 ¹²⁷ (2 ¹²⁸ −10 408) −1 ≈ 5,790 × 10⁷⁶^
256	2 ²⁵⁶	2 ²⁵⁶ −9166	2 ²⁵⁵ (2 ²⁵⁶ −9166) −1 ≈ 6,704 × 10¹⁵³^
512	2 ⁵¹²	2 ⁵¹² -150 736	2 ⁵¹¹ (2 ⁵¹² −150 736) −1 ≈ 8,988 × 10³⁰⁷^

В то время как безопасное простое число гарантирует, что почти любой элемент группы имеет большой порядок, период генератора, в частности, имеет порядок b . Для небольших модулей можно использовать более дорогостоящие в вычислительном отношении методы, чтобы найти множители a с периодом ab / 2 - 1. Ниже снова приведены максимальные значения a различных размеров.

Биты в а	б ^г	Максимум a такой, что b имеет порядок ab ^r / 2−1	Период
8	2 ⁸	2 ⁸ −7 = 249	31 871
8	(2 ⁸ ) ² = 2 ¹⁶	2 ⁸ −32 = 224	7,340,031
15	2 ¹⁶	2 ¹⁵ −29 = 32 739	1 072 791 551
16	2 ¹⁶	2 ¹⁶ −22 = 65 514	2 146 762 751
8	(2 ⁸ ) ⁴ = 2 ³²	2 ⁸ −64 = 192	412 316 860 415
15	(2 ¹⁶ ) ² = 2 ³²	2 ¹⁵ −26 = 32 742	70 312 909 602 815
16	(2 ¹⁶ ) ² = 2 ³²	2 ¹⁶ -2 = 65 534	140 733 193 388 031
31 год	2 ³²	2 ³¹ −68 = 2 147 483 580	4 611 685 872 398 499 839
32	2 ³²	2 ³² −76 = 4 294 967 220	9 223 371 873 646 018 559
8	(2 ⁸ ) ⁸ = 2 ⁶⁴	2 ⁸ −41 = 215	2 ⁶³ (2 ⁸ −41) −1 ≈ 1.983 × 10²¹^
15	(2 ¹⁶ ) ⁴ = 2 ⁶⁴	2 ¹⁵ −50 = 32 718	2 ⁶³ (2 ¹⁵ −50) −1 ≈ 3,018 × 10²³^
16	(2 ¹⁶ ) ⁴ = 2 ⁶⁴	2 ¹⁶ −56 = 65 480	2 ⁶³ (2 ¹⁶ −56) −1 ≈ 6.039 × 10²³^
31 год	(2 ³² ) ² = 2 ⁶⁴	2 ³¹ -38 = 2 147 483 610	2 ⁶³ (2 ³¹ −38) −1 ≈ 1.981 × 10²⁸^
32	(2 ³² ) ² = 2 ⁶⁴	2 ³² −43 = 4 294 967 253	2 ⁶³ (2 ³² −43) −1 ≈ 3.961 × 10²⁸^
63	2 ⁶⁴	2 ⁶³ -140 = 9 223 372 036 854 775 668	2 ⁶³ (2 ⁶³ −140) −1 ≈ 8,507 × 10³⁷^
64	2 ⁶⁴	2 ⁶⁴ −116 = 18 446 744 073 709 551 500	2 ⁶³ (2 ⁶⁴ −116) −1 ≈ 1.701 × 10³⁸^

Генераторы MWC как повторяющиеся десятичные дроби [ править ]

Выходные данные генератора умножения с переносом эквивалентны разложению дроби по основанию radix - b со знаменателем p = ab ^r - 1. Вот пример для простого случая b = 10 и r = 1, поэтому результат - повторяющееся десятичное число .

Начиная с последовательности MWC ${\textstyle c_{0}=1,x_{0}=0}$

x_{n}=(7x_{n-1}+c_{n-1})\,{\bmod {\,}}10,\ c_{n}=\left\lfloor {\frac {7x_{n-1}+c_{n-1}}{10}}\right\rfloor ,

производит эту последовательность состояний:

10,01,07,49,67,55,40,04,28,58,61,13,22,16,43,25,37,52,19,64,34,31, 10,01,07, ...

с периодом 22. Рассмотрим последовательность x _i :

0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4,1, 0,1,7, 9,7,5,0, ...

Обратите внимание, что если эти повторяющиеся сегменты значений x расположены в обратном порядке :

1449275\cdots 9710\,1449275\cdots 9710\,144\cdots

получаем разложение j / ( ab −1) с a = 7, b = 10, j = 10 :

{\frac {10}{69}}=0.1449275362318840579710\,14492753623\ldots

Это верно в целом: Последовательность х лет производится с помощью lag- г генератора MWC:

x_{n}=(ax_{n-r}+c_{n-1}){\bmod {\,}}b\,,\ \ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor ,

если поставить в обратном порядке, будет основание системы счисления b дроби j / ( ab ^r - 1) для некоторого 0 < j < ab ^r .

Эквивалентность линейному конгруэнтному генератору [ править ]

Продолжая приведенный выше пример, если мы начнем с и сгенерируем обычную конгруэнтную последовательность ${\textstyle x_{0}=34}$

x_{n}=7x_{n-1}\,{\bmod {\,}}69

,

получаем последовательность периода 22

31,10,1,7,49,67,55,40,4,28,58,61,13,22,16,43,25,37,52,19,64,34, 31,10,1, 7, ...

и эта последовательность, сокращенная по модулю 10, является

1,0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4, 1,0,1, 7,9,7,5,0, ...

та же последовательность x, полученная в результате последовательности MWC.

Это верно в целом (но, по-видимому, только для последовательностей Lag-1 MWC ^{[ необходима ссылка ]} ):

При заданных начальных значениях последовательность, полученная из последовательности Lag-1 MWC $x_{0},c_{0}$ $x_{1},x_{2},\ldots$

x_{n}=(ax_{n-1}+c_{n-1})\,{\bmod {b}}\,,\ \ c_{n}=\left\lfloor {\frac {ax_{n-1}+c_{n-1}}{b}}\right\rfloor

является в точности выходной последовательностью генератора случайных чисел Лемера y _n = ay _{n - 1} mod ( ab - 1), приведенной по модулю b .

Выбор другого начального значения y ₀ просто вращает цикл x .

Генераторы комплементарного умножения с переносом [ править ]

Установление периода в lag- г генератора MWC обычно влечет за собой выбор множителя таким образом , что р = абы ^г - 1 является простым. Тогда p - 1 нужно будет разложить на множители, чтобы найти порядок b mod p . Если р является безопасным простое , то это просто, и порядок Ь будет либо р - 1 или ( р - 1) / 2. В других случаях коэффициент p - 1 может быть затруднен.

Однако алгоритм также допускает отрицательный множитель. Это приводит к небольшой модификации процедуры MWC и дает модуль p = | - ab ^r - 1 | = ab ^r + 1. Это позволяет легко разложить p - 1 = ab ^r на множители, что делает практичным определение периода очень больших генераторов.

Модифицированная процедура называется комплементарной-кратно-с-переносом (CMWC), и установки тот же, что и для lag- г MWC: Умножитель , основание б и г + 1 семян,

x ₀ , x ₁ , x ₂ , ..., x _{r −1} и c _{r −1} .

Модификация заключается в создании новой пары ( x , c ). Изменяя порядок вычисления, чтобы избежать отрицательных чисел, новое значение x дополняется вычитанием его из b - 1:

x_{n}=(b-1)-(ax_{n-r}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor .

В результате чего последовательность х « ы производится с помощью RNG CMWC будет иметь период порядка Ь в мультипликативной группе вычетов по модулю аб ^г +1, а выходной сигнал х » с, в обратном порядке, будет формировать основание Ь расширение J / ( ab ^r +1) для некоторого 0 < j < ab ^r .

Использование lag- г CM делает его гораздо легче найти периоды для г ' с , как большой , как 512, 1024, 2048 и т.д. (Изготовлением R мощности 2 позволяет несколько простых к элементам доступа в массиве , содержащий г самых последние х ' с.)

Еще одно преимущество этой модифицированной процедуры состоит в том, что период кратен b , поэтому выход точно равнораспределен по модулю b . ^[3] (Обычный MWC за полный период производит каждый возможный результат равное количество раз, за исключением того, что ноль вырабатывается на один раз меньше, смещение, которым можно пренебречь, если период достаточно длинный.)

Одним из недостатков конструкции CMWC является то, что при мощности двойки базовый максимально достижимый период меньше, чем для генератора MWC аналогичного размера; вы теряете несколько бит. Таким образом, генератор MWC обычно предпочтительнее для небольших лагов. Это можно исправить, используя b = 2 ^k −1 или выбрав задержку на одно слово длиннее для компенсации.

Некоторые примеры: при b = 2 ³² и a = 109111, или 108798, или 108517, период лага-1024 CMWC

x_{n}=(b-1)-(ax_{n-1024}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-1024}+c_{n-1}}{b}}\right\rfloor .

будет · 2 ³²⁷⁶² = AB ¹⁰²⁴ /64, около 10 ⁹⁸⁶⁷ .

При b = 2 ³² и a = 3636507990 p = ab ¹³⁵⁹ - 1 является безопасным простым числом , поэтому последовательность MWC, основанная на этом a, имеет период 3636507990 · 2 ⁴³⁴⁸⁷ ≈ 10 ¹³¹⁰¹ .

При b = 2 ³² ГСЧ CMWC с периодом, близким к записи, может быть основан на простом числе p = 15455296 b ⁴²⁶⁵⁸ + 1. Порядок b для этого простого числа равен 241489 · 2 ^1365056 ≈ 10 ⁴¹⁰⁹²⁸ .

Более общие модули [ править ]

Модуль MWC ab ^r −1 выбран для того, чтобы сделать вычисления особенно простыми, но он имеет некоторые недостатки, в частности то, что период составляет не более половины модуля. Есть несколько способов обобщить это за счет большего числа умножений на итерацию.

Во-первых, к продукту можно добавить дополнительные члены, получив модуль в виде a _r b ^r + a _s b ^s -1. Это требует вычисления c _n b + x _n = a _r x _{n - r} + a _s x _{n - s} . (Перенос ограничен одним словом, если a _r + a _s ≤ b .)

Однако это не решает проблему периода, которая зависит от младших битов модуля. К счастью, алгоритм редукции Монтгомери допускает другие модули, если они взаимно просты с базой b , и это может применяться для разрешения модуля формы a _r b ^r - a ₀ для широкого диапазона значений a ₀ . Горески и Клэппер ^[5] разработали теорию этих обобщенных генераторов умножения с переносом, доказав, в частности, что выбор отрицательных a ₀ и a _r - a ₀ < bзначение переноса всегда меньше, чем b , что делает реализацию эффективной. Более общий вид модуля также улучшает качество генератора, хотя не всегда можно получить полный период.

Для реализации генератора Горески-Klapper один предварительно вычисляет⁻¹
₀ (mod b ), и меняет итерацию следующим образом: ^[6]

t=c_{n-1}+\sum _{1}^{r}a_{i}x_{n-i},\ x_{n}=a_{0}^{-1}t{\bmod {b}},\ c_{n}=\left\lfloor {\frac {t-a_{0}x_{n}}{b}}\right\rfloor .

В общем случае , что б = 2 ^к , ₀ должно быть нечетным для обратной существовать.

Реализация [ править ]

Ниже приводится реализация алгоритма CMWC в языке программирования Си . Также в программу включена функция инициализации образца. В этой реализации база равна 2 ³² -1, а лаг r = 4096. Период получившегося генератора около . $2^{131104}$

// Генератор дополнительного умножения C99 с переносом #include  <stdint.h>#include  <stdio.h>#include  <stdlib.h>#include  <time.h>// Сколько бит в rand ()? // https://stackoverflow.com/a/27593398 #define LOG_1 (n) (((n)> = 2)? 1: 0) #define LOG_2 (n) (((n)> = 1 << 2 )? (2 + LOG_1 ((n) >> 2)): LOG_1 (n)) #define LOG_4 (n) (((n)> = 1 << 4)? (4 + LOG_2 ((n) >> 4)): LOG_2 (n)) #define LOG_8 (n) (((n)> = 1 << 8)? (8 + LOG_4 ((n) >> 8)): LOG_4 (n)) #define LOG (n) (((n)> = 1 << 16)? (16 + LOG_8 ((n) >> 16)): LOG_8 (n)) #define BITS_TO_REPRESENT (n) (LOG (n) + !! ( (n) & ((n) - 1))) #if ((RAND_MAX | (RAND_MAX >> 1))! = RAND_MAX) #error "Ожидается RAND_MAX, равный 2 ^ n - 1!" #endif #define RAND_BITS BITS_TO_REPRESENT (RAND_MAX)// Рабочие части CMWC #define CMWC_CYCLE 4096 // как рекомендует Марсаглия #define CMWC_C_MAX 809430660 // как рекомендует Марсаглия struct  cmwc_state  { uint32_t  Q [ CMWC_CYCLE ]; uint32_t  c ; // должно быть ограничено CMWC_C_MAX unsigned  i ; };// Собираем 32 бита rand (). Вместо этого вам рекомендуется использовать более качественный источник. uint32_t  rand32 ( недействительно ) { uint32_t  result  =  rand ();  for  ( int  bits  =  RAND_BITS ;  биты  <  32 ;  биты  + =  RAND_BITS )  результат  =  результат  <<  RAND_BITS  |  rand (); вернуть  результат ; }// Инициализировать состояние с помощью seed void  initCMWC ( struct  cmwc_state  * state ,  unsigned  int  seed ) { srand ( seed );  для  ( Int  я  =  0 ;  я  <  CMWC_CYCLE ;  я ++ ) состояние -> Q [ я ]  =  rand32 (); сделать состояние -> c  =  rand32 (); в то время как  ( состояние ->c  > =  CMWC_C_MAX ); состояние -> i  =  CMWC_CYCLE  -  1 ; }// Механизм CMWC uint32_t  randCMWC ( struct  cmwc_state  * state )  // Параметр EDITED * состояние отсутствует { uint64_t  const  a  =  18782 ; // как рекомендует Марсалья uint32_t  const  m  =  0xfffffffe ; // как рекомендует Марсалья uint64_t  t ; uint32_t  x ;состояние -> i  =  ( состояние -> i  +  1 )  &  ( CMWC_CYCLE  -  1 ); t  =  a  *  состояние -> Q [ состояние -> i ]  +  состояние -> c ; / * Пусть c = t / 0xffffffff, x = t mod 0xffffffff * / state -> c  =  t  >>  32 ; x  =  t  +  состояние -> c ; если  ( х <  состояние -> c )  { x ++ ; состояние -> c ++ ; } вернуть  состояние -> Q [ состояние -> я ]  =  m  -  x ; }int  main () { struct  cmwc_state  cmwc ; беззнаковое  целое  семя  =  время ( NULL );initCMWC ( & cmwc ,  семя ); printf ( "Случайный CMWC:% u \ n " ,  randCMWC ( & cmwc )); }

Ниже приведены реализации обобщенных генераторов MWC Goresky-Klapper с 64-битным выходом с использованием 128-битных умножений.

// C99 + __uint128_t Goresky-Klapper GMWC, 128 бит состояния, период ок. 2 ^ 127uint64_t  x  =  0 ,  c  =  1 ;  // Не все нулиuint64_t  inline  next ()  { const  __uint128_t  t  =  0xff8fa3db04bb588e  *  ( __uint128_t ) x  +  c ; x  =  0xd81fdde4eba3aae9  *  ( uint64_t ) t ; c  =  ( t  +  0xadca32a7  *  ( __uint128_t ) x )  >>  64 ; вернуть  x ; }

// C99 + __uint128_t Goresky-Klapper GMWC, 256 бит состояния, период ок. 2 ^ 255uint64_t  x ,  y ,  z ,  c  =  1 ;  // Не все нулиuint64_t  inline  next ()  { const  __uint128_t  t  =  0xff2a4b18846bbee2  *  ( __uint128_t ) x  +  c ; х  =  у ; у  =  г ; z  =  0x94d34db4cd59d099  *  ( uint64_t ) t ; c  =  ( t  +  0x96e36616f07c57  *  ( __uint128_t ) z )  >>  64 ; return  z ;}

Использование [ править ]

Благодаря простоте, скорости, качеству (он очень хорошо проходит статистические тесты) и удивительному сроку, CMWC, как известно, используется в разработке игр, особенно в современных рогаликах . Он неофициально известен как Мать всех ГПСЧ, имя, первоначально придуманное самим Марсалья. ^[7] В libtcod CMWC4096 заменил MT19937 в качестве PRNG по умолчанию. ^[8]

См. Также [ править ]

Мерсенн Твистер
Список генераторов случайных чисел

Ссылки [ править ]

^ Марсалья, Джордж ; Заман, Ариф (август 1995 г.). "CDROM случайных чисел Marsaglia, включающий стойкую батарею тестов на случайность" . Cite journal requires |journal= (help)
^ Marsaglia, ДЖОРДЖ (май 2003). «Генераторы случайных чисел» . Журнал современных прикладных статистических методов . 2 (1): 2–13. DOI : 10.22237 / jmasm / 1051747320 .
^ a b От кутюр, Раймонд; L'Ecuyer, Пьер (апрель 1997 г.). "Распределительные свойства генераторов случайных чисел умножения с переносом" (PDF) . Математика вычислений . 66 (218): 591–607. Bibcode : 1997MaCom..66..591C . CiteSeerX 10.1.1.154.331 . DOI : 10.1090 / S0025-5718-97-00827-2 . Мы увидим, что для дополнительного MWC каждый бит выходного значения является справедливым, то есть две двоичные цифры будут появляться одинаково часто в течение полного периода, свойство, не разделяемое генераторами MWC.
^ Халл, TE; Добелл, АР (июль 1962 г.). «Генераторы случайных чисел» (PDF) . SIAM Обзор . 4 (3): 230–254. Bibcode : 1962SIAMR ... 4..230H . DOI : 10.1137 / 1004061 . hdl : 1828/3142 .
^ a b Гореский, Марк ; Клэппер, Эндрю (октябрь 2003 г.). «Эффективные генераторы случайных чисел с функцией умножения с переносом и максимальным периодом» (PDF) . Транзакции ACM по моделированию и компьютерному моделированию . 13 (4): 310–321. CiteSeerX 10.1.1.4.9190 . DOI : 10.1145 / 945511.945514 .
^ Обратите внимание, что статья Горески и Клэппер^[5] содержит ошибку в уравнении (4): последнее равенство неверно - нельзя исключить второе слагаемое из вычисления переноса.
^ «Мать Марсальи всех генераторов случайных чисел» . home.sandiego.edu .
^ "Генератор случайных чисел - RogueBasin" . www.roguebasin.com . Проверено 30 ноября +2016 .

Марсалья, Джордж (4 июля 2003 г.). «Xorshift RNG» . Журнал статистического программного обеспечения . 8 (14): 1–6. DOI : 10,18637 / jss.v008.i14 .
Марсалья, Джордж (октябрь 2005 г.). «О случайности числа Пи и других десятичных разложениях» . Интерстат . CiteSeerX 10.1.1.694.4783 .
Press, Уильям Х .; Теукольский, Саул А .; Веттерлинг, Уильям Т .; Фланнери, Брайан П. (2007). «Раздел 7.1.2.B Умножение с переносом (MWC)» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.

[Marsaglia95-1] Марсалья, Джордж ; Заман, Ариф (август 1995 г.). "CDROM случайных чисел Marsaglia, включающий стойкую батарею тестов на случайность" . Cite journal requires |journal= (help)

[Marsaglia03-2] Marsaglia, ДЖОРДЖ (май 2003). «Генераторы случайных чисел» . Журнал современных прикладных статистических методов . 2 (1): 2–13. DOI : 10.22237 / jmasm / 1051747320 .

[Couture97-3] От кутюр, Раймонд; L'Ecuyer, Пьер (апрель 1997 г.). "Распределительные свойства генераторов случайных чисел умножения с переносом" (PDF) . Математика вычислений . 66 (218): 591–607. Bibcode : 1997MaCom..66..591C . CiteSeerX 10.1.1.154.331 . DOI : 10.1090 / S0025-5718-97-00827-2 . Мы увидим, что для дополнительного MWC каждый бит выходного значения является справедливым, то есть две двоичные цифры будут появляться одинаково часто в течение полного периода, свойство, не разделяемое генераторами MWC.

[4] Халл, TE; Добелл, АР (июль 1962 г.). «Генераторы случайных чисел» (PDF) . SIAM Обзор . 4 (3): 230–254. Bibcode : 1962SIAMR ... 4..230H . DOI : 10.1137 / 1004061 . hdl : 1828/3142 .

[Goresky03-5] Гореский, Марк ; Клэппер, Эндрю (октябрь 2003 г.). «Эффективные генераторы случайных чисел с функцией умножения с переносом и максимальным периодом» (PDF) . Транзакции ACM по моделированию и компьютерному моделированию . 13 (4): 310–321. CiteSeerX 10.1.1.4.9190 . DOI : 10.1145 / 945511.945514 .

[6] Обратите внимание, что статья Горески и Клэппер^[5] содержит ошибку в уравнении (4): последнее равенство неверно - нельзя исключить второе слагаемое из вычисления переноса.

[7] «Мать Марсальи всех генераторов случайных чисел» . home.sandiego.edu .

[8] "Генератор случайных чисел - RogueBasin" . www.roguebasin.com . Проверено 30 ноября +2016 .

[1]