Трехмерное обобщение генератора LFSR случайных точек

История разработки генераторов псевдослучайных последовательностей насчитывает несколько десятилетий. Разработано множество генераторов, реализующих различные алгоритмы и идеи. Однако большинство из созданных генераторов являются одномерными [1]: выходная последовательность такого генератора состоит из точек определенного промежутка числовой прямой, чаще всего (0.1]. Генерация последовательности с заданным законом распределения обычно осуществляется путем преобразования равномерно распределенной последовательности [2].

Развитие многопроцессорных систем, создание параллельных алгоритмов специфика реальных задач обуславливают необходимость разработки пара-леллельных генераторов, генераторов, производящих многомерные последовательности [2] (последовательности точек в пространстве R n [3]).

Исследованы [3, 4, 5] методы генерации таких последовательностей основанные на разбиении одномерной псевдо-случайной последовательности, использовании нескольких одномерных генераторов различных типов или одного типа с различными параметрами.

В данной работе рассматривается принципиально иная процедура генерации трехмерной псевдослучайной последовательности точек. Предлагаемая процедура основана на обобщении одномерного генератора Таусворта [7] (Tausworthe generator, linear feedback shift register generator, LFSR). Состояние (битовый вектор) генератора интерпретируется как цифры представления элементов кольца целых чисел в кубическом расширении поля рациональных чисел Z [ θ ] в канонической системе счисления (сanonical number system, CNS [10]).

Предложенный метод был использован для вычисления многомерных интегралов методом Монте-Карло. Результаты численного эксперимента и сравнение с предложенной схемы с другими генераторами приведены в разделе 4.2.

1.    Генератор Таусворта

Процедура генерации Таусворта [7, 8] основана на использовании последовательности, заданной линейным рекуррентным соотношением в конечном поле из двух элементов GF(2) . Блоки элементов этой последовательности (битовые блоки) рассматриваются как цифры записи дробной части некоторого числа в двоичной системе счисления.

Определим процедуру генерации Таусворта более формально. Пусть GF (2) – конечное поле из двух элементов. Далее рассмотрим многочлен

P(z) = zm-a1zm-1 -...-am , aj ∈ GF(2) ,(1)

характеристический многочлен рекуррентного соотношения (2)

xn=a1xn-1+a2xn-2+...+akxn-m(mod2) .(2)

Пусть si – состояние генератора (вектор бит) si=(xi,xi+1,...,xi+m-1)∈{0,1}m .(3)

Будем полагать, что задано начальное состояние s 0 = ( x 0 , x 1 ,..., x m - 1 ) ∈ {0,1} ^m .

Рассмотрим рациональное число u_n , представление которого в двоичной системе счисления имеет вид:

L un= ∑ xnq+i-1 ⋅ 2-i ,                                (4)

i = 1

где q и L натуральные. Если многочлен (1) не приводим, s 0 ≠ 0 и НОК( q , 2 ^m - 1) = 1, тогда периоды последовательностей     x n    и     u n    равны

ρ ( x_n ) =ρ ( u_n ) = 2 ^m - 1 [8] (в этом случае, x n и u n -последовательности максимального периода, x n называется m -последовательностью [9]).

Свойства генератора Таусворта изучены, существуют методы супер-быстрого вычисления элементов последовательности (3), если характеристический многочлен (1) является трехчленом особого вида [8].

2.    Канонические системы счисления

Предлагаемый метод генерации основывается на использовании канонических систем счисления (canonical number systems), введенных в [10] и исследованных многими авторами в [11], [12] и др.

Приведем формальное определение канонической системы счисления. Назовем решеткой (lattice) Λ в R k множество всех линейных комбинаций с целыми коэффициентами k линейно независимых векторов .

Рассмотрим решетку Λ , групповой эндоморфизм M : Λ →Λ , det( M ) ≠ 0, и множество D , конечное подмножество Λ , 0 ∈ D .

Тройка объектов ( Л , M , D ) называется системой счисления (или, иначе, тройка ( Л , M , D ) обладает свойством единственности представления ), если для любого элемента n е Л существует единственное представление вида (5):

l n = Z Miai ,                                (5)

i = 0

