AOP_Tom2 (1021737), страница 176
Текст из файла (страница 176)
Последней будет точка 2г '(у,п(у),,а' '(у)), где о(у) = (-оу — (о/4)) шоб2' плюс постоянное отклонение. Снова применим алгоритм Б с т = 2' г; замена о на т — а не сказывается на резульгвте. 21. Хз эв = Хз (по модулю 4), поэтому сейчас удобно положить $г = (4,4аг,4аг)/т, Уг = (О., 1, 0), Уг = (0,0, 1) и определить соответствующую решетку /з. 24.
Пусть т = р': можно произвести анализ, подобный приведенному в разделе. Например, когда С = 4, то Х, +з = ((о -~- Ь)Хв+г -Ь аЬХ„) шоб т, и необходимо так минимизировать ог + иг + из + из Вв О, чтобы из + Ьиз+ абаз = из + ааз+ (о + Ь)ав щ 0 (по модулю т).
Заменим шаги Б1 — БЗ операцией присвоения (т О ) (1 0) В (1 0) г 1 2 и на выходе получим ггг = т. Заменим шаг Б4 шагом Б4'. Б4'. (Продвижение б) Если 1 = Т, алгоритм завершен. Иначе — присвоить 1 +- 1+ 1 и Е +- Н(, „) шодтп. Присвоим К новой строке ( — г~г, -гы,0,,0, 1) из Г элементов и присвоим иа з — 0 для 1 < г < б Присвоим 14 новой строке (0,...,0,т). для 1 < г < 1 присвоим д в- округление((апгш -ь амгы)/гл), оо в — оаггг-ьо,гггг — от и К г — К+ОК. Наконец, присвоить в в — пгш(з, К К), й +- г, 2 з- 1. (Подобное обобщение применяется ка всем последовательностям длиной р — 1, удовлетворяюгним линейным рекуррентным соотношениям 3.2.2 — (8).
Дапачнительные числовые примеры приведены в работах А. СгпЬе, Хе!Тэсбг!В Гбг апбекнл!11е Магб. пп!1 МесИаоий 53 (1973), Т223 — Т225;, Ь'Еспуег, В1ооап, апс( Сои!иге АСМ Тгэлэ. Мог)е!!лб лп!1 Сошр. Ящп!. 3 (1993), 8?-98.) 25. Рассматриваемая сумма меньше либо равна удвоенной аумме 2 г(!11с) 1+ „-/(па/И), где /(ш) = — ~ сэс(я1г/ш) 1 !<ьйм!Э ! !2 1 1 /! = — / сэс(хх/т)Их+О( — ) = — 1псап( — х) +О( — ) ! (Когда !1 = 1, справедливо равенство 2 „< г()г) = (2/я)!пт ! 1+(2/я)1п(2е/я)+0(1/т) ) 26. Когда т = 1, использовать (52) нельзя, так как к будет равняться нулю.
Если Оса(д, т) = Н (бс!1 — наибольший общий делитель), то доказательство остается прежним, только п! заменяется на ш/И. Предположим. что справедливо равенство гп = р",...р",", боб(о — 1,т) = р!'... р!" и е1 = р,'... р„". Если т заменить на пг/!Ь то э замеияагся на к! л а !е, «-Г» — И!) ааа1е,а — 1 — Л ) р! ..р 2Т. Удобна использовать следующие функции: р(х) = 1, если х = 0; р(х) = х, если 0 < х < т/2; р(х) = ш — х, если ш/2 < х < т, усечение(х) = (х/2), если 0 < х < ш/2; усечение(х) = т — Иш — х)/2), если гп/2 < х < ш; Ь(х) = О, если х = 0; Ь(х) = (18 х) -!- 1, если 0 < х < гл/2; Цх) = — ((18(ш — х)) + 1), если ш/2 < х < ш, и 1(х) = пзак(1,2'*' ').
Заметим, что 1(Цх)) < р(х) < 21(Ь(х)) и 2р(х) < 1/г(х) = тэ!п(пх/т) < гр(х) для 0 < х < т. Скажем, что вектор (и!,,и!) плохой, если он не равен нулю и удовлетворяет (15), Пусть рм!а — минимальное значение р(и!)...р(и!) по всем плохим (и|,...,и!). Вектор (иа,,о!) относят к классу (Цо!),, Ь(в!)). Поэтому существует не более (2 18 па+ 1)' клагсов и в классе (Ь|,..., Ь ) содержится самое большее 1(Ь!)...1(Ц) векторов. Чтобы получить требуемое утверждение, достаточно доказать, что плохие векторы в каждом фиксированном классе привносят самое большее 2/р „, в сумму 2, г(и!,..., и,); это позволяет получить желаемую грань, так как 1/рава < к'г,, Пусть д = (18р !„).
р-кропшмй оператор Вселения, применяемый к вектору, определяется следующей операцией, выполненной р раз: "Пусть у — такой минимальный индекс, что р(сц) > 1 Заменим и, на !гипс(и„), но ничего не будем делать, если р(и,) = 1 для всех /". (Эта операция, по существу, отбрасывает один двоичный разряд информации от (иа,..., и!).) Если (к'„..., о!) и (и",,..., и!') — два вектора из одного и того же класса, имея>щие одно и то же и-кратное усечение, то мы говорим, что они подобны: в этом случае справедливо неравенство р(и', — о!')...р(и', — о!') < 2" < рм! Например, любые два вектора вида ((1гэх!)м О, т — (1хз)э, (101хах!)ц (1101)э) подобны, когда ш большое и р = 5; р-кратный оператор усечения последовательно удаляет ха, хэ, хз.
ха, гэ. Так как разность двух плохих векторов удовлетворяет (15), невозможно, чтобы два неравных плохих вектора были подобными. Поэтому класс (Ь,...,Ь!) может содержать самое большее шах(1, ЦЬ!)... 1(Ь!)/2") плохих векторов. Если в классе (Ь!,..., Ь!) содержится точно один плохой вектор (и!,..., и!), то справедливы неравенства г(и!,.... и!) < г „< 1/р;„; если в нем содержится < 1(Ь!)... 1(Ь!)/2" плохих векторов, то для каждого из них выполияетси г(иг,..., и!) < 1/р(в!)... р(и!) < 1/1(Ь!)...1(Ь!) и справедливо неравенство 1/2а < 2/р 28. Пусть ( = ез П1м П и пусть Зег = 2,о<< г го*гегбг~. Аналогом (51) будет равенство ]Ого) = чгт.
Значит, аналогом (53) является Аг ~ ог*" = 0((г/т 1об т)/Аг). о«н Теорема, аналогичная теореме М, сейчас утверждает, что / 1 г-г-1 '~ Рл91 = 0 ) + О((1обт)'г, ), Р О, = 0((1обгп) ггее ). На самом деле Р, < =, 2 г(иг,...,иг) [суммируем по всем не равным нулю гг) -о решениям (15)] +,— „', 2„г(иг,..., иг) [суммируем по всем не равным нулю (иг,..., иг)]. Из упр. 25, если положить 4 = 1, следует, что последняя сумма будет иметь порядок 0(1об т)'. С полученной суммой поступим, как в упр.
27. Рассмотрим величину Я(а) = 2,'г(иг,...,иг), где суммирование выполняется по ненулевым решениям (15). Так как гп — простое число, каждый (иг,..., иг) может быть решением (15) для самое большее 1 — 1 значений а. Следовательно, 4 о«,„,)г(а) < (1 — 1) х, г(иг,..., иг) = О(1(!об гп)'). Отсюда получаем, что среднее значение )д(а), взятое по всем Ог(т — 1) первообразным корням, равно 0(1(!об т)г/р(гп — 1)). Замечание. Справедливо соотношение 1/дг(п) = 0(1о3!ойп/и), поэтому необходимо доказать, что для всех простых чисел т н для всех Т существует переообразный корень а по модулю т, такой, что линейная конгруэнтнел последовательность (1, а, О, т) имеет разброс Р~'~ г = 0(т 'Т(1обт) !о31обт) для 1 < 1 < Т. Этот метод доказательства нельзя расширить, чтобы получить подобные результаты для линейного конгруэнтного генератора с периодом 2' по модулю 2', так как, например, вектор (1, — 3,3, — 1) будет решением (15) для приблизительно 2ыг~ значений а.
29. Чтобы получить верхнюю гранину, позволим ненулевым компонентам и = (иг,..., иг) быть любыми действительными величинами 1 < [иг[ < -'т. Если о' компонент не равны нулю, то г(и) < 1/(2~р(и)) в обозначениях ответа к упр. 27. И, если и1 + . + игз равно данному значению и, минимизируем р(и), взяв иг = = ие г = 1 и иог — — н — Й+ 1. г о з г бг, гг ггг" Р-Т+2.0 2 гТт г, . г 2. ЗО.
Сначала минимизируем д]ад — тр[ для 1 < д < т и О < р < а. В обозначениях упр 4.5.3-42 справедливо равенство ад — тре = (-1)"К, „г(а ео,..., а,) для О < и < з. В области д„г < д < д„справедливо неравенство )ад — гпр) > )ад~ г — тр г); значит, д)ад — тр] > д -г(од„г — тре г) и минимум равен пппо«, д„]ад — тр ] = гашо«* К (аг,, а ) Кг-„-г(ае+гг ... г а,).
Иэ упр. 4.5.3 — 32 следует равенство т = К„(аг,..., а ) а тг Кг- г(авез,,аг) + К„(аг, ..., а ) К. „з(а +з,, а,) + К -г(аг,..., а г) К, „г(а„ео, ..., а,); и задача, по существу, состоит в нахождении максимума величины т/К„(аг, ..., а„) К, „г(а„+з, ..., а,), лежащей между а„ег и а„+,+2. Пусть сейчас А = шах(аг,...,а,). Так как г(т — и) = г(и), можно предположить, что г „„= г(и)г(аи шог1 т) для некоторого и с 1 < и < г го.
Полагая и~ = ппп(аи шод т, ( — аи) шог(т), получим г, = г(и)г(и~). Из предыдущего раздела известно, что ии' > дд~, где А/т < 1/дд' < (А+ 2)/т. Кроме того, 2и < г(и) ' < ки для О < и < -'гп, тогда г,„< 1/(4иг/), Следовательно, г„,, < (А + 2)/(4т). (Существует подобная нижняя грань, а именно -- г,„, > А/(кзт) ) 31.
Эквивалентное предположение состоит в том, что все большие т могут быть записаны в виде гп = К„(аг,..., а„) для некоторого и и некоторых а, б (1, 2, 3) Для фиксированного и 3" чисел К„(аг,...,о.„) имеют среднее значение порядка (1 + чГ2)", и их стандартное отклонение имеет порядок (2.51527)"; так что предположение почти всюду верно. С. К. Заремба (Я.
К. ЕэгешЬа) в 1972 году предположил, что все ш могут иметь такое представление с а, < 5., Т. В. Кузик (Т. 15г. Спв1сй) достиг определенного прогресса в решении этой задачи в работе Масйешабйа 24 (1977), 166 — 172. Оказалосьч что только в случаях, когда т = 54 и гп = 150, требуются а, = 5, и самые большие пгг, для которых необходимо а, = 4,— это 2052, 2370, 5052 и 6234; по крайней мере, автор нашел представление с о, < 3 для всех других целых чисел, меньших 2 000 000.
Чтобы выполнялось неравенство а; < 2, среднее Ка(ан..., а„) должно быть равно 1 2" + -'(-2) ", в то время как стандартное отклонение растет как (2.04033)". Оказалось, что плотность таких чисел в эксперименте автора (автор рассмотрел 2 блоков из 2'~ чисел каждый для пг < 2ге) изменялась между .50 и .65. (См. работу 1. ВогоэЬ апб Н. К(едессе(гег, В1Т 25 (1980), 193-208, в которой рассматривается вычислительный метод нахождения множителей с малым частичным отношением. Авторы нашли представление с а, для гп = 2', где 25 < е < 35.) 32. (а) Ь'„— Я /туг ш (гог — тг)У /тгтг (по молулю 1) и (по — шг)/тгт 2 (Поэтому можно анализировать самый старший двоичный разряд Е„, анализируя У .
Младшие разряды, вероятно, также случайны, но эти соображения к ним не применяются.) (Ь) Справедливо равенство П, = 14'„/т для всех и. Из китайской теоремы об остатках следует, что достаточно только проверить соотношении гг' ш Х тг (по модулю шг) и г('„ш — У„тг (по модулю тг), так как пг, .1. тг. (Ргегге Ь'Еспуег аш1 ЯЬп Тезвйа, МагЬ. Сошр. 57 (1991), 735 — 746.) РАЗДЕЛ 3.4.1 1. а+ ()3 — а)Г г. пус и = х/т, тогда (ЙЦ = г е=ь г < йх/т < г+1 4=Ф тг/й < х < т(г+ 1)/)г ег=ь (гпг//с) < Л < (гп(г+ 1)/Ц. Точная вероятность задается формулой (1/т)((ш(г+ 1)/Ц вЂ” (гпг/я)) = 1/Й + б где )е) < 1/гп.
3. Если заданы случайные числа, длина которых равна машинному слову, то результат будет отличаться от правильного распределения самое большее на 1/т, как показано в упр. 2, но все эксцессы приводят к наименьшим отличиям. Так, если и ш пг/3, результат будет меньше й/2 приблизительно в г раз. Намного лучше получить совершенно равномерное распределение, отбросив П, если (7 > я(пг/Ц [см. П. Е. КпвГЬ, ТЬе асан/огс( СгарЬВээе (Неэг Уотерс АСМ Ргеээ, 1994), 221]. С другой стороны, если использовалась линейная конгруэнтная последовательность, то Ь и модуль ш должны быть взаимно простыми числами, иначе числа имеют очень короткий период, как следует из раздела 3.2.1.1. Например, если й = 2 и т четное, наилучшими числами будут попеременно повторяемые числа 0 и 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
