Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 14
Текст из файла (страница 14)
Перемешнвайне имеет еще одно сравнительное неудобство, заключающееся в том, что оно не позволяет стартовать с заданного места в периоде либо быстро перемещаться из Х„в Х„+ь при больших А. Многие поэтому советуют объединять последовательности (Х„) и (У„) более простым способом, лишенным дефектов перемешивания. Например, можно использовать объединение инда г„= (Х вЂ” 1'„) шод гп, (15) где 0 < Л„< щ и 0 < У„< гп' < гп. В упр.
13 и 14 обсуждается длина периода таких последовательностей; в упр. 3.3.2-23 показано, что (15) имеет тенденцию к увеличению случайности, если начальные значения Хе и )'о выбираются независимо. Простой метод устранения структурных смещений арифметически генерируемых чисел был предложен на заре программировании Дж, Тоддом (3. То~Ы) н О. Таусски Тодд (О. Тацзз)гу ТогЫ) [Яушр. оп ЛХоп1е СаЛо Мейосв (ЪЪ !!еу, 1956), 15-28). Мы можем просто выбросить несколько чисел последовательности.
Их предложение мало использовалось в линейных конгрузнтных генераторах, но оно стало использоваться сейчас в связи с появлением генераторов, подобных (7), имеющих очень длинный период, потому что есть сколько угодно чисел, которые можно отбросить. Простейшим путем улучшения случайности (7) является использование только каждого 1-го элемента для некоторОго малого З. Но лучшим способом, возможно, еще более простым, является применение (7) для получения, скажем, массива из 500 случайных чисел и использование только первых 55 чисел, После этого таким же методом генерируются следующие 500 чисел.
Эта идея была предложена Мартином Люшером (Магйп ЬйэсЬег) (Сотригег РЬуа1сэ Сошшишса1юпя 79 (1994), 100-110). Толчком послужила теория хаоса в динамических системах. Можно рассматривать (7) как процесс преобразования 55 значений (Х„оо,..., Х„1) в друтой вектор из 55 значений (Хк+~ оо,...,Х„~~ 1). Предположим, что генерируется Г > 55 значений, а используются первые 55. Тогда, если г = 5о, новый вектор значений в некоторой степени близок старому; но, если г 500, старый и новый векторы всегда не коррелируют между собой (см. упр.
33). Для аналогичного случая генераторов суммирования с переносом или вычитания с заимствованием (упр, 3.2.1.1-14), как известно, векторы будут представлениями чисел в Ь.ичной системе счисления в линейном конгруэнтном генераторе, а подходящим множителем, когда генерируется сразу Г чисел, будет Ь '. Теория Люшера в этом случае, следовательно, может быть подтверждена спектральным критерием из раздела 3.3.4.
Портативный генератор случайных чисел, основанный на последовательности Фибоначчи с запаздыванием, усиленный методом Люшера, рассматривается в разделе 3.6, в котором приведены и комментарии. Генераторы случайных чисел, как правило, выполняют лишь незначительное число умножений и/или суммирований при переходе от одного члена последовательности к другому. Когда такие генераторы комбинируются, как рассказывалось выше, здравый смысл говорит нам, что полученная последовательность не должна отличаться от настоящей случайной последовательности.
Однако интуиция не может заменить строгое математическое доказательство. Если поработать дольше (скажем, 1 ООО или 1 000 000 часов), можно получить последовательности, для которых, по существу, имеются лучшие теоретические гарантии случайности. Например, рассмотрим последовательность двоичйых разрядов Вы Во,..., генерируемую соотношением Х„+1 — — Х„' п1од ЛХ, В„= Х„пюд 2 (16) (см. работу В! иш, В!и|п, апд БЬиЬ, ЯСОМР 15 (1986), 364-383), или более сложную последовательность, генерируемую соотношением Х„+, —— Л а шод Л7, В„= Х„Я пюд 2, (17) где скалярное произведение г разрядных двоичных чисел (х„ь ..
хо)о и (хг-1 ° оо)о равно х„, э,, +... + хоэо. Здесь Я вЂ” г-разрядная "маска", а т — число двоичных разрядов в ЛХ. Модуль ЛУ может быть произведением двух больших простых чисел ваша 49+3, а начальное значение Хо — взаимно простым числом с Ы Правило (17), предложенное Леонидом Левиным, является обобщением метода средин квадратов фон Неймана; мы будем называть его смешанно-квадратичным мещадам, потому что он перемешивает квадраты двоичных разрядов. Правило (16), конечно, является частным случаем для Я = 1.
В разделе 3.5Г содержится доказательство того, что, когда Хо, У и М выбраны наудачу, последовательность, сгенерированная соотношениями (16) и (17), удовлетворяет всем статистическим критериям случайности:, на генерирование такой последовательности требуется усилий не болыпе, чем на умножение больших чисел. Другими словами, двоичные разряды неотличимы от действительно случайных чисел для любых вычислений, длящихся менее ста лет, на современных быстродействующих компьютерах, когда Л1 достаточно велико. Если это не так, то можно найти множители нетривиальных частей таких чисел намного быстрм, чем известно сейчас. Формула (16) проще, чем (17), но модуль М в (16) должен быть несколько больше, чем в (17), есаи необходимо получить те же статистические гарантии. УПРАЖНЕНИЯ 1. Щ На практике случайные числа формируются с помощью Х„~~ = (аЛ, +с) шоб т, где ˄— Чалме числа, которые впосчгдствин рассматриваются как дроби П = Хп/пь Рекуррентное соотношение для (/„на самом деле имеет вид К,+1 = (аУ„+с/ш) шоп1, Объясните, как генерируется случайная последовательность с помощью этого соотношения, непосредственно используя арифметику с плавающей точкой компьютера.
° 2. [М80) В хорошем источнике случайных чисел неравенства Л 1 с Х +1 < Л, будут встречаться примерно один раз из шести, звк как каждое нз шести возможных отношений порядка Х„м Л и Л +1 должно иметь одну и ту же вероятность. Покажите, однако, что приведенный выше порядок нокогде не возникнет, если использовать последовательность Фибоначчи (5). 3. [80) (а) Какую последовательность генерирует алгоритм М, если Хе = О, Хк ы = (3Х„+3)шоб8, 1е =О, 1' ~~ =(31~+ Цшобб и й = 4? (Заметим, что потенциал равен двум, т. е. (Л,) н (У ) не настолько случайны, чтобы стоило их использовать.) (Ь) Что случится, если алгоритм В применить к этой же последовательности (Л" ) с А = 4» 4. [00) Почему наибольший значащий байт используется в первой строке программы (14) вместо других? б.
[80) Обсудите. стоит ли использовать Л = У„в алгоритме М для того, чтобы новы- сить скорость генерирования. Будет ли резуозьтат аналогичен результату, полученному с использованием алгоритма В? 6. [10] В бинарном методе (10) младший разряд Х случаен, если программа многократно повторяется. Почему все слоев Х не случайно? Т. [80[ Покажите, что можно получить полную последовательность длиной 2' (т. е, последовательность, в которой каждое из 2' возможных множеств е примыкающих разрядов встречается только адин раз за период), если программу (10) изменить следующим образом, ЬОА Х 1ЭА А ЗНОЗ э+3 ХО8 А ЗА83 э+2 АОО Х 1АХ э+2 3ТА Х 3 8. [М30) Докажите, что квадратичная конгруэнтная последовательность (3) имеет период длиной ш тогда и только тогда, когда выполняются следующие условия; 1) с я т — взаимно простые числа," й) Ы и а — 1 «ратны р для всех р — нечетных простых делителей и; ш) 8 четцо и ы щ о -1 (по модулю 4), если т кратно 4; Ыщ а — 1 (по модулю 2), если ш кратно 2; (ч) Ы И Зс (по модулю 9), если т кратно 9.
[Указание. Последовательность, определенная как Хе = О, Х„ч.1 —— 6Х„+ аХ + с, по модулю т имеет период длиной ш тогда и только тогда, когда этв же последовательность по модулю г имеет период длиной г, где г — делитель щ.) 9. [ЛЩ] (Р. Р. Копаю (К. К, Соэеуоп).) Используйте результаты упр.
8 для доказательства того, что длина периода модифвщированного метода средин квадратов (4) равна 2" г 10. [Мдд1 |Покажите, что если Ло и Л ~ — такие простые числа, что по крайней мере одно из них печатно, н т = 2', то период последовательности Фибоначчн (5) равен 3 2' 11. [Мдд) Назначение этого упражнения состоит в анализе определенных свойств последовательности целых чисел, удовлетворяющих рекуррентному соотношению Х„= а|Л„1+ .. +аэХ -ю и > Ь.
Если можно вычислить длину периода данной последовательности по модулю т = р', когда р — простое число, то длина периода этой последовательности по отношению к произвольному модулю т равна наименьшему общему кратному длин периодов последовательностей, для которых модуль равен степеням простых сомножителей гл. а) Если 1(х), а(а), Ь(х) — это полиномы с целымн коэффициентами, то запишем а(э) ш Ь(э) по модулям 1(е) и гл, если а(э) = Ь( ) + 1(э)и(э) + тв(х) для некоторых паанномов в(х) и э(е) с целыми коэффицие|пвмн. Докажите, что имеет место следующее утверждение, когда 1(О) = 1 и р' > 2: если з" ш 1 по модулям г(х) н р' и э~ ф 1 по модулям 1(э) и р"+', то ээ" ш 1 по модулям 1(х) н р"+' и гг" р 1 по модулям 1(э) н р'+з. Ъ) Пусть |(х) = 1 — аьэ — ..
— аэх" и С(х) = 1/у'(э) = Ао + А1х + Аах + Пусть Л(т) обозначает длину периода (А щос) т). Докажите, что Л(т) — нанмень. шее положительное Л, такое, что х~ щ 1 по модулям 1(а) и т. с) Дано: р — простое число, р' > 2 и Л(р') 14 Л(р'+ ). Докажите, что Л(р'+") = р'Л(р') для всех г > О. (Таким образом, чтобы найти длину периода последовательности (А що62'), можно подсчитывать Л(4), Л(8), Л(16)...., пока не будет найдено наименьшее е > 3, такое, что Л(2') ф Л(4). Тогда длина периода будет определена по шоб 2' для всех е.
В упр. 4.6.3-26 объясняется, клк вычислить Л„для больших и за 0()об и) операций.) 6) Покажите, что любая последовательность целых чисел, которая удовлетворяет рекуррентному соотношению, сформулированному в начале этого упражнения, имеет производящую функцию д(х)/Дэ) для некоторого полинома д(х) с целыми коэффициентами. е) Дано, что полиномы 1(э) н д(х) в и. (г)) взаимно просты по модулю р (см. раздел 4.6,1). Докажите, что последовательность (Х„гаобр') имеет ту же длину периода, что и специальная последовательность (А шог)р') в (Ь). (Нельзя увеличить длину периода путем выбора любых 'Хо,..., Хэ м так как общая последовательиость является линейной комбинацией "сдвигов" специальной последовательности.) [Указание. Из упр.
4 6 2-22 (лемма Хенселя) следует, что существуют полиномы, такие, что а(а) 7(х)+ Ь(х)д(х) ш 1 (по модулю р'),,' ь 12. [Мдд] Найдите целые числа Хо, Лм а, Ь и с, такие, что последовательность Л .~! =(аХ +ЬХ„1+с)що62', п>1, имеет самый длинный перед среди всех последовательностей этого типа. [Указание. Можно показать, что Х„+э = ((а+ 1)Х„+1+ (Ь вЂ” а)Л„- ЬХ„1) шой 2', см. упр, 11, (с)] 13. [Мдд) Пусть (Л„) н (1' ) — последовательности целых чисел по тоО т с периодамн длиной Л1 и Ль Объединим их, положив Е„= (Х„+ У,) шос1т.
Покажите, что если Л~ н Лэ — взаимно простые числа, то последовательность (Е ) имеет период длиной Л1 Лэ. 14. (МЯ4] Пусть Х„, 1'», Я», Л» и Л» определены так же, как в предыдущем упражнении. Предположим, что разложение Л| на простые множители имеет вид 2" 3" 5"... и аналогично Л» = 2т»3»»5»».... Пусть др = (шах(ер,/р), если е ,-» Ур, в других случаях — О) и пусть Ло = 2»»ЗР»5»».... Покажите, что длина периода Л' последовательности (Я ) кратна Ло и является делителем Л = 1сп»(Лп Л»). В частности, Л' = Л, если (ер Ф ур или ер — — »р = О) для каждого простого Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