где a i е D и l >  0, l е X .

В этом случае, эндоморфизм M называется основанием системы счисления, а D - множеством цифр .

Система счисления ( X k , M , D ) называется канонической , если D образует полную систему вычетов по модулю M и

D = { ve i ,v = 0,1,...,|det M\ - 1},                    (6)

где e ₁ = (1,0...0).

Рассмотрим канонические системы счисления, генерируемые многочленами с целыми коэффициентам. Рассмотрим многочлен f (x) = CkXk + Ck-1 xk-1 + ... + C0 = = (x-61)...( x-9 k), Ck = 1.

Обозначим Л f кольцо классов вычетов X [ x ]/( f ).

Пусть, далее в = x + ( f ) - образ x в Л f . Нетрудно заметить, что множество I р = { ро , оеЛ f } представляет собой идеал, порождающий фактор-кольцо Л f / 1 р .

Выбирая по одному элементу из каждого класса эквивалентности в Л f / 1 р , можно сформировать множество цифр (6)

Введя в кольце Лf эндоморфизм Mр (а) = ва, можно показать [12], что для определенных многочленов (7), тройка (Л f, Mр, Dp) обладает свойством единственности представления.

Многочлены, генерирующие канонические системы счисления (CNS-полиномы), могут быть найдены с помощью алгоритма CNS-Sieve, предложенного в [12]. В этой работе также вычислены многочлены (7) степени до 8, порождающие бинарные канонические системы счисления, D = {0,1}.

Необходимо отметить, что, так как CNS-многочлены не приводимы, то соответствующие фак-тор-кольца X [x ]/( f j ) изоморфны алгебраическим расширениям Z [ 6 ], порожденным корнями f j ( x ).

Далее в данной работе будут использованы бинарные канонические системы счисления в Z [ 6 ], порожденные многочленами (8).

• f. = 2 + x³,

3.    Трехмерное обобщение генератора Таусворта. Генератор LFSR-CNS

f 2 = 2 - x + x ³ , (8)

f 5 = 2 + x + x ² + x ³ , f 4 = 2 + 2 x + 2 x ² + x ³ .

На втором этапе схемы генерации Таусворта последовательности бит (2) интерпретируется как цифры записи дробной части некоторого числа в двоичной системе счисления (3).

По аналогии, рассмотрим последовательность (2) как последовательность цифр представления разложения (5), представления элементов Л f в бинарной канонической системе счисления, порожденной одним из многочленов (8).

Конкретизируя схему генерации, положим, q = 1; L = m , тогда выражение (4) примет вид:

m - 1

u n = £ M i x +i , i = 1

где x i е {0,1} = D f .

Таким образом, каждому вектору состояния (3) s i генератора (2) поставлен в соответствие элемент U n е Л f .

Для f е { f₁,..., f 4 }   можно   показать,   что,

Лf = Z[6] = Z3. Таким образом, каждому вектору si поставлен в соответствие элемент «трехмерного пространства».

Заметим, что вследствие уникальности представления (5), различным векторам s_i соответствуют различные элементы n е Л f , а, следовательно, и точки X ³ .

Множество U точек X ³ , соответствующих всем возможным векторам s_i , представляет собой область сложной (фрактальной) формы. Это множество можно считать аналогом фундаментальной области [0,1) для одномерного случая [13]. На рис. 1-3 приведены примеры областей для рекуррентных соотношений (2) порядка 3t с периодом р = 2 ³ t - 1.

Рис. 1. U , соответствующее f 2 и t = 3

^^j^^^

Рис. 2. U , соответствующее f 3 и t = 3

Рис. 3. U , соответствующее / 4 и t = 3

Определим в пространстве X ³ куб

C = { z : z е X ³ ,0 <  z i <  2 t , i = 0,1,2}.            (10)

Рассмотрим точки й n е U и u n е C . Определим взаимно однозначное соответствие:

• 1.    u n = u n , если u n g C .

• 2.    если й_n 6 С , то вместо й_n будем брать точку u n е C , полученную параллельным переносом й_n с шагами ( a , b , c ) , лежащую в другой в другой «чешуйке» из U .

• 4.    Свойства LFSR–CNS генератора

