Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей, страница 5

Так, например, генераторы Фибоначчи с операцией «исключающееили» могут рассматриваться как частный случай обобщенных регистровсдвига. Ниже приводится краткий обзор основных методов генерации псев­дослучайных последовательностей в соответствии с введенной классифи­кацией, полная структура которой изображена на рис. 1.1.1.2.3. Л И Н Е Й Н Ы Й К О Н Г Р У Э Н Т Н Ы Й М Е Т О ДЛинейный конгруэнтный метод генерации псевдослучайных последо­вательностей был предложен Д. Лемером [45] в 1951 г. и впоследствии раз­вит У. Томсоном [75] в 1958 г. Этот метод является одним из наиболеестарых, но, несмотря на это, широко используется в современных системахи по сей день.

Такую популярность методу обеспечила эффективность ипростота его программной реализации. Кроме того, за время использова­ния линейных конгруэнтных генераторов был проведен глубокий и всесто­ронний математический анализ их свойств [12,30,34,37,39,43 и др.].Линейный конгруэнтный метод [6] основан на вычислении простогорекуррентного соотношенияat+i = (а • at + с) mod N,£ = 0,1,...,(1.1)в кольце Zyv для определения очередного члена псевдослучайной последо­вательности.

В этом выражении используется четыре параметра:- N — модуль, i V e N ;- а —множитель, а Е 2дг, а ф 0;- с —приращение, с Е Ъ^\- «о ~ начальное состояние генератора, а 0 £ %NВ случае, если приращение с = 0, то рекуррента (1.1) задает муль­типликативный конгруэнтный генератор, а в случае с Ф 0 — смешанныйконгруэнтный генератор. Следует отметить, что Д. Лемером изначальнобыл предложен именно мультипликативный вариант, а смешанный генера­тор был разработан в 1958 г. У. Томсоном.Модуль N, множитель о и приращение с определяют свойства генера­тора и обычно являются его фиксированными параметрами, а конкретнаяПростыеЛинейные кон­груэнтныеМультипликативныеСмешанныеНелинейныеконгруэнтные«Середина квадрата»Умножение с переносомКвадратичныеИнверсивныеФибоначчиКлассическиеАддитивныеМультипликативныеС операцией «исключающее или»ГенераторыпсевдослучайныхпоследовательностейСоставныеito1На основе реги­стров сдвигаЛинейных над конечным полемОбобщенныхОбобщенных с закручиваниемНелинейныхНа основе кле­точных автома­товКлассическихНеоднородныхРис.

1.1. Классификация основных генераторов псевдослучайных последовательностей-28выходная последовательность задается начальным значением а^.Поскольку выходная последовательность является псевдослучайной,ее члены связаны между собой. В случае линейной рекуррентной последо­вательности для любых чисел t € No, к € N эта взаимосвязь описываетсясоотношением{(at + кс) modN,а = 1;(akat + ^ с ) mod N,аф\.Кроме того, поскольку генератор является автономным конечным ав­томатом, его выходная последовательность является периодической. Мо­дуль' N определяет число внутренних состояний автомата, ограничивая ве­личину периода сверху.

Максимально возможный период выходной после­довательности смешанного конгруэнтного генератора (приращение с ф 0)равен Ттах = N и достигается в том и только том случае, когда выполня­ются три условия (см. [6,12]):1) модуль N и приращение с взаимно просты;2) число Ъ = а — 1 кратно р для любого простого р, являющегося дели­телем N;3) число Ъ кратно 4, если N кратно 4.Для мультипликативных конгруэнтных генераторов (с = 0) макси­мально возможный период составляетТ т а х = X(N), где X(N) — максималь­но возможный порядок элемента в мультипликативной группе Zjy.

Такойпериод достигается, когда выполнены следующие два условия:1) модуль N и начальное значение ао взаимно просты;2) множитель а является первообразным элементом по модулю N, то естьобразующим элементом мультипликативной группы Ъ*н.Особенности программной реализации линейных конгруэнтных гене­раторов обычно приводят к выбору одного из трех наиболее часто исполь­зуемых вариантов задания модуля:q1) N = 2 , где q+ 1 — число двоичных разрядов ЭВМ, на которой реали­зован генератор;2) JV = 1 0 ' , g > l ;3) A^GP, где Р —множество простых чисел,-29поэтому для них мы приведем частные результаты из [12].Если N — 2q, q ^ 4, то максимальное значение периода Ттах = 29~2 =j достигается, если оо > 1 —нечетное число и a(mod8) е {3,5}.Если с — О, N — 109, g ^ 5, и оо не кратно двум или пяти, то Ттах =5 • 1С 7 " 2 = ^ достигается тогда и только тогда, когда вычет a(mod 200)принимает одно из следующих 32 значений:3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61, 67, 69, 77, 83, 91, 109, 117, 123, 131, 133,139, 141, 147, 163, 171, 173, 179, 181, 187, 189, 197.Если с = 0, ао ф 0 и TV— простое число, то максимально возможноезначение периода Ттах = N — 1 достигается, если a(mod N) / 0 и a ^ —1 Ф 0(mod iV"), где Pj — простые числа в разложении числа iV— 1 на простыемножители.Для оценки статистических свойств выходных последовательностейлинейных конгруэнтных генераторов вводится понятие потенциала [6] —наименьшего целого числа z, удовлетворяющего условию(a-l)z= 0mo&N.Считается [6], что для обеспечения хороших статистических свойств ге­нератор должен обладать потенциалом 5 и более.

