Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 9
Текст из файла (страница 9)
Если Л вЂ” наимень- шее целое положительное число, для которого (а" — 1)/(а — Ц эз О (по модулю р'), то ( а ги 1 (по модулю р), Л = р' тогда и только тогда, когда 1~ а ьз 1 (по модулю 4), где р> 2, где р= 2. (а~ — 1)/(а - 1) ги О (по модулю 2'). Эти рассуждения показывают, что в большинстве случаев необходимо, чтобы а = 1+ дрг, где рг > 2 и д не кратны р, всякий раз, когда Л = р'. Докаэательстпво. Предположим, что Л = р'. Если а -„в 1 (по модулю р), то (а" — 1)Да — 1) ьз О (по модулю р') тогда и только тогда, когда а" — 1 ьз О (по модулю р'). Значит, условие аг'-1 аз О (по модулю р') влечет равенство аг' ьз 1 (по модулю р), но из теоремы 1.2.4г следует, что аг'.ш а (по модулю р). Таким образом, предположение, что а р! 1 (по модулю р), приводит к противоречию.
Если р = 2 и а = 3 (по модулю 4), то из упр. 3 следует Остается показать, что это условие достаточно для того, чтобы Л = р'. Применив лемму Р, находим, что лля всех д > О а" = 1 (по модулю р1+»), а" й) 1 (по модулю рай+э+1); следовательно, (а" — Ц/(а — 1) = О (по модулю рэ) (а" — 1)/(а — 1) ф О (по модулю р»+').
(6) В частности, (а»* — 1)/(а — 1) ьз О (по модула р'). Сейчас для конгруэнтной последовательности, определяемой параметрами (О,а,1,р') Л„, справедливо Х„= (а" — 1)/(а — 1) шос) р'. Значит, ее период равен Л, т. е. Х„= О тогда н только тогда,, когда п кратно Л. Следовательно, р' кратно Л. Это может случиться, только если Л = рэ для некоторых д и соотношения (6) означают, что Л = р'. $ Итак, теорема А доказана.
3 В завершение этого раздела рассмотрим специальный случай использования исключительно мультипликативных генераторов, когда с = О. Несмотря на то что процесс генерирования случайных чисел является немного более быстрым в данном случае, теорема А показывает, что максимальный период не может быть достигнут. Действительно, это совершенно очевидно, так как последовательность удовлетворяет соотношению Х».~1 = аХ» шоб т ал = 1 (по модулю р' У), (8) По теореме Эйлера (упр. 1.2.4-28) а~'<г 1 ьз 1 (по модулю р' 1); следовательно, Л является делителем Фр' г) = р' г '(р-1) и значение Х„= О может появиться, только если последовательность вырождается в нуль.
Вообще, если д — любой делитель т н если Х„кратно д, все последующие элементы мультипликативной последовательности Х»+ы Х„ з, ... будут кратны 4, Так что когда с = О, необходимо, чтобы Х„и т были взаиынб простыми числами для всех и, что и ограничивает длину периода максимум до ~р(т) — числа целых взаимно простых чисел с т, лежащих между О и т. Приемлемой длины периода можно достичь, даже если оговорить, что с = О. Давайте сейчас попытаемся найти такие условия, которым удовлетворяет множитель, чтобы в этом специальном случае период стал настолько длинным, насколько это возможно. Согласно лемме Ц период последовательности зависит исключительно от периодов последовательностей при т = р', Рассмотрим эту ситуацию. Итак, Х» ы а" Хо шод р' и ясно, что период будет иметь длину 1 (здесь можно только сказать, что длина периода не больше, чем с. — Прим.
род.), если а кратно р. Поэтому будем считать, что а и р взаимно простые. Тогда период будет наименьшим целым числом Л, таким, что Хв = а"Хв шод р', Если наибольшим общим делителем Хе и р' является ру, то это условие эквивалентно условию Когда а и т — взаимно простые числа, наименьшее число Л, для которого а" ьэ 1 (по молужо т), принято называть порядком а по модулю т. Любое такое значение а, которое имеет максимальный возможный порядок по модулю т, называют иервообраэкым элементом по модулю т. Обозначим через Л(гл) порядок первообразного элемент, а именно — максимальный возможный порядок по модулю пь Из замечаний следует, что Л(р') является делителем р' ~ (р-1); достаточно легко (см. упр.
11-16, приведенные ниже) можно определить значения Л(т) во всех сзедующнх случаях: Л(2) = 1, Л(4) = 2, Л(2') = 2' ', если е > 3; Л(р') = р' '(р — 1), если р > 2; (9) Л(р",... р,") = 1сш(Л(р",),..., Л(р,")). Все сказанное можно подытожить в следующей теореме. Теорема В. (С. Г. Оапээ, В1эчп1э1бопаэ Аг1гйте11сю (1601), 190-92.) Максимальным периодом, возможным, исида с = О, является Л(т), где Л(т) определено в (9). Этот период достигается, если: 1) Хэ и т — взаимно простые числа; й) а является первообразным элементом по модулю т.
$ Заметим, что можно получить период длиной т — 1, если т — простое число; т. е. это всего на единицу меньше, чем максимальная длина периода. Так что для практических целей такой период может быть настолько длинным, насколько это необходимо. Теперь возникает вопрос, как найти первообразные элементы по модулю т7 В упражнениях, данных в конце раздела, приводится совершенно очевидный ответ на вопрос, когда т является простым числом илн степенью простого числа.
Результаты сформулированы в следующей теореме. Теорема С. Число а является лервообразным элементом по мод, лю р' тогда я' только тогда, когда выполняется адно нз следующих условий: 1) р = 2, е = 1.на — нечетное число; й) р = 2, е = 2 я апю44 = 3; й() р = 2, е = 3 н а шоб 8 = 3, 5 ллл 7; 1т) р = 2, е > 4 н а шоб 8 = 3 илн 5," т) р - нечетное чпсло, е = 1, а ф О (по модулю р) и а~э 'хэ й': 1 (по модулю р) для любого простого делителя д числа р — 1; т1) р — нечетное число, е > 1, а удовлетворяют условию (т) я аэ ~ ~ 1 (по модулю рэ).
! Условия (т) и (т() теоремы легко проверяются на компьютере для больших р. Эффективные методы оценки степени, когда известны множители числа р — 1, обсуждаются в разделе 4.6.3. Теорема С применима только к степеням простых чисел. Но если заданы значения аэ, являющиеся первообразнымн элементами по модулю р,", то можно найти единственное значение а. такое, что а эв а1 (по модулю р" ) при 1 < 1 < 1, используя китайский алгоритм (алгоритм, построенный на основании китайской теоремы об остатках.
— Прим. нерее.), рассматриваемый в разделе 4.3.2. Число а будет перво- образным элементом по модулю р",... р,". Таким образом, существует приемлемый эффективный путь построения множителей, удовлетворяющих условию теоремы В, для любых модулей т умеренной размерности, хотя вычисления в общем случае могут быть весьма длинными. В распространенном случае, когда т = 2', где е > 4, изложенные выше условия приводят к единственному требованию: а хд 3 или 5 (по модулю 8). В этой ситуации четвертая часть всех возможных множителей даст длину периода, равну.ю гп/4, а т/4 булет максимальной длиной периода, когда с = 0.
Существует второй, еще более распространенный случай, когда т = 10', Используя леммы Р и (4, нетрудно получить необходимые и достаточные условия достижения максимального периода для десятичного компьютера (см. упр. 18). Теорема ху. Если т = 10', е > 5, с = 0 и Хо не кратно 2 или 5, то период линейной копгруэптпой последовательности равен 5 х 10' з тогда и только тогда, когда а шоб 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. $ УПРАЖНЕНИЯ 1. ]10) Чему равна длина периода линейной конгруэнтной последовательности с параметрами Хо = 5772156648, а = 3141592621, с = 2718281829 н т = 10000000000? 2. (10] Будут ли следующие два условия гарантировать максимальную длину периода, когда т является степенью 2? (!) с — нечетное число; (й) а той 4 .
1. 3. (1О] Предположим, что т = 10', где е > 2, и пусть с — нечетное число, не кратное 5. Покажите, что линейная конгруэнтная последовательность будет иметь период макси- 118ЛЬНОй длины илда и пивко тогда, когда ашо420 = 1 4. (МОО] Предположюо, что т = 2' и Хо = О. Если числа а и с удовлетворяют условиям теоремы А, чему равно Хы — ? 5. (!/] найдите все множители а.
удовлетворя(0щве условиям теоремы А, когда га = 2зо + 1. (Простые множители т можно найти в тоба. 3.2.1.1-1.) 6. [ОО] Найдите все множители а, удовлетворяющие условиям теоремы А, когда т = 10 — 1 (см. табл. 3.2.1.1-1). ° 7. (Лгяу] Период кангруэнтной последовательности не должен начинаться с Хо, но всегда можно найти индексы и > О и Л > О, такие, что Х„ох = Л„прн всех п > и, н для которых И и Л являются наименьшими возможными значениями с этими свойствами (см. упр, 3.1-6 н 3.2.1 — !), Если и, н Л1 — индексы, соответствующие последовательностям (Хо шод р„', а шоб и,', с шой р, ', и '), и если И и Л соответствуют составной последовательности (Хо, а, с, р",... р,"), то согласно формулировке леммы С) Л является наименьшим общим кратным Лп, Ль Чему равно значоино и в терминах значений 1оы..., И,? Чему равно максимально возможное значение И, получаемое путом варьирования Ло, а и с, когда т = и,"...
и," фиксировано? 8. (МОО) Покажите, чтоеслн ашо44 = 3, то (ао -1)/(а — 1) щ 0 (по модулю 2'), когда о > 1. (Воспользуйтесь леммой Р.) ° 9. [Мйй] (В. Э. Томсон (%. Е. ТЬошаоп).) Когда с ж 0 и гл = 2' > 16, теоремы В и С утверждают, что период имеет длииу 2' г тогда и только тогда., когда множитель а удовлетворяет равенствам а шоб б = 3 или а шоб8 = 5. Покажите, что кюкдая такая последовательность, по существу, является линейной коигруэнтиой последовательностью с гл = 2" г, имеющей палимо период, в следующем смысле: а) если Л„ег = (4с+ 1)Х„шод 2' и Х„= 4У„+ 1, то 1' м = ((4 + 1)У + с) щи 2' г; Ь) если Х~ч.г = (4с — 1)Л шо42' и Х„= (( — 1)" (4Уь + 1)) шо42', то 1'„ч.г = ((1 — 4с)1'„— с) шоб 2' [Замечакие.
В этих формгшах с есть нечеткое целое число. В литературе содержится достаточио утверждеиий о том, что последовательности с с = О, удовлетворяющие теореме В, так или иначе являются более случайиыми, чем последовательности, удовлетворякь щие условиям теоремы А, вопреки тому факту, что период — это только четверть длины периода, получаемого в условиях теоремы В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
