Рандомизация последовательности конгруэнтных чисел

Т.В. Митянкина,

В.В.Швыдкий, к.т.н., доцент,

А.И. Щерба, к.ф-м.н., доцент.

РАНДОМИЗАЦИЯ ПОСЛЕДОВАТЕЛЬНОСТИ КОНГРУЭНТНЫХ ЧИСЕЛ

Черкасский государственный технологический университет

Введение

Генератор линейных конгруэнтных чисел ( в дальнейшем- генератор) - устройство, решающее уравнение

(1)

где К,С,М- параметры генератора, s(n) и s(n-1) -числа, порожденные генератором в «n» и в

(n-1) - дискретный момент времени.

Такие генераторы широко используются во всех сферах человеческой деятельности, где необходимо использование случайных последовательностей. Данный генератор порождает случайную, а точнее псевдослучайную периодически повторяемую последовательность чисел (ПСП), которая представляет последовательность вычетов по модулю М и может принимать любые значения из интервала [0,(М-1)]. Однако, из этого совсем не следует, что последовательность, порождаемая генератором, есть периодически повторяемая последовательность равновероятно распределенных чисел интервала [0,(М-1)], а мощность множества состояний в пределах периода повторения равна М. Реально генератор порождает несколько циклов, длина которых

t ? (M -1),

при этом какой из циклов будет порождаться генератором определяется значением его параметров и выбором вектора начальной загрузки. Это значит, что при фиксированных параметрах К, С, М генератор, не является генератором равновероятно распределенной последовательности чисел, а является генератором ПСП чисел, распределение которых может существенно отличаться от равномерного, хотя бы по той причине, что порождаемая последовательность содержит не все символы алфавита (0..(М-1)).

При решении множества прикладных задач необходимы генераторы равновероятно распределенных на некотором интервале чисел. Такие генераторы часто строятся на основе аналоговых генераторов «белого» шума, которым присуща температурная и временная нестабильность и, которая порождает дрейф равновероятного распределения чисел в сторону не равновероятного. Поэтому актуальной является задача построения генераторов равновероятно распределенных чисел, не использующих аналоговые шумящие элементы. Данная цель, в частности, может быть достигнута путем рандомизации псевдослучайной последовательности чисел, порождаемой генератором линейных конгруэнтных чисел.

Анализ источников и публикаций

Наиболее полно анализ генераторов ПСП выполнен в работе [1]. В ней в частности показано, что получение равновероятно распределенной последовательности чисел интервала [а,в] совсем непростая задача не только для генераторов линейных конгруэнтных чисел, но и для других генераторов ПСП, например, для генераторов на основе чисел Блюма или Фибоначчи. Для линейных конгруэнтных последовательностей приведены рекомендации по выбору значений К,С,М, обеспечивающих максимальное приближение ПСП к последовательности равновероятных чисел.

Выделение нерешенных ранее частей общей проблемы

При всей глубине анализа принципов получения ПСП, аналитические выражения, связывающие выбор К,С,М со статистикой генерируемой последовательности не существуют. Это значит, что задача подбора К,С,М, должна выполняться «в слепую», что не гарантирует ни решения задачи вообще, ни решения задачи за заданный интервал времени, в частности.

Целью настоящей работы является преобразование псевдослучайной последовательности линейных конгруэнтных чисел, порожденных уравнением (1), в равновероятно распределенную на интервале [0, (M-1)] последовательность из М чисел, путем выполнения процедуры рандомизации.

Постановка задачи

С целью решения поставленной задачи исследуем циклы генератора линейных конгруэнтных чисел, а затем решим вопрос объединения этих (коротких) циклов в одну последовательность длиной, равной интервалу[0, (M-1)] , т.е. интервалу равному сумме всех циклов генератора.

Решение задачи

В качестве первого шага решения поставленной задачи дадим следующие определения:

Цикл - упорядоченное по времени подмножество символов из множества М.

