AOP_Tom2 (1021737), страница 37
Текст из файла (страница 37)
Вееэ).) В разделе объясняется, как найти функции 7", такие, что последовательность (11) имеет длину периода т' — 1, если т — простое число и не все Хо,...,Хь ) равны нулю. Покажите, что такие функции могут быть изменены для получения последовательности наподобие (11) с длиной периода т" для всех целых т. [Указание. Рассмотрите лемму 3.2.1.2С), трюк иэ упр.
7 и последовательность вида (рХг + Хг +1).) ь 22. [М24) В разделе нет обширных обсуждений способов расширения линейной последовательности (8) до случая, когда т является простым числом. Докажите,что достаточно длинный период может быть получен, когда т "свободно от квадратов', т. е является произведением различных простых чисел (Из табл 3.2 1.1-1 ясно, что т = ш х 1 часто удовлетворяет этим предположениям. Многие из результатов, приведенных в настоящем разделе, могут поэтому быть распространены на случай, который в некоторой степени более удобен для вычислений ) ь 23. [20) Рассмотрите последовательность Л„ = (Х„ ы — Х„ г4)шоб т как альтернативу последовательности (7) 24.
[М20) Пусть 0 < 1 < А. Докажите, что последовательность двоичных разрядов, определенная рекуррентным соотновгением Х„= (Х„ечг + Х„г) шоб 2, имеет длину периода 2е — 1 всякий раз, когда такой же период имеет последовательность, определенная соотношением И, = (У'„г -~- У'„э) тогу 2. 25. '[211) Рассмотрите альтернативу для программы А, состоящую в том, по все 55 входов в таблице У-в заменяются 55 раз требуемыми случайными числами. 26 [М40] (Дж. Ф. Рейзер (,1. Г.
Ве)еег).) Пусть р — простое число и А — — положительное число. Пусть заданы целые числа аг,..., аг и хц..., хгз пусть Л вЂ” период последовательности (Х„), заданной рекуррентным соотношением Х = (агХ г + +аэХ„е) шог(р, и > Й, Х„= х, шоб р, 0 < и < /с, и пусть гУч равно числу нулей, которые встречаются в периоде (числу индексов г', таких, что ц < г < гз + Л и Х, = О). Докажите или опровергните следующее утверждение: существует константа с (зависящая, возможно, от р, х и ац.,.,ав), такая, что Аг < ср 1 гц г для всех и и всех хг,..., хь. [Замечание.
Рейзер доказал, что если рекуррентная последовательность имеет максимальную длину периода по модулю р (т. е. если Лг = р" — 1) и если утверждение имеет место, то й-мерное расхождение (л' ) будет равно 0(п"р 'г1" ю) при и -+ ж. таким образом, адаптивный генератор, подобный (7), был бы распределен в 5о измерениях, когда т = 2' и рассматривается полный период. (См. раздел 3.3.4, в котором определено понятие расхождения в й измерениях ) Утверждение является слабым условием, если (Х„) принимает каждое значение примерно одинаково часто н если Л = р" '(р — 1). Величина гУч ш (р — 1)/р не увеличивается, вообще говоря, когда и возрастает. Рейвер проверил это утверждение для А = 3.
С другой стороны, он показал, что можно найти необычайно плохие (зависящие от и) начальные значения хм..., хю такие, что № > р~, обеспечивающие Л = р~ '(р" — 1), й > 3, и достаточно большое.) 27. [М30) Предположим, что алгоритм В применяется к последовательности (Х„) с длиной периода Л, где Л » й. Покажите, что для фиксированного й и всех достаточно больших Л последовательность на выходе будет периодичной с той же самой длиной периода Л, если (Х„) ие является слишком случайной. [Указание.
Найдите структуру последовательных значений [АХ„/т), которая обеспечивает "синхронизацию" дальнейшего поведения алгоритма В.) 28. [40) (А. Дж. Вотермац (А. С. %асегшап).) Исгледуйте линейную конгруэнтпую последовательность с т, равным квадрату или кубу длины компьютерного слова, в то время как а и с заданы с обычной точностью. ь 29. [40) Найдите хороший метод вычисления функции /(хг,...,хг), определенной последовательностью Мартина (Магйп) в упр. 17, если задана только строка (хы..., хг) размерности я. 30. [МЯ7] (Р. П.
Брент (В. Р. Вгелс).) Пусть |(х) = хь — а!хо ' — — аь — первообразный полинам по модулю 2, и предположим, что Хо,..., Хь ! — целые чигла, не все четные. а) Докажите, что длина периода последовательности, заданной рекуррентным соотношением Х = (а~Х„ь + . + аьХ„») шод 2', равна 2' '(2ь — 1) для всех е > 1 тогда и только тогда, когда у'(х) + 1( — х) ж 21(х ) и 1(х) + У( — х) ~ 2( — 1)ьг»( — х ) (по модулю 8).
[Указание. Равенство хо" = — х (по модулям 4 и /(х)) справедливо тогда и только тогда, когда т(х) + у(-х) = 21(х~) (по модулю 8).] Ь) Докажите, что это условие всегда выполняется, когда полинам /(х) = х х х х 1 ь, » является первообразным полннолюм по модулю 2 н?» > 2. 31. [Мдд] (Дж. Марсалья (С.
Магьаб!1а).) Какова длина периода последовательности (7'), когда гл = 2' > 8? Предположите, что не все Ло,, Хь» — = х! (по модулю 8). 32. [Мд!] Каким рекуррентным соотношениям удовлетворяют элементы подпоследовательностей (Лз ) и (Хз ), когда Л„= (Х вЂ” »4+ Хо-ьь) шо»1 го» ь ЗЗ. [Мдд) (а) Пусть д (ь) = Х «ьо+Х ьшь+ +Х ь' +Х ьь»ьм «- .+Хчоь~э, где Х удовлетворяют рекуррен гному соотношению Фибоначчи с запаздыванием (7) Найдите простое соотношение между д (ь) и д„+»(х). (Ь) Выразите Хьоо в терминах Хо, ..., Хь«.
34. [М85] Докажите, что обратная рекуррентная последовательность (12) имеет период р+ 1 тогда и только тогда, когда полипом у(х) = х — сх — а обладает следующими двумя свойствами: (1) хгч' шо»1 у(х) равняется отличной от нуля константе, егли вычислять, используя полиномивльную арифметику по модулю р; (й) хм П?» шог! 7(х) имеет степень 1 для каждого простого д, делящего р+ 1.
[Указание. Рассмотрите степени матрицы (,, ) .] о ~ Зб. [НИХ] Как много пар (а, с) удовлетворяют условиям упр. 34? 38. [М85] Докажите, что обратная конгруэнтная последовательность Л ьь = (аХ,, '+с) шо»12', Хо = 1, е > 3, имеетпериоддлиной2' ' всякий раз, когдаашо»14 = 1 и сшей 4= 2.
ь 37. (НМЯЯ] Пусть р — простое число, и предположим, что Хэ ы = (аЛч' + с) п»пар определяет обратную конгруэнтную последовательность с периодом р + 1. К тому же пусть 0 < Ьь « бо < р. Рассмотрим множество 1 — ((Л ььмЛ чь»,,»,Л ьь»)[О<в <риЛ„«ь г.годля 1 <д <3] В нем содержится р+ 1 — Ы векторов; любые а' иэ них лежат в некоторой (»1 — 1)-мерной гиперплоскости Н = ((оы..., оь) ] гьо» + . + гьеа = го (по людулю р)), где (гп, гь) Ф (О,, 0). Докажите, что никакие Ы+ 1 векторов из 1: не лежат в одной и той же гиперплоскости, 3.4. ДРУГИЕ ВИДЫ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В предыдущих глздкллх мы обсуждали, как генерировать на компьютере последовательность чисел с7а, (7п 17з,..., которые ведут себя так, как если бы каждое число выбиралось независимо и случайно между О и 1 с равномерным распределением.
Однако при использовании случайных чисел часто требуются другие виды распределений. Например, чтобы сделать случайный выбор из к альтернатив, нужны случайные целые числа, лежащие между 1 и к. Если необходимо моделировать случайное время ожидания между появлениями независимых событий, желательно получить случайные числа с показательным распределением, Иногда в случайных числах нет необходимости, но нужны случайные перестановки (случайное размещение и объектов) или случайное сочетание (случайный выбор к объектов из совокупности, содержащей и объектов).
В принципе, любая из этих случайных величин может быть получена из равномеРно РаспРеделенных слУчайных величин На, Г7м сгз, .... Значительное число "случайных трюков" было придумано для эффективного преобразования равномерно распределенных случайных чисел. Изучив эти методы, получим возможность правильно использовать случайные числа при любом применении метода Моите- Карла. Вероятно, что кто-нибудь когда-нибудь придумает генератор случайных чисел, который будет вырабатывать одну из этих случайных величин иепосредстпвенна, а не косвенно через равномерное распределение. Но прямые методы, как доказано, не практичны, за исключением генератора "случайный двоичный разряд", описанного в разделе 3.2.2. (См.
также упр. 3.4.1-31; в нем равномерное распределение используется, главным образом, для инициализации, после которой метод является почти полностью прямым.) В следующем разделе предполагается наличие случайной последовательности равномерно распределенных между О и 1 независимых действительных чисел. Равномерно распределенная случайная величина П генерируется всякий раз, когда в ней возникает необходимость. Эти числа обычно представлены в компьютере словом с десятичной точкой слева. 3.4.1. Численные распределения В этом разделе объединены наиболее известные методы получения случайных чисел для различных важных распределений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
