Генератор Фибоначчи с запаздыванием

Генератор Фибоначчи с запаздыванием ( LFG или иногда LFib ) является примером генератора псевдослучайных чисел . Этот класс генераторов случайных чисел призван стать усовершенствованием «стандартного» линейного конгруэнтного генератора . Они основаны на обобщении последовательности Фибоначчи .

Последовательность Фибоначчи можно описать рекуррентным соотношением :

S_{n}=S_{n-1}+S_{n-2}

Следовательно, новый член представляет собой сумму двух последних членов последовательности. Это можно обобщить до последовательности:

S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod {m}},0<j<k

В этом случае новый термин представляет собой некоторую комбинацию любых двух предыдущих терминов. m обычно представляет собой степень 2 ( m = 2 ^М), часто 2 ³² или 2 ⁶⁴. $\star$ Оператор обозначает общую бинарную операцию . Это может быть сложение, вычитание, умножение или побитовый оператор «исключающее ИЛИ» ( XOR ). Теория генератора этого типа довольно сложна, и простого выбора случайных значений для j и k может быть недостаточно . Эти генераторы также имеют тенденцию быть очень чувствительными к инициализации.

Генераторы этого типа используют k слов состояния (они «запоминают» последние k значений).

Если используется операция сложения, то генератор описывается как аддитивный генератор Фибоначчи с запаздыванием или ALFG, если используется умножение, то это мультипликативный генератор Фибоначчи с запаздыванием или MLFG, а если используется операция XOR, он называется двух- коснитесь сдвигового регистра с обобщенной обратной связью или GFSR. Алгоритм Mersenne Twister является разновидностью GFSR. GFSR также связан с регистром сдвига с линейной обратной связью или LFSR.

Свойства генераторов Фибоначчи с запаздыванием

Максимальный период генераторов Фибоначчи с запаздыванием зависит от двоичной операции. $\star$ . Если используется сложение или вычитание, максимальный период составляет (2 ^к − 1) × 2 ^{М −1}. Если используется умножение, максимальный период равен (2 ^к − 1) × 2 ^{М −3}, или 1/4 периода аддитивного случая. Если используется побитовое исключающее ИЛИ, максимальный период равен 2. ^к − 1.

Чтобы генератор достиг этого максимального периода, полином:

у = х ^к + х ^дж + 1

должен быть примитивным над целыми числами по модулю 2. Значения j и k, удовлетворяющие этому ограничению, были опубликованы в литературе.

Популярные пары примитивных полиномиальных степеней ^[1]^[2]
дж	7	5	24	65	128	6	31	97	353	168	334	273	418
к	10	17	55	71	159	31	63	127	521	521	607	607	1279

Другой список возможных значений j и k находится на странице 29 тома 2 книги « Искусство компьютерного программирования» :

(24, 55), (38, 89), (37, 100), (30, 127), (83, 258), (107, 378), (273, 607), (1029, 2281), (576, 3217), (4187, 9689), (7083, 19937), (9739, 23209)

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

Если используется сложение, требуется, чтобы хотя бы одно из первых значений k , выбранных для инициализации генератора, было нечетным. Если вместо этого используется умножение, требуется, чтобы все первые значения k были нечетными и, кроме того, чтобы хотя бы одно из них было ±3 по модулю 8. ^[3]

Было высказано предположение, что хорошие соотношения между j и k примерно соответствуют золотому сечению . ^[4]

Проблемы с свалочными газами

В статье о сдвиговых регистрах с четырьмя отводами Роберт М. Зифф , ссылаясь на LFG, использующие оператор XOR, утверждает, что «сейчас широко известно, что такие генераторы, в частности с правилами двух отводов, такими как R(103, 250), имеют серьезные недостатки, Марсалья заметил очень плохое поведение генераторов R(24, 55) и меньшего размера и посоветовал вообще не использовать генераторы этого типа... Основная проблема двухотводных генераторов R(a, b) заключается в том, что они имеют встроенную трехточечную корреляцию между $x_{n}$ , $x_{n-a}$ , и $x_{n-b}$ , просто задается самим генератором... Пока эти корреляции разбросаны по размеру $p=max(a,b,c,\ldots )$ самого генератора, они, очевидно, все еще могут привести к значительным ошибкам.". ^[5] Это относится только к стандартному LFG, где каждое новое число в последовательности зависит от двух предыдущих чисел. Было показано, что LFG с тремя касаниями устраняет некоторые статистические проблемы, такие как провал тестов «Интервалы между днями рождения» и «Обобщенные тройные тесты». ^[4]

Использование

Freeciv использует генератор Фибоначчи с задержкой с {j = 24, k = 55} в качестве генератора случайных чисел.
Библиотека Boost включает реализацию генератора Фибоначчи с запаздыванием.
Subtract с переносом , механизм генератора Фибоначчи с запаздыванием, включен в библиотеку C++11 .
База данных Oracle реализует этот генератор в своем пакете DBMS_RANDOM (доступном в Oracle 8 и более поздних версиях).

См. также

На странице Википедии « Список генераторов случайных чисел » перечислены другие ГПСЧ, в том числе с лучшими статистическими качествами:

Ссылки

На пути к универсальному генератору случайных чисел , Г.Марсалья, А.Заман

^ «Глава РН» . www.ccs.uky.edu . Архивировано из оригинала 9 марта 2004 года . Проверено 13 января 2022 г.
^ «SPRNG: масштабируемая библиотека параллельного генератора псевдослучайных чисел» . Архивировано из оригинала 14 июня 2010 г. Проверено 11 апреля 2005 г.
^ Параметризация параллельных мультипликативных генераторов Фибоначчи с запаздыванием , М. Масканьи, А. Шринивасан
↑ Перейти обратно: Перейти обратно: ^а ^б «Унифицированные генераторы случайных чисел для суперкомпьютеров» , Ричард Брент, 1992 г.
^ «Генератор случайных чисел со сдвиговыми регистрами и четырьмя отводами» , Роберт М. Зифф, Компьютеры в физике, 12 (4), июль/август 1998 г., стр. 385–392

[1] «Глава РН» . www.ccs.uky.edu . Архивировано из оригинала 9 марта 2004 года . Проверено 13 января 2022 г.

[2] «SPRNG: масштабируемая библиотека параллельного генератора псевдослучайных чисел» . Архивировано из оригинала 14 июня 2010 г. Проверено 11 апреля 2005 г.

[3] Параметризация параллельных мультипликативных генераторов Фибоначчи с запаздыванием , М. Масканьи, А. Шринивасан

[uniform-4] Перейти обратно: Перейти обратно: ^а ^б «Унифицированные генераторы случайных чисел для суперкомпьютеров» , Ричард Брент, 1992 г.

[5] «Генератор случайных чисел со сдвиговыми регистрами и четырьмя отводами» , Роберт М. Зифф, Компьютеры в физике, 12 (4), июль/август 1998 г., стр. 385–392

[1]

[2]

[3]

[4]

[5]