Нуль цикл - цикл, содержащий один элемент множества М.

Сверхцикл-объединение циклов в единый цикл длиной М путем присоединения подмножеств, входящих в каждый цикл.

Гиперцикл-объединение сверхциклов с разным порядком следования элементов в сверхцикле, полученный путем присоединения сверхциклов.

Вектор начальной загрузки (ВНЗ) - одно из чисел множества М, загружаемое в начале цикла, как число S(n-1).

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

Утверждение

Один или группа символов из множества (0..(М-1)) не может принадлежать двум или более циклам.

Доказательство

Из уравнения (1) следует, что из S(n-1) однозначно вычисляется S(n), это возможно только для циклов рис. 1б, для циклов рис. 1а, это невозможно, поскольку нужна дополнительная информация - какому циклу принадлежит точка касания (или точка пересечения) циклов, что не обеспечено уравнением (1). Что и утверждается.

Следствия

1 Циклы генератора конгруэнтных чисел, разбивают множество из М чисел на непересекающиеся подмножества;

2. Циклы могут быть объединены. Для этого в конце каждого цикла в качестве вектора начальной загрузки в генератор записывается число-представитель другого цикла. После перебора представителей всех циклов (включая нуль цикл) без повторения и изъятий, образуется сверхцикл, включающий все М элементов множества только по одному разу.

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

Рис. 1 Невозможное и возможное сочетание циклов генератора конгруэнтных чисел

Теперь определим циклы генератора. Самым простым способом является непосредственное применение уравнения (1) и модифицированного «решета Эратосфена », который продемонстрируем на примере 1.

Пример 1. Выберем М=43, К==11, С=3.

Этот генератор будет давать ПСП из множества (0..(М-1)), мощность которого равна М.

Запишем по порядку все числа этого множества, загрузим любой вектор начальной загрузки (например, 0) и будем генерировать числа до завершения цикла. Получим последовательность 0, 3,36,12,26,31 . Вычеркнем из списка (0..(М-1)) элементы первого цикла, введем в качестве вектора начальной загрузки любой другой элемент из не вычеркнутой части списка и повторим процедуры генерации и вычеркивания до тех пор, пока в списке не останется не вычеркнутых элементов. Тогда получим:

Таблица 1 - Конструкция циклов

Это значит, что данный генератор производит 6 циклов длиной 7 символов и один нуль цикл.

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

Теорема

Множество состояний генератора линейной конгруэнтной последовательности обязательно содержит один нуль цикл и равные по длине ненулевые циклы. Число ненулевых циклов и их длина определяются разложением числа (М-1) на простые сомножители.

Доказательство

Прежде всего, докажем, что нулевой цикл единственный.

Положим, что элементы s₁ и s₂ множества (0..(М-1)), порождают два разных нуль цикла. Учтем, что если s₁ и s₂ нуль циклы, то для любого «j»

.

Тогда запишем:

(2)

(3)

Поскольку вычеты не превышают величины (М-1), то расстояние между точками s₁ и s₂ на отрезке [0,(М-1)] не может превышать величины (М-1), что выполняется только при q₁=q₂.

Тогда

(4)

Это равенство выполнимо в том и только в том случае, если s₁=s₂, что доказывает единственность нуль цикла на отрезке [0,(М-1)].

Теперь докажем, что остальные элементы отрезка [0,(М-1)] образуют равные по длине ненулевые циклы. Для этого воспользуемся (1) и при некотором векторе начальной загрузки s₀, выпишем последующие элементы цикла:

.

Тогда для элемента «m» цикла получим:

(5)

При циклической структуре последовательности и длине цикла t получим :

,

Тогда

. (6)

Учтем, что

тогда окончательно:

(7)

Отсюда, решая в целых числах уравнение(7), при фиксированных К,С,М, можно найти все циклы, в зависимости от ВНЗ.