• 4.1    Спектральные свойства

• 4.2    Интегрирование по методу Монте-Карло

Таким образом, каждому вектору состояния s i взаимнооднозначно ставится в соответствие элемент куба (10) или, после масштабирования, куба [0,1) ³ .

Генератор LFSR-CNS – трехмерный генератор псевдо–случайных последовательностей. Так как генератор получен путем альтернативной интерпретации второго этапа генератора Таусворта, он наследует как «плохие», так и «хорошие» свойства базового генератора. Однако данный генератор обладает также и новыми свойствами.

При использовании рекуррентных соотношений, соответствующих m -последовательностям максимального периода р = 23t -1, на выходе генератора появятся все 23t -1 точки сетки (с шагом 2—t) трехмерного единичного куба (кроме точки (0,0,0)).

В отличие от классических схем распараллеливания одномерных генераторов, осуществляемых методом leapfrog [6], рассмотренный алгоритм обладает лучшими характеристиками в смысле спектрального критерия предложенного в [2] в трехмерном пространстве.

Для экспериментальной оценки свойств генератора могут быть использованы различные методы [14], в частности вычисление многомерных интегралов по методу Монте-Карло.

Было произведено вычисление интеграла

I j = UI y j ^{( z} ) ^dz ’                            ⁽¹¹⁾

z е [0,1)³

некоторых классов функций путем вычисления сумм

N - 1

I j = Т7 I y j (u i ).                             (12)

N i = 0

Последовательности u_i ^{( k )} в суммах (12) сгенерированы с использованием LFSR-CNS генератор и других генераторов MC1-MC4 использованных Н.М. Коробовом [15].

В качестве подынтегральных функций были использованы

У 1 ( z ) = 8 z 0 z 1 z 2 ; У 2 ( z ) = y( z 0 + 3 z 1 - z 2 ); (13,14)

У3(z) = 11 - 4e z0z2z2ez0z1 z2;(15)

У4(z) = 8^7/21Л(1 -zj)-2e-™z22)/<1-zjV ;(16)

3/2 n m = 1,10,30,60.

Точное значение интеграла (11) для функций (13)-(16) равно 1. Количество точек сетки N ~ 4 - 10 ³ . Был использован LFSR-CNS генератор, соответствующий f 1 и t = 7. Результаты эксперимента представлены в таблице 1.

Результаты, полученные с помощью методов MC1–MC4, заимствованы из [15].

Заключение

Предложенный метод генерации псевдо-случайных последовательностей, благодаря «естественной трехмерности», может быть широко использован при решении различных 3D задач (например для работы с 3D Ising models [16]). Существование CNS-полиномов более высоких степеней обуславливает возможность увеличения «естественной размерности».

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

Таблица 1. Вычисление трехмерного интеграла методом Монте-Карло при использовании различных генераторов случайных чисел

Подынтегральные функции	Метод неравномерных сеток	Методы Монте-Карло
		1	2	3	4	Предлагаемый метод
y 1	0,39	0,78	1,05	1,02	1,01	0,997
y 2	0,73	0,94	0,997	1,008	1,008	0,998
y 3	0,81	0,75	1,07	1,04	0,98	0,987
y 4 (m=1)	1,03	1,23	1,02	0,92	0,98	1,01
y 4 (m=10)	1,38	1,67	1,32	0,84	0,79	0,914
y 4 (m=30)	3,22	2,49	0,88	0,92	0,94	0,971
y 4 (m=30)	7,49	3,87	0,54	0,53	1,15	1,037

Большое влияние на свойства данного генератора оказывает тип использованной рекуррентной последовательности. При дальнейшем развитии теории генераторов Таусворта (LFSR-генераторов) полученные результаты могут быть легко обобщены на случай рассматриваемого LFSR-CNS генератора.

Данная работа была выполнена при финансовой поддержке Министерства образования и науки РФ, Администрации Самарской области, Фонда гражданских исследований и развития США (CRDF Project SA-014-02) в рамках совместной Российско-Американской программы «Фундаментальные исследования и высшее образование» (BHRE), а также Российского фонда фундаментальных исследований (гранты №№ 05-01-96501, 03-01-00736).