Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 27
Текст из файла (страница 27)
1.2.4-37, в котором было доказано, что — + — + у(с~у), у = боб(Ь, Ь), (5) 1 ЬЛ + с! (Ь вЂ” 1)(Ь вЂ” 1) у — 1 о<у<в для любых целых Ь и Ь, Ь > 0 (ба — каибольшкй общий делитель). Так как а и гп — взаимно простые числа, зта формула дает ~:Ю а<<« 0<е<т (а — 1)(гл — 1) 2 +с, (Ь вЂ” 1)(гл — Ц И вЂ” 1 2 + — + с — (с люб и') 2 и (3) следует немедленно. ! Доказательство теоремы Р указывает, что а«упорные критерии можно исследовать, если уметь удовлетворительно обращаться с суммами, содержащими функции ( ) и ( 1, Во многих случаях наиболее мощной техникой оперирования функциями "пол" и "потолок" является нх замена двумя отчасти более симметричными операциями: ((-х)) = -Их)); Кх+я)) = ((х)) для целого я; ((пх)) = ((х)) + (~х+ -)) + ° ° + ((х+ — )) для целого я > 1 е(х) = (х) + 1 — (х) ж [х-целое число(; (6) Их)) = х — (х) — $ + тб(х) = * - Гх1 + у' — ФУ(х) = х — НФ + (х() (7) Последняя функция — зто "пилообразная" функция, встречающаяся в теории рядов Фурье.
На рис. 7 приведен ее график, Причина того, что мы предпочитаем работать с функцией ((х)), а не с 1х) или (х1, состоит в том, что ((х)) обладает несколькими очень полезными свойствамн: Рис. 7. Пилообразная функпия ((х)), (см, упр. 2). Для приобретения практических навыков работы с этими функциями докажем теорему Р снова, на этот раз, не используя упр, 1.2.4-37. С поыощьв равенств (7)-(9) ИОжнО показать, что — — — +- — -3 х-е(х) х — (ах+с) 1 х в(х) 6х+ с 1 так как (х — э(х))/пт никогда не будет целым числом. Легко видеть, что ~" — =0, х- е(х) тв сбь<щ поскольку и х, и е(х) принимают значение из (0,1...пз — Ц точно один раз. Следовательно, (11) влечет Пусть 6 = 6сй, ж = тпео, где 6е н те — взаимно простые числа.
Нам известно, что (6сх) той тс принимает значения (О, 1, ..., тпе — Ц в некотором порядке, когда х изменяется от 0 до пес — 1. Из (9), (10) н равенства 6(х+тс)+с Ы+с (13) Теорема Р немедленно следует из (12) и (13). Одно нз следствий теоремы Р таково: практически при любам выборе а и с можно получить приемлемые вероятности того, что Х„+1 < Х„, по крайней мере прн полном периоде, за исключением болыпнх и. Большие значения т( соответствуют низкому потенциалу. (Уже известно, что генераторы с низким потенциалом нежелательны). Следующая теорема дает более точные условия выбора а и с. Рассмотрим критлернй сернальиой корреляции, применяемый на полном периоде.
Величина С, определенная в разделе 3.3.2 (формула (23)), равна с ( т *»» — ( с *) )/( 1 * — ( 1 *) ). ~1» Пусть х' — такой элемент, что в(х') = О. Тогда в(х) = щ(( — )) + — ]к ~я']. (15) Формулы, которые необходимо получить, лучше всего вьгразить с помощью суммы о(Ь,й,с) ж 12 ~ ~(-)) (( — )), (16) ойт<ь важной функции, возникающей в некоторых математических задачах. Ее называют обобщенной суммой Дедекиндв„так как Ричард Дедекинд (Вебейпт() ввел функцию н(Ь,».„О) в 1876 году, когда комментировал неоконченную рукопись Римана. (См.
работу В. Жетпапп, Севаттттпе(се тасл. Ятег)те, 2пб ес), (1892), 466-478.] Используя достаточно известные формулы с пт(т - 1) пт(тп — -') (тп — 1) х 2 и х .с 3 0<»<»т 0<»<т» можно легко преобразовать (14) в С— тпо(а, пт, с) -3+ 6(пт — х — с) тттт — 1 (17) (см. упр. 5). Так как т обычно очень большое, можно отбросить члены порядка 1/тп и получить приближенную формулу С о(а, тп, с)/щ (18) с погрешностью по абсолютной величине, меньшей, чем б/т, Критерий сериальной корреляции сейчас сводится к определению значения суммы Дедекинда о(а, пт, с). Вычислять о(а, пт, с) непосредственно из определения (16) не легче непосредственного вычисления коэффициента корреляции, но, к счастью, существуют простые методы быстрого подсчета сумм Дедекинда.
где е(Л,с) = [с=б]+ ]сыпет(тт~О], (26) Лемма В ('Закон еваимиостли длл сумм Дедехинда). Пусть тт, й и с — целые числа, Яслнб< с < Й, О < Ь < й и всат гтя тт — взютмно простые числа, то Ь (т 1 бст ! с ! о(тт, й, с) + о(й, й, с) = — + — + — + — — б ~ — ] — 3е(Ь, с)„ (19) й и йй Ы Доказащельсглва.
Оставляем читателю доказательство того, что при наших оредположеииях имеет место равенство без 1с! а(а,й,с)+а(й,й,с) =а(а,й,О)+и(й,а,О)+ — — 6~ — ~ — Зе(1~.,с)+3 (21) (см. упр. 6). Теперь докажем лемму только для с = О. Приведенное ниже доказательство, в котором используются комплексные корни из единицы, по существу, принадлежит .Ч. Карлицу (1.
Сагйсз). Это действительно более простое доказательство, чем доказательство с использованием элементарных преобразоваиий сумм (см. упр. 7), но для следующего метода необходимо больше математических понятий, чем требуется обычио для задач такого типа, поэтому он более поучителен. Пусть |(х) и д(х) -- полиномы, определеиные следующим образом: /(х) = 1 + х + " + х' ' = (хь — 1)/(х — 1), д(х) = х + йхз + --. + (й — Ц*"-' (22) = х/'(х) = йх'/(х — 1) — х(х' — 1)/(х — 1)'.
Если ы -- комплексный к-й корень из единицы е™~ь, то из формул 1.2.9-(13) получим — ы 1'д(ьг'х) =гх", если О <г < х. (23) о<1<о Положим х = 1, тогда д(ыух) = х/(ыт — 1), если,у ф О, иначе это выражеиие равно й(й — 1)/2. Поэтому -ь г шод й = ~~~ . + 1(й — 1), если г целое. с,д — 1 о<1<о (Равенство (23) показывает, что правая часть равна г, когда О < г < й, и она ие кзменяется при прибавлении к г числа, краткого )г,) Следовательно, ~(-)) = — ~~~ — — — + — б~- ), (24) о<~<о ~ Эта важная формула, которая справедлива для всех целых г, позволяет свести многие вычисления, включающие ((г/й)), к суммам, содержащим й-й корень единицы. Оиа предоставляет новые возможности для вычислений. В частности, получим следующую формулу, когда Ы й: 3(й — 1) 12 -и о,-ты (Ь,й,о)+, = —, ŠŠŠ—.1 —,1 (25) о<г<ь о<~<о о<1<о Правая ее часть может быть упрощеиа, если просуммировать ее по г.
Получим 2 о«,,ьы"' = /(ы') = О, если всвое й ~ О. Равенство (25) сведется к а(й, Й,О) + — =— 3(Й вЂ” 1) 12 1 (26) а й (ы-1" — 1)(ад — 1) ' о<г<о Апалогичная формула получена для а(Й, Ь, О) с «' = ез"'7» вместо ы. Не ясно, что делать с суммой (26), однако существует элегантный метод ее преобразования, основанный на том факте, что каждый член суммы является функцией от ьФ, где О < у < Й. Следовательно, суммы, в сущкости, берутся по Й-и корням из единицы, отличным от 1. Когда х~, хз, ..., х„— различные комплексные числа, получаем равенство 1 ~- (ху — х~)... (х1 — ху»)(х — х»)(х~ — х1+»)... (ху - х») (27) (х — х»)...
(х — х„) которое можно вывести в результате применения обычного метода разложения на элементарные дроби в правой части этого равенства. Кроме того, если д(х) = (х — Р~)(х — Рз)... (х — Р,„), спРавелливо Ч (РУ) = (Рт — Рз) ° ° (Ру РУ-»)(Рг Рт+1) ° ° ° (Рз Р )' (23) это тождество часто используется для упрощения выражений, подобных левой части (27). Когда Ь и Й вЂ” взаимно простые, все числа ы, »Р..... ы» ~, «, «з, ..., «" » различны. Поэтому можно рассмотреть формулу (27) в частном случае для полинома (х-и)...
(х-ы» ')(х-«)... (х-«" ') = (х" — 1)(х" — 1)/(х — 1)з, получив следующее тождество для зс «Ф(«1 1)з 1,Ф'( Ф Цз (х Цг («з» 1)( «з) Й с ( „л ц( „„) (.» 1)( .» ц Оно имеет много интересных следствий и позволяет получить многочисленные формулы для сумм наподобие (26). Например, если (29) дважды продифференцировать по х и устремить х -» 1, получится 2 «3ф Цз 2 1( Р 1)2 Ь л'.
у» ц(1 «1)з + Й ~~'. ( 1» 1)(1 „о)з 1И Й 1~ 6Ь Ь ЬЙ! 2 2Ь 2Й Заменим З' на Ь вЂ” 7' и на Й вЂ” у в этой сумме и используем (26), чтобы получить равенство - ~о(Й.Ь,О)+ ) + - ~т(Ь,Й,О)+ — ) 1 г' 3(Ь вЂ” 1)Ь 1 / З(Й вЂ” 1)~ 1~Ь Й 1~ 1 1 1 -+ -+ — + - — — —— 60 Ь ЬЙ/ 2 ЗЬ 2Й' эквивалентное желаемому результату. 3 Лемма В дает явно заданную функцию ДЬ, Й, с), такую, что п(Ь,Й,с) = ДЬ,Й,с) — о(Й,Ь,с), (ЗО) какими бы ни были взаимно простые числа Ь и Й, такие, что О < Ь < Й, О < с < Й. Из определения (16) следует, что п(Й,Ь,с) = о(Йпюб Ь, Ь, стой Ь), (31) Поэтому можно повторно использовать (ЗО) для оценки с(Ь, Ь, с) путем уменьшения параметров, как в алгоритме Евклида.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
