Целью диссертационной работы является разработка новых методов синтеза и исследование свойств многомерных генераторов, порождаемых рекуррентными процессами и базирующихся на концепции позиционных систем счисления в многомерных дискретных решетках.
Актуальность темы
Методы статистического моделирования, методы Монте Карло получили большое распространение и применяются в различных областях: от моделирования сложных физических явлений (распространения излучения в земной атмосфере, субъядерных процессов физики высоких энергий, неламинарного течение жидкости и разреженного газа, химической кинетики и процессов горения [1]) до теоретического анализа эффективности различных финансовых инструментов, решения задач эконометрики и предсказания значений индекса Доу-Джонса [3]. Разработаны вычислительные методы Монте Карло для решения стохастических дифференциальных уравнений, задач с граничными условиями для уравнений в частных производных [2], интегральных уравнений, вычисления значений многомерных интегралов и интегралов по контуру [4].
К методам Монте Карло можно отнести численные методы статистического моделирования, основанные на получении большого числа реализаций случайного процесса с вероятностными характеристиками, совпадающими с гипотетическими характеристиками решаемой задачи. Несмотря на применение метода (в наивной форме) в течение нескольких столетий, историю метода Монте Карло принято отсчитывать с публикаций Уламом и Метрополисом в 1944 году работы [6]. За последующие десятилетия своего существования метод был развит до состояния мощного математического аппарата, используемого для решения сложных вычислительных задач [4].
В отличие от классических методов исследования реальных физических или математических систем, центральное место среди которых занимает численное решение обыкновенных дифференциальных уравнений или уравнений в частных производных, описывающих поведение физической или математической системы, метод Монте Карло моделирует эволюции физической или математической системы непосредственно, при условии что исследуемая величина может быть рассмотрена как случайная величина в некотором вероятностном пространстве.
Метод Монте Карло состоит из следующих этапов:
Этап I. Определение области (множества) входных значений (параметров) и вероятностных характеристик входных параметров.
Этап 2. Формирование (многократное) случайной выборки входных значений из заданной области, и вычисление выходного значения (решения задачи, соответствующего сформированной выборке).
Этап 3. Агрегация результатов вычислений, полученных на предыдущем этапе: вычисление статистической оценки значения исследуемой величины.
Пример 0.1. В качестве примера применения метода Монте Карло рассмотрим вычисление значения определенного интеграла. где 5сК 0<<со. Здесь и далее Я, будем обозначать 5-мерную меру Лебега. Для / е!1^), оценка значения многомерного интеграла по методу Монте Карло удовлетворяет соотношению:
Здесь {йн} — множество узлов квадратурной формулы (множество случайных векторов равномерно распределенных в В).
Заметим, что эффективность моделирования (0.2) по методу Монте Карло определяется не только адекватностью стохастической модели физической или математической системы (этап 1), но и, в значительной степени, свойствами используемой случайной выборки (этап 2) [9]. Развитие методов Монте Карло дало толчок теории, методологии и вычислительным методам формирования случайных выборок. Применение случайных последовательностей для реализации алгоритмов на базе метода Монте Карло является классическим. В настоящее время случайные последовательности и выборки находят новые области применения: используются в вычислительной статистике, при реализации вероятностных алгоритмов, тестировании сверхбольших интегральных схем, в задачах криптографии, в компьютерных играх [9].
0.1).
0.2).
В обобщенном виде, задача формирования случайной выборки может быть сформулирована следующим образом:
Пусть задана случайная величина X с функцией распределения F{x) = Р (.- < X). Требуется сформировать мноэ/сество чисел {.vj свойства которого имитируют (в терминах определенных критериев качества) свойства множества независимых pecuiu3aicuii случайной величины X.
Существует множество различных подходов [7] к формированию случайной выборки: от использования таблиц случайных величин и физических датчиков случайных чисел до выполняемых на компьютере детерминированных алгоритмов генерации псевдослучайных последовательностей.
На начальных этапах развития генерации случайных выборок те, кому были необходимы случайные числа (векторы), вынуждены были [7] бросать игральные кости, либо раскладывать карты. В 1927 г (L.H.C. Tippett) была опубликована таблица, содержащая более 40 000 чисел «взятых наудачу» из отчетов о переписи. В 1939 году были опубликованы таблицы, содержащие 100 000 случайных чисел (M.G. Kendall), в 1955 году содержащие уже миллион чисел (RAND Corporation). Для генерации этих таблиц применялись устройства, называемые механическими (физическими) датчиками случайных чисел.
Действительно, свойства последовательностей, генерируемых физическими датчиками случайных чисел очень близки свойствам «истинно» случайных последовательностей. Физические датчики случайных чисел могут быть основаны как на микроскопических (тепловой шум, фотоэлектрический эффект, квантовые эффекты) так и на макроскопических физических процессах/эффектах (вращение колеса рулетки, бросание игральных костей, и т д).
Тем не менее, физические датчики обладают следующими недостатками, значимыми для статистического моделирования:
1) физические датчики относительно медленны;
2) нередко распределение последовательности на выходе физического датчика значительно отличается от требуемого;
3) так как датчики представляют собой физические устройства, они могут утрачивать со временем свои свойства;
4) с использованием физических датчиков невозможно повторить численный эксперимент, не сохранив всю произведенную генератором последовательность в памяти вычислительной машины, что во многих практических задачах является невозможным в силу огромного числа используемых случайных чисел.
Попытки синтезировать метод, лишенный перечисленных недостатков, породили методологию генерации псевдослучайных последовательностей [7], то есть детерминированных (обычно рекурсивных) алгоритмов (функций), производящих на выходе последовательность чисел или точек {л'&bdquo-}, имитирующую последовательность реализаций случайной величины X.
История генераторов псевдослучайных чисел (ГСЧ) берет свое начало в 1946 году, когда Дж. Фон Нейман предложил метод средин квадратов [7].
В общем виде последовательность (л-,) на выходе генератора псевдослучайных чисел (точек) может быть представлена в виде: где —детерминированная функция, аргументами которой служат предыдущие порожденные псевдослучайные значения, значение функции интерпретируется как следующий элемент последовательности. При этом считается, что начальные элементы последовательности {х,}, необходимые для корректного однозначного вычисления значения функции Ч' известны.
Критика генераторов псевдослучайных чисел очевидна: генерируемые последовательности по построению не являются случайнымикаждое генерируемый элемент полностью определяется предыдущими элементами и параметрами генератора. Однако, в случае если априорная информация о методе генерирования последовательности чисел, или участка этой последовательности, неизвестна, но задана последовательность (или конечное множество) {.г,} чисел или векторов многомерного пространства, можно ли, используя лишь элементы этой последовательности, определить, является она (или ее участок, т. е. конечное множество) случайной или нет?
Правомерность и способы проверки гипотезы случайности заданного множества или последовательности, выбор «меры случайности», «критериев качества» являются предметом длительной дискуссии математиков и философов [7], [9].
Приведем лишь нескольких высказываний о мере случайности заданной последовательности чисел1.
Определение" 0.1. (Лехмер Д. Г., цитируется по [7]). «Случайная последовательность является смутным понятием, олицетворяющим идею последовательности, в которой каждый член является непредсказуемым для непосвященных и значения которой проходят определенное количество проверок, традиционных у статистиков и отчасти зависящих от пользователей, которым предложена последовательность».
Определение" 0.2. (Франклин Д. Н., цитируется по [7]) «Последовательность случайна, если она обладает любыми свойствами, присущими всем бесчисленным последовательностям независимых выборок. случайных величин».
Несмотря на неполноту и неточность данных высказываний, суть их очевидна: истинно случайная последовательность должна удовлетворять всем возможным критериям качества. Дальнейший анализ этого требования и попытки его формализации привели [10] к неутешительным выводам — такого объекта как истинно случайная последовательность не существует. Какова бы ни была последовательность {*"} и способ ее генерации, всегда можно построить критерий относительного которого данная последовательность не будет достаточно случайной. Всегда можно построить определенную меру (критерий), относительно которого используемая генерируемая последовательность будет «несостоятельна» [7]. Как следствие, несмотря на то, что генераторы псевдослучайных последовательностей могут использовать произвольные детерминированные алгоритмы, для любого генератора можно утверждать, что он не может быть с одинаковой эффективностью применен для всех практических задач.
В результате попытки конструктивного разрешения этой проблемы, были выработаны (эвристические) рекомендации к «оценке качества» псевдослучайных последовательностей [84], [106], [107].
1 Следует отметить, что приведенные ниже высказывания не должны рассматриваться как корректные, а уж, тем более, математически строгие определения понятия «случайной последовательности».
1. Алгоритм генерации псевдослучайной последовательности должен быть исследован теоретически с использованием различных аналитических (например, теоретико-вероятностных) критериев качества.
2. Гипотеза о соответствии свойств псевдослучайной последовательности требуемым, должна быть исследована численно с применением как можно более обширного набора тестов.
3. Если возможно, генератор, планируемый для использования в для решения определенной вычислительной задачи, должен быть использован для решения аналогичной задачи, правильное решение которой заранее известно (может быть вычислено аналитически)2.
Решение о «уровне качества» псевдослучайной последовательности (обычно по сравнению с другими ГСЧ) принимается на основании результатов, полученных с использованием всех трех описанных подходов.
Критерии качества, используемые как для теоретического исследования псевдослучайных последовательностей, так и лежащие в основе статистических (численных) тестов, различны. Дополнительными требованиями, предъявляемыми к генераторам, используемым в алгоритмах моделирования по методу Монте Карло, являются системо-технические критерии эффективности программной реализации алгоритма генерирования на ЭВМ.
Применяемые в настоящее время критерии могут быть классифицированы [9] по следующим признакам:
1. Структурные критерии. К данной группе относятся требования к длине периода псевдослучайной последовательности, требования к геометрической структуре множества многомерных векторов, составленных из последовательных значений на выходе генератора, и др. 2.
Заметим, что данный способ анализа очень редко реализуем на практике, так как если аналогичная задача может быть решена аналитически, достаточно высоки шансы, что аналитическое решение может быть получено и для реальной задачи [41].
2. Статистические (теоретико-вероятностные) критерии. К данной группе относятся критерии согласия «эмпирического» закона распределения множества на выходе ГСЧ теоретическому (наперед заданному) закону распределения в одномерном пространстве, а также согласия распределения множества многомерных векторов, составленных из последовательных значений на выходе генератора, и др.
3. Критерии теории сложности. К данной группе критериев относятся теоретико-информационные критерии, интерпретирующие случайность последовательности, как «непредсказуемость» последующих отчетов [87].
4. Системо-технические критерии. К данным критериям относятся показатели эффективности реализации генератора на ЭВМ: длина программной реализации алгоритма генерации, время выполнения, требуемый объем памяти, кросс-платформенная переносимость [85].
Рассмотрим, какие критерии различных групп используются при оценке качества псевдослучайных последовательностей для статистического моделирования3. Наибольшее практическое значение имеют генераторы псевдослучайных последовательностей равномерно распределенных в некотором «регулярном» множестве. Для одномерных генераторов таким регулярным множеством является (см. [41]) отрезок [0.1], для многомерных генераторов — гиперкуб [0,1]Л .
1. Длина периода.
Пусть генератором псведослучайных чисел порождается последовательность {*"}, /7 = 0,1,. Величина периода Т псевдослучайной последовательности, то есть наименьшее Т е N, такое что является важным параметром, характеризующим качество генератора. Для решения практических задач с использованием генераторов различных классов, рекомендуется использовать не более чем 4 т последовательных отсчетов на выходе последовательности. Отметим, что подобные рекомендации являются чисто.
3 Иные критерии предъявляются, например, к псевдослучайным последовательностям, используемым в криптографии. Для последних большое значение имеют теоретико-сложностные критерии. эвристическими [65], [66], [67], [68], [69], [70]. Определенные аналитические оценки характеристик распределения множества чисел/точек на выходе генераторов различных семейств, возможно получить только для ее участков, длина которых превосходит.
2. Соответствие распределения элементов последовательности на выходе генератора теоретическому.
Для генерируемой псевдослучайной последовательности должны быть получены аналитические гарантии соответствия (согласия) «эмпирического» распределения генерируемых отсчетов теоретическому. Па практике, таким теоретическим распределением часто является равномерное распределение в регулярной структуре.
В качестве критериев согласия используются критерий (критерий.
Пирсона), двусторонняя статистика Колмогорова-Смирнова, различные меры отклонения (экстремальное отклонения, «звездное» отклонение), статистика Андерсона-Дарлинга, Крамера-фон-Мизеса и другие.
Формальные определения критериев, используемых в работе, представлены в первой главе.
3. Исследование статистической независимости элементов псевдослучайной последовательности.
Анализ статистической независимости элементов псевдослучайной последовательности является важнейшим методом теоретического анализа. Разработаны критерии качества генераторов, которые позволяют делать надежные предсказания о поведении генерированных отсчетов в реальных вычислениях (тем не менее, реальность все же может отличаться от прогноза [84]),.
Наиболее распространенным методом исследования независимости элементов псевдослучайной последвоательности является исследование распределения многомерных векторов, составленных из последовательных отсчетов псевдослучайных последовательностей (так называемый критерий серий).
Пусть {*"} - последовательность равномерно распределенных в [0,1) отсчетов на выходе генератора псевдослучайных точек. Элементы данной последовательности должны представлять собой реализации последовательности независимых равномерно распределенных в единичном полуотрезке случайных величин {Хп}. Рассмотрим {хп} последовательность ¿-/-мерных векторов.
— Ч (,'7) = (-Ч,&bdquo- • -V мх/{п+пч). (0.3).
Если элементы последовательнсти {хп} являются статистически независимыми, последовательность (0.3) векторов {хп} должна быть равномерно распределена в <Лмерном кубе [0,1)1'.
Таким образом, исследование равномерности распределения последовательности (0.3) может быть интерпретировано как исследование статистической независимости элементов псевдослучайной последовательности у >
Совершенно ясно, что конечность величины (I не позволяет исследовать независимость всех возможных наборов случайных элементов псевдослучайной последовательности. В частности, не г никаких гарантий, что последовательность будет лишена корреляций между удаленными отсчетами, которые могут сказаться в задачах, использующих параллельные алгоритмы основанные на разбиении одномерной последовательности на блоки. [72], [73], [74], [75], [76], [77].
Исследование равномрности полно-периодических последовательностей {.х^}, л = 0,1,., Г-1 в отношении некоторых критериев качества в пространствах различной размерности <Л позволяют делать предположения о поведении участка одномерной последовательности в реальных задачах. Эвристические результаты в пользу такого вывода приведены, например в работах [78], [81], [66]. Теоретических результатов в данной области на данной момент не получено.
Для некоторых ГСЧ, например линейных конгруэнтных генераторов, [10], множество векторов — элементов последовательности — в пространствах различной размерности с1 порождают т.н. «решетчатую структуру» [71]. Т. е. существует такая дискретная решетка, А с К'', чго векторы последовательности {х^} являются узлами этой решетки (формальное определение решетки в ЕА дано в разделе 1.3). Очевидно, что наличие подобной решетчатой структурой является недостатком метода генерирования, однако, в случае если в рамках определенной схемы генератора, решетчатая структура неизбежна, возможно сравнение качества различных генераторов с использованием дополнительных критериев, учитывающих структуру решетки Л (например, с использованием т.н. спектрального критерия, [7], [88]).
В общем случае, к исследованию равномерности распределения элементов на участках многомерных последовательностей {х//5}, применяются критерии согласия аналогичные критериям, применяемым в одномерном случае, например двусторонняя статистика Колмогорова-Смирнова или критерий %2 Пирсона. [82], [77], [65]. Двусторонняя статистика Колмогорова-Смирнова известна под названием звездного отклонения [83], [9], [77] (см. раздел 1.5).
Следует также отметить, что при выполнении гипотезы о статистической независимости элементов последовательности, {х&bdquo-} равномерность распределения элементов последовательностей {х1} является лишь одним из следствий, хотя и достаточно сильным. Если возможно определить статистику У, распределение которой известно, когда элементы последовательности {хп} являются реализациями статистически независимых равномерно распределенных случайных величин, соответствие эмпирического распределения статистики У теоретическому может быть использовано для проверки гипотезы о равномерности и статистической независимости элементов последовательности {х&bdquo-}. Данный принцип положен в основу методов синтеза всех статистических тестов псевдослучайных последовательностей.
5. Вычислительная эффективность.
Принимая во внимание огромные количества случайных чисел/точек, используемых в современных численных экспериментах по методу Монте-Карло, эффективность генерации псевдослучайной последовательности выходит на первый план. Именно для генераторов ГСЧ, используемых при статистическом моделировании, вычислительная эффективность имеет большое значение. Для ГСЧ, применяемых в других задача, например в криптографии, данное требование является менее значимым.
Рассмотрим важнейшие классы генераторов псевдослучайных точек, разработанные на настоящий момент.
1. Линейный конгруэнтный генератор (linear congruent generator, впервые предложен в работе [10]). Элементы последовательности {.v"} на выходе данного генератора, удовлетворяют соотношениям.
Уп =аУп-1 +b (modM), х"=Ъ> (0−4) М где в (0.4), в качестве чисел уп берутся наименьшие неотрицательные вычеты соответствующих классов (modM).
Линейные конгруэнтные генераторы являются простейшими генераторами псевдослучайных чисел, основанными на рекуррентном соотношении первого порядка. Максимальный период линейного конгруэнтного генератора (если Ь = 0 и а'00) является (М-1). Для генераторов этого типа характерна решетчатая структура распределения векторов в многомерном пространстве.
В работах [7], [79], [80] представлены параметры лучших линейных конгруэнтных генераторов в терминах спектрального теста и звездного отклонения.
2. Множественный рекурсивный генератор.
Последовательность {хп} на выходе этого генератора, удовлетворяет соотношениям.
У"и = 2>Л+/ (modM), п = 1,2,. I х"=77> (0−5) м где величины k, aQ, av., ak{, М являются параметрами генератора, в (0.5) в качестве чисел уп берутся наименьшие неотрицательные вычеты соответствующих классов (modM), начальные значения генератора уй, ух,.ук^ предполагаются ненулевыми.
Данный генератор детально исследован в [9]. 3. Метод Фибоначчи с запаздываниями (lagged Fibonacci generator, [7], [9]). Последовательность {*"} на выходе данного генератора удовлетворяет соотношениям y" - У&bdquo—j Oy"-k (mod Af),.
0.6) где О — некоторая бинарная битовая операция, например сложение по модулю 2, величины j, ke N, М являются параметрами генератора, в (0.6) в качестве чисел уп берутся наименьшие неотрицательные вычеты соответствующих классов (modM), начальное состояние генератора Су0, Vp—>.Ишахо,*н) предполагается ненулевым.
4. Генератор Таусворта (регистр сдвига с линейной обратной связью, linear feedback shift register generator, Tausworthe generator, [14]).
Последовательность на выходе генератора, удовлетворяет соотношениям где величины т, а0, а, М, я, I являются параметрами генератора, в (0.7) в качестве чисел уп берутся наименьшие неотрицательные вычеты соответствующих классов {тоАМ), начальное состояние генератора .у,.,.>>&bdquo-, предполагаются ненулевыми.
5. Мерсениовский вихрь.
Данный генератор, разработанный Матсумото и Нишимурой, и описанный в [15], на настоящий момент является одним из лучших ГСЧ. Его формальное описание требует формулировки значительного числа предварительных утверждений. Данный метод представляет собой пример гибридных ГСЧ, комбинирующих различные подходы.
Особое место среди ГСЧ занимают криптографические генераторы псевдослучайных чисел, к которым предъявляются дополнительные требования качества. В частности, данные генераторы должны выдерживать различные типы криптоаналитических атак, даже если часть их начального состояния (и/или параметров) известна атакующему. т-1.
У"+к =Т*а1У"+1 (modM), /7 = 1,2,.
1=0 v-I.
0.7).
В частности, каждый криптографический ГСЧ должен удовлетворять теоретико-сложностному критерию «тест следующего бита», суть которого в том что если заданы к бит псевдослучайной последовательности, не должно существовать алгоритма с полиномиальной сложностью, способного определить (к +1) бит последовательности с вероятностью, превышающей ½. Эндрю Яо доказал [21], важные свойства данного теста криптографических ГСЧ. Кроме того, например, каждый криптографический генератор должен выдерживать тест «продолжения состояния генератора» (в случае если всё (или часть) состояния генератора известна, должно быть невозможно восстановить последовательность псевдослучайных чисел, предшествующих данному состоянию).
Следует отметить, что генераторы ГСЧ общего назначения не удовлетворяют требованиям, предъявляемым к КГСЧ.
Одним из самых известных КГСЧ, является генератор Blum-Blum-Shub, описанный в работе [20]. Последовательность, порождаемая генератором, удовлетворяет следующему рекуррентному соотношению =(*"-i)2 (modpg), где p, q достаточно большие целые простые числа, удовлетворяющие некоторым дополнительным условиям.
К числу недостатков большинства КГСЧ, включая Blum Blum Shub, следует отнести их высокую вычислительную сложность. В силу данного недостатка, КГСЧ не применяются в задачах статистического моделирования по методу Монте Карло, хотя свойства распределения чисел на выходе генератора являются «более сильными» по сравнению с большинством ГСЧ общего назначения. Далее в работе, криптографические генераторы случайных чисел рассматриваться не будут.
Описанные выше генераторы псевдослучайных последовательностей являются одномерными, однако существуют задачи (например, вычисление оценки значения многомерного определенного интеграла с использованием соотношения (0.2)) требующие генерации последовательности псевдослучайных векторов с многомерным равномерным распределением.
Теория генерации псевдослучайных последовательностей многомерных векторов (или точек) является относительно новым направлением, и к настоящему моменту разработано лишь несколько «естественно» многомерных генераторов:
1. Матричный метод генераг (гш (Нидеррайтер, [9]). Последовательность А:-мерных векторов {и,} на выходе генератора, удовлетворяет соотношениям:
Матрица, А е, простой модуль М являются параметрами генератора, начальное состояние г0 предполагается ненулевым.
2. Матричный инверсивный метод генерации.
Пусть для заданной размерности к>2, выбирается большое простое число р, и пусть К — конечное поле из д = рк элементов. Для у е, определим у = у~ если уф 0, и у-0, если у-0. Далее, определим последовательность /о,?',. элементов Г нелинейным рекуррентным соотношением первого порядка:
Если {Д, Д,., Д} — базис в Гч над и Тг обозначает след из ^ в ^ (см. раздел 1.1), то последовательность {г7я| равномерно распределенных векторов в 1к может быть определена соотношением:
Данный метод предложен в монографии Г. Нидеррайтера [9]. 3. Матрично-рекурсивный метод.
Последовательность к-мерных векторов {"") на выходе генератора удовлетворяет соотношениям.
2"+1=г"А (тос1М), Ае^ М гп+1 =оу&bdquo- +Ь, если п>0. йп=-{Тг{/317п).Тг (Д7″))е/ Р кгк м.
0.8).
Величина М, т, матрицы А^в^*' являются параметрами генератора, начальное состояние г0 предполагается ненулевым. Данный метод впервые предложен в монографии Г. Нидеррайтера [9].
К достоинствам «естественно» многомерных методов относится заложенное конструктивно качество многомерного распределения псевдослучайных векторов в пространстве размерности к.
К недостаткам этой группы можно отнести принципиальную невозможность эффективной параллельной реализациитак, например, в матрично-рекурсивном методе для генерации /-ой координаты следующего псевдослучайного вектора, в соотношении (0.8) необходимы значения всех к координат предыдущих т векторов. Для генераторов данной группы не исследованы свойства координатных компонент образующих многомерную последовательность.
Для вычислительно эффективной реализации алгоритмов, основанных на использовании последовательности многомерных псевдослучайных векторов, применяются параллельные методы генерации псевдослучайных последовательностей векторов. Монте Карло. Действительно, многие алгоритмы Монте Карло являются «естественно» параллельными [86], что обуславливает применение параллельных генераторов псевдослучаных последовательностей многомерных векторов.
Традиционным методом параллелизации, параллельного синтеза псевдослучайной последовательности, является, например, «повышение размерности» одной или нескольких одномерных псевдослучайной последовательностей одним из следующих методов [18]:
1. Метод кругового обхода.
Пусть {.хп} — последовательность на выходе одномерного генератора псевдослучайной последовательности, к — размерность многомерного вектора, количество процессоров параллельного алгоритма. Тогда элементы последовательности псевдослучайных векторов {гп}, генерируемых параллельным алгоритмом, определяются соотношением (Х"):*Хпк+1.).
Данный принцип увеличения размерности одномерной последовательности до размерности 3 проиллюстрирован на рис. ОЛ. Одномерная последовательность как бы «наматывается» по спирали на координатные компоненты многомерной последовательности.
Рис. 0.1 — Увеличение размерности одномерной последовательности методом кругового обхода. Горизонтальные линии обозначают координаты многомерного пространства.
2. Разбиения одномерной последовательности на блоки.
Пусть {*"} — последовательность на выходе одномерного генератора псевдослучайной последовательности, к — требуемая размерность многомерного вектора, количество процессоров параллельного алгоритма, тогда элементы последовательности псевдослучайных векторов {г,} удовлетворяют соотношению:
Здесь? — параметр параллельной схемы, длина блока последовательных значений одномерной последовательности, производимых на одном процессоре. Данный метод проиллюстрирован на рисунке 0.2.
Рис. 0.2- метод увеличения размерности псевдослучайной последовательности методом разбиения последовательности на блоки. Горизонтальные линии обозначают координаты многомерного пространства.
3. Использование нескольких различно инициализированных однотиных псевдослучайных последовательностей, использование нескольких независимых последовател ьностей.
Пусть к — количество процессоров параллельной схемы, требуемая размерность многомерной псевдослучайной последовательности векторов. Пусть далее {л£0)}(— различные псевдослучайные последовательности, полученные с использованием различных методов, или с использованием одного метода генерации, но инициализированные различными начальными состояниями.
Тогда элементы последовательности псевдослучайных векторов {гп} удовлетворяют соотношению:
Иллюстрация данного метода, представлена на рисунке 0.3.
Рис. 0.3 —Метод повышения размерности одномерной последовательности путем использования различных одномерных последовательной для различных процессоров параллельной схемы. Горизонтальные линии обозначают координаты многомерного пространства.
К числу достоинств методов параллелизации одномерных последовательностей можно отнести возможность эффективной параллельной реализации алгоритма генерации координатных компонент, и, как следствие, многомерной последовательности псевдослучайных векторов.
Однако многомерное распределение элементов псевдослучайных последовательностей векторов, полученных с использованием методов параллелизации, может иметь существенные недостатки. В качестве наглядного примера очевидно недостаточных случайных свойств многомерной последовательности приведем последовательность, полученную методом кругового обхода из последовательности Капс1и, [18]. На рис. 0.4 проиллюстрировано распределение векторов этой многомерной последовательности в единичном кубе.
Рис. 0.4 — Элементы трехмерной псевдослучайной последовательности, полученные путем кругового обхода из последовательности Randu.
Причиной возникновения подобных артефактов является статистическая зависимость между элементами одномерной последовательности на выходе базового генератора Randu псевдослучайных точек. Следует отметить, однако, что для некоторых генераторов, подобные артефакты не наблюдаются вплоть до очень высоких размерностей, например для Мерсенновского вихря (Mersenne twister, [15]) многомерное распределение удовлетворяет критериям эквираспределенности в пространствах размерности вплоть до 623.
В дополнение к общим требованиям, к генераторам многомерных псевдослучайных последовательностей предъявляются следующие специфические требования:
1. Схема генерации должна быть работоспособна для любого количества используемых процессоров — требуемой размерности псевдослучайных векторов.
2. Последовательности, генерируемые на каждом из процессоров (координатные последовательности), должны удовлетворять критериям качества, предъявляемым к одномерным псевдослучайным последовательностям.
3. Распределение элементов многомерной последовательности векторов должно быть равномерным, координатные последовательности, должны быть статистически независимы между собой.
4. Алгоритм генерации должен быть вычислительно эффективен.4.
Следует отметить, что как существующие методы генерации «естественно» многомерных последовательностей пседвдослучайных векторов, так и методы параллельной генерации псевдослучайной последовательности имеют определенные достоинства и недостатки, перечисленные в Таблице 0.1.
Таблица 0.1 -Достоинства и недостатски «естественно» многомерных. методов и методов увеличения размерности одномерной последовательности.
Метод Достоинства/ недостатки «Естественно» многомерные методы Увеличение размерности (параллелнзация) одномерных последовательностей.
Достоинства Конструктивно заложенные хорошие свойства многомерного распределения Конструктивно заложенные параллельные свойства генератора.
Недостатки Данные методы не подходят для параллельных вычислений. вследствие невыполнения требования к локальности обрабатываемых данных Качество многомерного распределения требует подбора параметров схемы увеличения размерности параметров используемых одномерных ге нерато ро в. до пол н ительных исследований.
Представляется возможным построение метода, комбинирующего положительные свойства обеих групп, но при этом лишенного описанных недостатков. В качестве базы построения такого метода была использована следующая основная идея.
Основная идея. Последовательность на выходе одномерных генераторов псевдослучайных последовательностей. используемых для численного моделирования, состоит из действительных чисел полуотрезка [0,1). Однако, принимая во внимание конечность разрядной сетки компьютера, на котором.
4 На практике это требование означает, что передача данных между процессорами, участвующими в вычислениях, должна отсутствовать. Будучи инициализированным, каждый процессор должен генерировать псевдослучайную последовательность независимо. реализован алгоритм генератора, можно считать, что генераторы производят рациональные числа множества Л: где л' — длина машинного слова, точность разрядной сетки компьютера.
Заметим, что.
Сагс1(К) = Г < оо;
В двоичной системе счисления каждый элемент Л решетки Л может быть представлен в виде г=О где элементы разложения аг, г = 0Л,—, л-1 образуют бинарный ¿—-мерный цифровой вектор а (Л). а = (ао, аг., а1,)е{0,1}', оге{0,1}, г = 0,1,., 5−1.
Таким образом, можно считать, что на выходе любого одномерного генератора псевдослучайных чисел порождается последовательность бинарных векторов а{х (п)) е {0,1}л размерности.
В тех случаях, когда элементы многомерного пространства могут быть ассоциированы с элементами некоторой многомерной алгебры, в которой существует представление элементов, аналогичное представлению чисел в позиционных системах счисления (т.е. в виде цифровых векторов), методы синтеза одномерных генераторов, как показано в диссертационной работе, могут быть экстраполированы на многомерный случай.
Система счисления как объект исследования интересует математиков уже в течение очень длительного периода. Помимо естественных «натуральных» оснований, уже в XII веке (Грюивальд) математики рассматривали системы счисления с такими «экзотическими» основаниями как '-2' (т.н. негабинарные системы счисления). Д. Кнут в своей монографии [7], со ссылкой на работу Питти (РМ), указывает на возможность представления любого комплексного числа с целочисленными компонентами (т.н. целого гауссова числа) в виде конечной суммы степеней основания с коэффициентами из множества {0,1}:
2 = а + 6/ = 5>Д-1±/У, г, ={0,1}, а, Ьег,.
7=0 с некоторым к = к (г), зависящим от г .
В 1975 г. Катай (I. К&а!) и Ковач (Коуасэ) в работе [16] доказали существование систем счисления вида (~В±1,{0.В2}), и представимость любого целого гауссова числа в виде конечной суммы: к г = а + Ы = ^г]{-В±1У, г, е [о.В2], а, Ь е Ъ, В е с некоторым к =, зависящим от г .
В работах [11], [12], [13], продолжающих развитие теории канонических систем счисления, Ковач вводит понятие канонических систем счисления (КСС) для Ъкхк и КАхА. Каждому элементу г е в КСС ставится в соответствие вектор цифр:
В работах [11], [12], [13] показано, что для любого к> 2,-ичные {(?>.2, д е N) канонические системы счисления существуют.
Теория КСС дает возможность использовать идеи, реализованные в одномерных генераторах псевдослучайных чисел, для построения их многомерных аналогов. Используя сходство представления чисел в одномерных позиционных системах счисления и элементов многомерной решетки в канонических системах счисления, любой одномерный генератор может быть положен в основу соответствующего многомерного генератора псевдослучайной последовательности. Для этого достаточно лишь интерпретировать элементы состояние генератора как коэффициенты? в разложения (1.31) элементаеГ, 0.
Основная идея работы, послужила мотивацией для постановки указанной выше цели работы, определила задачи диссертационного исследования и структуру работы.
Задачи диссертационной работы:
1) теоретическое обоснование возможности синтеза генераторов псевдослучайных последовательностей векторов (КСС-генераторов) с использованием теории канонических систем счисления в решетках, синтез обобщенного генератора Таусворта.
2) исследование свойств множества точек на выходе КСС-генераторов, возможности унифицирующего преобразования данного множества к виду, удобному для практического использования в задачах моделирования по методу Монте Карло;
3) аналитическое исследование многомерного распределения на выходе предложенного обобщенного генератора Таусворта (на полном и неполном периоде) — исследование статистической независимости отсчетов генерируемой последовательности,.
4) исследование свойств координатных последовательностей на выходе генератора, анализ влияния параметров генератора и начальных условий на его свойства;
5) численное исследование свойств последовательностей на выходе генератора на участке периода, сравнение предложенного генератора с существующими схемами.
Краткое содержание диссертации. Диссертационная работа, содержащая 159 страниц, состоит из введения, пяти глав, заключения и списка использованной литературы, составляющего 107 наименований.
Заключение
.
В работе предложен метод синтеза многомерных генераторов псевдослучайных точек, обобщающих базовые одномерные ГСЧ с использованием теории канонических систем счисления в решетках. Исследовано множество точек многомерной решетки Ък, порождаемых Л’СС-генераторами. Найдены условия, при которых обобщенный ЖГОгеператор может быть эффективно применен для решения практических задач моделирования по методу Монте-Карло.
Синтезирована схема генератора ЬРБК-СЫБ, обобщающего одномерный генератор Таусворта. С использованием введенного понятия Л’СС-отклонения и разработанного аппарата канонических (/,/", к)-сетей проведено теоретическое исследование последовательности на участке, соответствующем полному и неполному периоду. Дополнительно проведено аналитическое исследование координатных последовательностей ЬРЗЯ-СМБ, зависимости характеристик генерируемого распределения от параметров и начальных условий генератора, проведено статистическое тестирование генератора ЬРЗЯ-СМЗ.
Синтезирован параллельный алгоритм генерации ХКЗД-СМ!?, проведено сравнительное исследование его интенсивности в терминах количества арифметических операций. Основные результаты диссертационной работы.
1. общий метод синтеза псевдослучайных последовательностей векторов многомерного пространства, основанный на использовании канонических систем счисления в многомерных решетках;
2. исследование свойств фундаментальных областей предложенных многомерных генераторов, синтез эффективных алгоритмов унификации;
3. аналитическое исследование многомерного распределения на выходе обобщенного генератора Таусворта на полном и неполном периоде, исследование статистической независимости отсчетов генерируемой многомерной последовательности;
4. исследование свойств координатных последовательностей на выходе обобщенного генератора Таусворта, исследование зависимости свойств генератора от его параметров и начальных условий.