Обратим внимание, что из теоремы Ферма, утверждающей, что при любом

следует, что уравнение (7) периодично по некоторому

m=t и m<(M-1),

где t-период цикла.

Это так же значит, что из М символов множества (0..(М-1)) один символ приходится на нуль цикл, а остальные (М-1) символов распределяются по d циклам равной длины t , где d и t числа из разложения числа (М-1) на простые сомножители, т.е.

(М-1)=d•t. (8)

Теорема доказана.

Применительно к примеру 1, число

(М-1)= 42=2х3х7

может порождать циклы вида

1х42,2х21, 6х7.

Какое из этих соотношений будет иметь место в конкретном генераторе, определяется выбором параметра К.Конфигурации циклов при М=43 и С=3 в зависимости от К приведены в примере 2.

Пример2.

При К=19 для ВНЗ=0 Структура последовательности имеет вид: 3, 17, 25, 5, 12, 16, 6, 31, 33, 28, 19, 20, 39, 13, 35, 23, 10, 21, 15, 30, 14, 11, 40, 32, 9, 2, 41, 8, 26, 24, 29, 38, 37, 18, 1, 22, 34, 4, 36, 42, 27, 0.

Конструкция циклов - 1х42. Длина цикла равна 42, нуль цикл - число 7.

При К=13 структура последовательности имеет вид:

Конструкция циклов- 2х21, длинна цикла 21, нуль цикл - число 32.

При К=41 структура последовательности имеет вид:

Конструкция циклов - 6х7, длинна цикла 7, нуль цикл - число 1.

При К=37 структура последовательности имеет вид:

Конструкция циклов - 7х6, длинна цикла 6, нуль цикл-число 25.

Отсюда следует, что в генераторе конгруэнтной последовательности чисел:

-число М определяет интервал (0..(М-1)), в котором можно получить равновероятное распределение чисел;

- разложение числа (М-1) на простые сомножители определяет диапазон возможных значений конструкции циклов,

-число С определяет состав чисел, входящих в цикл.

Теперь решим задачу объединения циклов в сверхцикл. Решение этой задачи продемонстрируем на примере данных таблицы 1. Этот генератор порождает 7 циклов длины 6 и нуль цикл. Для получения равновероятно распределенной последовательности необходима буферная память, в которую запишем в произвольном порядке по одному представителю каждого кольца (одну из строк таблицы), например, строку 0, 1, 11,13,15,16,4. Выберем один элемент этой таблицы и введем его в качестве вектора начальной загрузки в генератор. Выбор производится в произвольном порядке или упорядоченно, например, в порядке возрастания (убывания). Здесь, как пример, используем ВНЗ в том порядке, в котором записаны в память, т.е. число 0. Далее подаются 6 тактов, обеспечивающих генерацию и вывод получателю первых 6 символов последовательности, т.е. первый столбец (числа 3, 36, 12, 6, 26, 31) на последнем седьмом такте цикла генерируется и выводится седьмой элемент цикла - число 0 при этом последовательность принимает вид 3, 36, 12, 6, 26, 31, 0 и загружается следующий вектор начальной загрузки (число 1). Следующие семь тактов порождают следующие 7 символов последовательности 14, 28, 10, 27, 42, 35, 1. Так продолжается до тех пор, пока не будут перебраны все вектора начальной загрузки, включая ноль цикл.

В результате этих действий получим псевдослучайную последовательность чисел длинной М, в которой каждый символ множества (0..(М-1)) использован только один раз. Однократное применение символов определяет равновероятное распределение чисел на интервале(0….(М-1)), при этом сама последовательность будет соответствовать последовательность чисел таблицы 1, если ее последовательно читать по столбцам. Выполненная операция последовательного обхода контура графа состояний по своей сути есть процедура рандомизации. Порядок обхода контура, начальная и конечная точка обхода могут быть выбраны множеством способов, при этом каждый раз получится сверхцикл длинной М символов, но с разной структурой чередования циклов. Учтем, что начальная точка обхода контура графа состояний определяется выбором вектора начальной загрузки. Вектор начальной загрузки в каждом из циклов может быть выбран t способами, а порядок обхода контуров, с учетом нуль цикла, может быть выбран (d+1)! способами, что позволяет объединить разные сверхциклы в один гиперцикл полной длины

