Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 68
Текст из файла (страница 68)
(Подобное обобщение применяется ко всем последовательностям длиной р — 1, удовлетворяющим линейным рекурреитным соотношениям 3.2.2-(8). Дополнительные числовые примеры приведены в работах А, СгиЬе, Яе!сж)гг!Хс Хйг апбеналс!се Мас!г. илс( Месйал|й 53 (1973), Т223-Т225:, Ь'Есиуег, В!ошп, апг! Сои!иге АСМ Тгалк Мос(ейля эпс( Сошр. 3!ши!. 3 (1993), 37-98.) 25. Рассматриваемая сумма меньше либо равна удвоенной сумме 2 < „г(с!л) 1+ -'/(т/с!), где /(т) = — ~ асио(яй/т) 1 |<э<» /3 г"'гз 1 1 сзс(ях/т) с(х+ О( — ) = — !исаи ( — х) ~ +О( — ). | (Когда |! = 1, справедлива равенство ) а < г(й) = (2/|г) !и из+1+(2/|г) !и(2е/я)+О(1/т).) 26.
Когда т = 1, использовать (52) нельзя, так как й будет равннться нулю. Если йсс)(9, т) = г( (бес! — наибольший общий делитель), то доказательство остается прежним, только т заменяетсн на т/И. Предположим, что справедливо равенство и| = р",'... р",", сг йсг!(а — 1, гл) = р,'... р„" н с! = р,'... р„', Если гл заменить на т/г(, то з заменяется на мзз(алг-гг-Эс| аз(Ое -г' -С ! р| ° ° ° Р 27. Удобно использовать следующие функции: р(х) = 1, если х = 0; р(х) = х, если 0 < х < т/2; р(х) = т — х, если т/2 < х < т! усечение(х) = (х/2), если 0 < х < т/2; усечение(х) = т — ((т — х)/2), если т/2 < х < т; Х(х) = О, если х = 0; Х(х) = (!3 х | + 1, если О < х < и|/2; Х(х) = — ((!3(т — х)) + 1), если гл/2 < х < т, н !(х) = псах(1,2' ').
Заметим, что !(5(х)) < р(х) < 2!(Х(х)) и 2р(х) < 1/|(х) = тнп(|гх/т) < |гр(х) лля 0 < х < т. Скажем, что вектор (и|,...,и|) плахой, если он не равен нулю и удовлетворяет (15). Пусть рмы — минимальное значение р(и|)... р(и,) по всем плохим (и|,..., и|). Вектор (и|,...,и|) относят к классу (Х(иг),...,Х(иг)). Поэтому существует не более (2!3п|+1)' классов и в классе (бг,...,Хч) содержится самое болыиее !(Хг)...!(Хг) векторов. Чтобы получить требуемое утверждение, достаточно доказать, что плохие векторы в эвждом фиксированном классе привносят самое большее 2/р,„м в сумму Х г(и|,..., иг); это позволяет получить желаемую грань, так как 1/р,м < я'г„„ Пусть р = (!3р,ь).
р-кратный ангра|вар рсечснил, применяемый к вектору, определяется следующей операцией, выполненной р раз| "Пусть / — такой минимальный индекс, что р(и„) > 1. Заменим и; на |гипс(и|), на начета яе будем делать, если р(и| ) = 1 для всех /". (Эта операция, по существу, отбрасывает один двоичный разряд информации от (и||...,и|).) Если (и',,..., и',) и (и",,... „и,") — два вектора из одного и того же класса, имеющие одна и то же р-кратное усечение, то мы говорим, что онн подобии; в этом случае справедливо неравенство р(и| — йг')...р(и', — и|') < 2" < р ь Например, любые два вектора вида ((1хзх|)з, О, т — (1хз)з, (101хзх|)з, (1101)з) подобны, когда т большое и р = 5; р-кратный оператор усечения последовательно удаляет х|, хз, хз, х|, хз. Так как разность двух плохих векторов удовлетворяет (15), невозможна, чтобы два неравных плохих вектора были подобными.
Поэтому класс (Х|,...,Хг) может содержать самое большее шах(1, !(Х г )... ((Х< ) /2" ) плохих векторов. Если в классе (Х з,..., Х | ) содержится точно один плохой вектор (и|,..., и|), то справедливы неравенства г(и|,..., и|) < г,„< 1/р,,м; если в яем содержится < !(Х |)... !(Х<)/2" плохих векторов, то для каждого из них выполняетсв г(и|,..., и,) < 1/р(и|)... р(и|) < 1/!(Х |)... !(Х<) и справедливо неравенство 1/2" < 2/р|сы 23. Пусть ь = ео" д и и пусть оо» = 2, ы*»+'~1~.
Аналогом (51) будет равенство ~3ьо( = ц/пь Значит, аналогом (53) является ! Ю ~~~ о»'" = 0((~/т!обт)/»Ч). о<«<н Теорема, аналогичная теореме Х, сейчас утверждает, что /--.(1 )н.1«, Р)П = О / об ) ~ + 0((!обт)'г ), Р~ 1, = О((1обт)'г,).
На самом деле Р~~1, < — о2»(им ..и,) (суммируем по всем не равным нулю решениям (15)) + — '1~ г(ип, „и,) (суммируем по всем не равным нулю (ип,.,,и»)1. Иэ упр. 25, если положить»1 ж 1, следует, что последняя сумма будет иметь порядок 0(1ой т)'. С полученной суммой поступим, как в упр. 27. Рассмотрим величину А(а) = 2 г(им...,и~), где суммирование выполняется по ненулевым решениям (15). Так как т — простое число, каждый (ип..., и») может быть решением (15) для самое большее 1 — 1 значений а. Следовательно, ) 'о«, Л(а) < (1 — 1) ~ г(иы, и~) = О(1(1об гл)').
Отсюда получаем, что среднее значение Я(а), взятое по всем 1»(т — 1) первообразным корням, равно 0(Ц!об т)»/Оо(т — 1)). Замечание. Справедхнво соотношение 1/1о(п) = 0(1о51обп/и), поэтому необходимо доказать, что для всех простмх чисел т и для всех Т существует первообрвзный корень а по модулю т, такой, что лннейнля конгруэнтнэл последовательность (1, а, О, т) имеет разброс Р„',~, = О(т 'Т(1обт) 1об!обт) для 1 <1 <Т.
Этот метод доказательства нельзя расширить, чтобы получить подобные результаты для линейного конгруэнтного генератора с периодом 2' по модулю 2', так как, например, вектор (1,-3,3, -1) будет решением (15) для приблизительно 2э'»о значений а. 29. Чтобы получить верхнюю границу, позволим ненулевым компонентам и = (щ,..., и~) быть любыми дейсп»ительньтн величинами 1 < )и ! < 1т.
Если й компонент не равны нущю, то г(и) < 1/(2"р(и)) в обозначениях ответа к упр. 27. И, если ио + + иэ равно данному значению «, минимизиртем р(и), взяв и1 — — = иь 1 = 1 и иь — — « — Й + 1. 2 2 э »р,<«1~2' 'Р:»+1.«»»а:» 1», » 30. Сначала минимизируем д)аа — тр( для 1 < а < т и О < р < а. В обозначениях упр. 4.5,3-42 справедливо равенство аа — тр = (-1)«К,- -1(а оо,...,а,) лдя О < и < о. В области д«1 < о < а«спрамдливо нерамнство (аа — тр( > (ад„-1 — гпр -1(; значит, О(ац — тр( > а»(ад«1 — тр«1) и минямум равен пппо<«<, д«!ад — тр ) = пппо«» К«(ам ..., а«) К»- -~(а»ьэ, ..., а») Из упр.
4.5.3-32 следует равенство т = К„(ам..., а„) а«.~1 К, «-1(а«оэ,...,а,) + К,(ам..., а«) К,- -о(а оо,, а,) + К«-~(ам..., а -~) К»-«-1(а«от, °, а»); н задача, по существу, состоит в нала~денни максимума величины т/К«(ам ..., а„) К» «1(а«оо, ..., а,), лежащей между а«.~1 и а»1+2. Пусть сейчас А = шах(ап.,.,а,), Так как г(т — и) = г(и), можно предпаэожичь, что г „„= г(и) г(аи шоб т) для неноторого и с 1 < и < 1т. Полагая и' = ппп(аи шод т, (-аи) пю»1 т), получим г, = г(и)г(и').
Из предыдущего раздела извести, что ии > 31, где А/т < 1/цд' < (А+ 2)/гл. Кроме того, 2и < г(и) ~ < хи для О < и < -'т, тогда г, < 1/(4ии'), Следовательно, г,„. < (А + 2)/(4т). (Существует поаобиэл нижняя грань, а именно — ги > А/(г т).) 31. Эквивалентное предположение состоит в том, что все большие т могут быть записаны в виде»п = К«(ам ., ., а„) для некоторого и и некоторых а, б (1, 2, 3) . Лая фиксированного и 3" чисел К„(ам,.,,а„) имеют среднее значение порядка (1 + ь/2)", и их стандартное отклонение имеет порядок (2.51527)"; так что предположение почти всюду верно.
С. К. Заремба (Б. К. Еагешйа) в 1972 году предположил, что все т могут иметь такое представлекие с а, < 5; Т. В. Кузик (Т, %. Семей) достиг определенного прогресса в решении этой задачи в работе Магйешаг!Ье 24 (1977), 166-172. Оказелось, что только в случаях, когда гп = 54 и гп = 150, требуются а; = 5, и самые большие т„для которых необходимо о; = 4,— это 20Ы, 2370, 5052 и 6234; по крайней мере, автор нашел представление с о, < 3 для всех других целых чисел, меньших 2 000 000. Чтобы выполнялось неравенство е, < 2, среднее К„(оп..., о„) должно быть равно 1 2" + -'( — 2) ", в то время как стандартное отклонение растет как (2.04033)". Оказалось, что плотность таких чисел в эксперименте автора (автор рассмотрел 2э блоков из 2ы чисел каждый для гп < 2го) изменялась между,50 и .65, [См. работу 1.
Вогоэй апб Н. Н!ебетге!зег, В1Т 26 (1980), 193-208, в которой рассматривается вычислительный метод нахождения множителей с малым частичным отношением. Авторы нашли представление с о; длв т = 2', где 25 < е < 35.[ 32. (а) П вЂ” У /тг ш (гпг — шз)1',/тгшг (по мцеулю 1) и (шз — тз)/тгшг ш 2™. (Поэтому можно анализировать самый старший двоичный разряд Я„, айализируя К,. Младшие разряды, вероятно, также случайны, ио эти соображения к ним не применяются,) (Ъ) Справедливо равенство (/„ж 1т'„/гп для всех и. Из китайской теоремы об остатках слегует, что достаточно только проверить соотношения И' гй Х„гпг (по модулю тз) и 1~1„ш -г'„тз (по молулю гиг), так как т1 Л гпз [Р!егге 1'Еспуег апб Бш Тезпйа, Мэгй.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