Тем не менее, высокийпотенциал является только необходимым, но не достаточным условием вы­работки качественной псевдослучайной последовательности.Основной статистический недостаток линейных конгруэнтных генера­торов был обнаружен и исследован Дж. Марсалья [47]. Если рассматри­вать последовательные члены a = 01,0:2,...

как координаты в d-мерномпространстве, то для линейных конгруэнтных генераторов распределениеточек вида(otdi+i,adi+2,• • •, 0£di+d),i = 0,1,...имеет решетчатую структуру: они располагаются на гиперплоскостях, при­чем количество гиперплоскостей, необходимых для размещения определен­ного числа точек, много меньше ожидаемого для истинно случайной после­довательности (см. рис. 1.2). Таким образом, выходная последовательностьлинейного конгруэнтного генератора значительно отличается по своим ста­тистическим свойствам от истинно случайной.-30-В двумерном пространстве+8о2 00040006 0008 00010 00012 000«2г+1В трехмерном пространстве10000со+со5 00010 000020004юоои12000аЗг+2Р и с . 1.2. Распределение точек, полученных при помощи линейного кон­груэнтного генератора at+i = (430oi£ 4- 2 531) mod 11979-31В заключение рассмотрения линейного конгруэнтного метода приве­дем обзор параметров некоторых наиболее распространенных мультипли­кативных генераторов (по материалам [39]).а = 23, N = 1Q8 + 1: такие значения были изначально предложены Лемером [45] в качестве параметров линейного конгруэнтного генератора и внастоящее время не используются в силу плохих статистических свойствполучаемых последовательностей.а = 65 539,' N — 2 3 1 : параметры алгоритма RANDU, использованногофирмой IBM в ранних моделях мейнфреймов System/360.

Использован­ные значения обусловлены, прежде всего, аппаратной архитектурой мейн­фреймов и соображениями производительности: множитель а может бытьпредставлен как а = 2 1 6 + 3, что позволило реализовать умножение a- atBвиде простых операций сдвига и сложения. Из-за «неправильного» выбо­ра параметров члены последовательности связаны простой рекуррентнойзависимостью at+2 = 6 • at+i — 9 • о;^, а при построении диаграммы рас­сеяния в трехмерном пространстве для размещения всех точек оказалосьдостаточно 15 плоскостей.а = 7 5 = 16807, N = 2 3 1 — 1: параметры алгоритма SURAND, исполь­зованного фирмой IBM в мейпфреймах System/360 для замены «дефект­ного» генератора RANDU.

SURAND уже не обладал столь явными недо­статками, как алгоритм RANDU, но, тем не менее, отставал от ряда другихгенераторов (например, MTHSRANDOM).32а = 69 069, N = 2 : значения параметров мультипликативного кон­груэнтного генератора, рекомендованные Дж. Марсалья [48] в 1972 г. Ге­нератор с такими параметрами и приращением с = 1 использовался в ка­честве генератора MTHSRANDOM для архитектуры VAX. Генератор об­ладал достаточно хорошими свойствами (неравномерность распределенияпроявлялась только в 6-мерном пространстве); кроме того, достоинствомгенератора является простота запоминания его параметров.1547а = 5 , п = 2 : параметры генератора, использованные Control DataCorporation в своих 60-битных мейнфреймах.

Выбор большого модуля поз­волил воспользоваться всеми преимуществами аппаратной 48-битной цело­13численной арифметики и обеспечивал большой (« 10 ) период выходной-32последовательности. Тем не менее, младшие биты ее членов использоватьне рекомендовалось из-за плохих статистических свойств.а — 1 664 525, п = 2 3 2 : генератор с таким выбором множителя а обла­дает одними из наилучших характеристик среди линейных конгруэнтныхгенераторов по модулю 2 3 2 , если проводить оценку при помощи предложен­ных Д.

Кнутом [6] критериев.1.2.4. Н Е Л И Н Е Й Н Ы Е К О Н Г Р У Э Н Т Н Ы Е М Е Т О Д ЫВ различное время предпринимались многочисленные попытки изме­нить структуру линейного конгруэнтного генератора и улучшить его свой­ства. Эти попытки привели к появлению различных нелинейных конгру­энтных методов, наибольшее распространение из которых получили следу­ющие:1) метод «середины квадрата»;2) метод умножения с переносом;3) квадратичный конгруэнтный метод;4) инверсивный (обратный) конгруэнтный метод.1.2.4.1. М Е Т О Д « С Е Р Е Д И Н Ы КВАДРАТА»Метод «середины квадрата» (см. [32]) был предложен Джоном фонНейманом в 1946 г. и является исторически первым алгоритмическим ме­тодом генерации равномерно распределенных псевдослучайных последова­тельностей.Идея метода заключается в возведении числа в квадрат и использо­вании в качестве выходного значения и следующего состояния генераторацифр из «середины» полученного значения.

Математически метод можетбыть описан следующим рекуррентным соотношением:at+12= (aSq299(mod 2 ) - a t (mod 2 ))/2 ,t = 0,1,...,(1.2)где q — параметр генератора. Начальное значение «о Ф 1 выбирается сре­2qди натуральных чисел, не превосходящих 2— 1 таким образом, чтобыа20 (mod 2?) ^ 0.Если проанализировать соотношение (1.2), становится видно, чтоак+\-33образовано 2q средними битами 4д-разрядного числа щ. Отсюда следуетосновной недостаток генератора: если на некотором шаге работы средниебиты а$ оказались равными нулю, все последующие члены выходной по­следовательности также будут нулевыми (т. е. генератор склонен к «сва­ливанию» в нулевое состояние); кроме того, короткие циклы могут об­разовываться и при ненулевых состояниях.