(9)

При этом, элементом гиперцикла будем считать присоединение двух символов. Для примера образуем гиперцикл по таблице 1.

Запишем в буферную память последовательность чисел, составленную из представителей каждого кольца (включая нуль цикл) и расположим ее в порядке возрастания, получим 0, 1, 4, 11, 13, 15, 16. Если сгенерировать первый сверхцикл длины М, соответствующей этой последовательности векторов начальной загрузки, то получим последовательность, приведенную в таблице с тем дополнением, что нуль цикл расположен третьим по порядку обхода и имеет единичную длину. Если в процессе генерации сверхцикла в дополнительную буферную память записывать один элемент из каждого кольца, например, первый элемент цикла, то к концу первого сверхцикла в этой памяти будем иметь вторую строку таблицы 1,дополненную числом 4, т.е числа 3, 14, 4, 38, 17, 39, 7. Упорядочим их в порядке возрастания и перепишем в первый буфер для использования в качестве вектора начальной загрузки, получим 3,4,7, 14, 17, 38, 39.

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

Полученные результаты

Таким образом, всегда существует возможность преобразования последовательности конгруэнтных чисел в равновероятно распределенную последовательность чисел интервала[0,М-1], при условии объединения циклов (включая нуль цикл) в сверхцикл. Для объединения циклов в сверхцикл необходимо априорно определить циклическую структуру генератора по уравнению (1), вычислить по одному представителю каждого цикла, включая нуль цикл и записать их в память. При применении генератора конгруэнтной последовательности чисел, в качестве генератора равновероятно распределенных чисел, из памяти выбирается случайным образом без изъятий и повторений представитель какого либо цикла, выводится как результат генерации и вводится в качестве вектора начальной загрузки для генерации цикла. Процедура выбора и генерации цикла повторяется, пока не будут сгенерированы все циклы.

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

- изменением начальной фазы каждого из циклов сверхцикла;

- изменением порядка чередования циклов в сверхцикле.

Изменение начальной фазы каждого из циклов в сверхцикле обеспечивается изменением вектора начальной загрузки. Для этого в процессе генерации сверхцикла (списка (0..(М-1)) после того, как загружен ВНЗ), выбирается и записывается в память (вместо использованного) следующий представитель цикла, что и обеспечивает поочередную смену вектора начальной загрузки в каждом из сверхциклов.

Изменение порядка чередования циклов в сверхцикле достигается «перетасовкой» порядка обхода циклов в сверхцикле. Для этого в памяти представителей циклов упорядочим представителей по возрастанию (убыванию). Если выборку и загрузку ВНЗ производить по возрастанию (убыванию), то в каждом сверхцикле будет меняться и сам ВНЗ, как начальная фаза цикла, так и порядок объединения циклов в сверхцикл.

Предложенная методика рандомизации последовательности конгруэнтных чисел позволяет конструировать генераторы равновероятно распределенной в интервале (0..(М-1)) последовательности чисел в виде последовательности следующих действий:

1. Выбирается простое число М, отсюда вытекает интервал равновероятных чисел (0..(М-1)) и разложение числа (М-1) на простые сомножители;

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

Выводы

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

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

Литература

1. Иванов М.А., Чугунков И.В "Теория, применение и оценка качества генераторов псевдослучайных последовательностей" М., издательство: Кудиц - образ ,2003, 238стр

2. Андронов И.К., Окунев А.К. Арифметика рациональных чисел, Москва, «Просвещение»,1971, стр. 399.