Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2), страница 3

Если построить график значений г„как функций 1пп по приведенным выше данным, то окажется, что эти значения расположены очень близко к прямой линии: (50) т„ж 0.8431пп+ 1.47. Это свойство будет учтено чуть позже, при исследовании процесса формирования правильной цепной дроби. Учитывая выражение (15), для алгоритма Евклида получаем 1э ~~ Ч~ ~ 14 г (уэ (/~ 6~-~ Уо поскольку (/э+~ = Ъ~,, Далее, если У = Уе и 1г = уэ взаимно просты и если имеется 1 шагов деления, то ХеХ~ ...Х~, = 1/Г (51) 1п Хе + 1ц Л ~ + ° ° + 1п Хг ~ -- — 1п Л~. Так как известно распределение величин Ле, Хм Хт, ..., это уравнение можно использовать для сщенки величины 1 = т(ж-. ) = Т(гп, Л/) - 1.

Возвращаясь к формулам, приведенным перед теоремой Ж, находим, что среднее значение величины 1п Л'„в случае, когда Хэ — вещественное число, равномерно распределенное в интервале [О .. 1), равно / 1 г~ 1пхУ„'(х)йх = / 1пх/„(х)Ия/(1+к), е е (52) где /„(я) определено в уравнении (33). Отсюда, рассуждая так же, как и ранее (см, упр. 23), получаем Ув(х) = + О(2 ). 1 1п2 (53) 95 96 97 98 99 100 101 5.4 5.3 5.3 5.6 5.2 5.2 5.4 996 997 998 999 1000 1001 7.2 7.3 7.3 7.3 7.3 7.4 49998 49999 50000 50001 10.59 10.58 10.57 10.59 Полагая У = Х и Ъ' = гп < Х, найдем, что 102 103 104 105 5.3 5.4 5,3 5.6 9999 10000 10001 9.21 9.21 9.22 99999 100000 100001 11.170 11.172 11.172 Следовательно, среднее значение величиньг 1п Л"„очень хорошо аппроксимируется вгличинОЙ 1 /' ие" — г(н !.2Л 1+И-" в — „'С (-1)"+' Гив "" ь~г 1 у 1 1 1 1 '1--+-- — + — -" ) )п21 4 9 16 25 17 1 1 у! 1 1 = — ~1+-+-+" -ф+ — + — + ")) 1п2~ 4 9 14 16 36 = -ит/(121п2).

Поэтому в силу (51) следует ожидать, что приближенная формула будет иметь вид -!Ит/(12!и 2) ю — !НЛг, т. е. Ф должно приближенно равняться величине ((12 !п2ДКТ) !и Лг. Эта константа (12 1П 2)/тэ = 0.642765913... полностью сотласуетгя с эмпирической формулой (50), пгпгученнОЙ ранее, так чгО есть Вескию ОснОВвния полВгать, чтО формула 12!п 2 т„м — 1пп+ 1.47 яэ ОПНСЫВВЕТ ИСТИННОЮ ПОВЕДЕНИЕ Тгг ПРИ и + ОО, Если предположить, что вьшолняется приближенное равенство (54), получим следующую формулу: Т„яг — ~1П п — ~~г — ~ + 1.47, 12 !и 2 / Л(И) 1 тде Л(г() — функция фои Мангольг)гпа, Определяемая правилами 1пр, если п = р", где р — простое число и т > 1; Л(п) = 0 в противном случае.

(См. упр. 27.) Например, 121п2 У !п2 !п2 1п5 !П5~ аггею — ~!и 100 — — — — — — — — / + 1.47 ят 1 2 4 5 25/ в (0.643) (4,605 — 0.347 — 0.173 — 0.322 — 0,064) + 1,47 гн 4.59; точное значение Тгюю Равно 4,56. Можно также оценить среднее количество шагов деления в случае, когда оба числа и и с равномерно распределены в интервале между 1 и Ю, вычислив (57) В предположении справедливости формулы (55) в упр. 29 показано, что эта сумма имеет вид — 1п Ж + О(1), 121п2 (58) а эмпирические расчеты, выполненные с теми же числами, которые использовались при выводе еютношения 4.5.2-(65), хорошо согласуются с формулой 12!и 2 — 1п Ю + О. 06. яз (59) т„= — !пи+С+О(п '), 12!и 2 -~,'в+ хт где С ш 1.4670780794 есть постоянная (60) 61п2 -э ~ — (3 !и 2 + 47 — 24х ~С(2) — 2) — —; ит (61) см. П.

Е. КпигЬ, Сошрпгетв ап6 МагЬ. вйЬ Аррйс. 2 (1976), 137-139. Таким образом, утверждение (50) полностью доказано. Используя формулу (60), Грэхэм Х. Нортон Конечно, пока мы ничего не доказали о поведенян Т„и г„в общем случае, До сих пор рассматривались только возможные обстоятельства, при которых дозжны быть верны определенные формулы. К счастью, сейчас уже можно применить методику строгого доказательства, которая основана на тщательном анализе, выполненном рядом математиков. Впервые главный член (12 1и 2)/хз в формулах, приведенных выше, был получен независимо Джоном Д.

Диксоном (3оЬп !1. В!хоп) и Гансом А, Хайльбронном (Напз Л. НеВЬгопп). Диксон (Х ХишЬег ТЬеогу 2 (1970), 414 — 422) развил теорию распределений Р„(х), чтобы показать, что индивидуальные частичные отношения являются в определенном смысле независимыми одно от другого, и доказал, что для любого положительного с выполняется соотношение !Т(т,п) — ((121п2)/тэ) 1пп) < (!в п)0~~>+', но не для значений т и и ехр(-с(с)(!ойдо)'~~)Ю в интервале 1 < т < и < й!, где с(с) > О.

Совсем иной подход к этой проблеме, при котором вместо непрерывных переменных рассматриваются только целые числа, предложил Хайльбронн. В основу его иден, излагаемой в несколько модифицированном виде в упр. 33 и 34, положен тот факт, что величину т„можно определенным образом связать с числом способов представления и. Кроме того, в его работе й!шпЬег ТЬеогу ап6 Апа!уя!е, е61сед Ьу Рап! Тигйп (Неп гогус Р!еппш, 1969), 87-96, показано, что распределение индивидуальных частичных отношений 1, 2, ..., которое рассматривалось выше, в действительности применимо ко всему множеству частичных отношений, принадлежащих дробям с заданным знаменателем, Это более точная форма теоремы Е.

Через несколько лет Дж, В. Портер (3. %. Роггег) [Ма!Ьегпагйв 22 (1975), 20-28! получил еще более точный результат. Он установил, что (сгаьаш н. хоггоп) [х Яугпьо)1с согпрпгаг(оп 10 (1990), 53-58[ продолжил вычисления упр. 29, чтобы доказать, что эмпирическая константа 0.06 в формуле (59) в действительности равна — (3 1и 2 + 4 у — 12я ~'(2) — 3) — 1 0.06535 14259.... (62) 61п2 Г. Э. Коллинз (6. Е. Сойше), применив классические алгоритмы выполнения арифметических операций, показал в 81СОМР 3 (1974), 1-10, что среднее время выполнения алгоритма Евклида при оперировании числами многократной точности равно [1 + 1ой(шах(н, е)/йод(и, и)) ) 1об ппп(и, е).

(63) Резюме. Мы обнаружили, что наихудший случай алгоритма Евклида имеет место, когда входные числа и и е связаны с числами Фибоначчи (теорема г), а число шагов деленна пРи 0 < е < /7 никогда не пРевышает величины [4.8 1обш )г' — 0.32~[. Мы определили частоту появления различных частичных отношений, показав, к примеру, что приблизительно в 417« случаев на шаге деления получается [и/е) = 1 (теорема Е). Наконец, в теоремах Хайльбронна и Портера доказывается„что среднее чишю Т„шагов деления при е = и приблизительно равно [(12[о 2)/т ) 1пп ж 1.94051ойшп, если не учитывать корректирующий член, основанный на делителях числа и, как следует из уравнения (55). БИХХ а гАХ «- гА.

Л. 2Р и — э<«2 В17 7 гХ «-гАХщобж 2Н ЬВХ 7 гА«-ж ЛХИХ 1В Вмпалнене, «сли гХ = О. ! ьВХ О гХ «- ж ЛИР 2Р 1И РТХ 7 е «- гХ ЯВВ 7 ГА «- и — е. СИРА 7 2. [МЯ1 [ Вычислите произведение матриц ~х~ 1) (хэ 1) ~х„ 1) 3. [МЯ1[ Чему равен определитель хг 1 О ... О -1 хэ 1 бег О -1 хе 1 — 1 ' 1 О О ... -1 х 4. [МЯО] Докажите тождество (8). УПРАЖНЕНИЯ ° 1. [ЯО[ Так как частное [в/е) Равно единице более чем в 40% времеви выполнения алгоритма 4.5.2А, на некоторых компьютерах может оказаться выгцаным проверить этот случай и запретить выполнение операции д«ления, когда частное равно единице.

Является ли следующая ИХХ-программа, реализующая алгоритм Евклида, более эффективной, чем программа 4.5,2АР б. (ВМЯЯ Пусть хн хг, ... — последовательность вещественных чисел и кажлое из них больше некоторого положительного числа и Докажите, что существует бес кон ачяая цепная лробь //хм хм, .. // = 1Пп„.~, //хн...,х //. Покажите также, что //хмхг,... // необязательно существует, если предположить только, что х, > 0 для всех у. О.

(МЯЛ) Докажите, что разложение числа в правильную цепную дробь едннсщвенно в следующем смысле. Если Вм Вг,... — положительные целые числа, то бесконечная цепная дробь //Вм Вг,... // есть иррациональное число Х, расположенное между 0 и 1, разложение которого в правильную цепную дробь имеет злементы А = В„для всех и > 1. Если же Вн ..., В, — положительные целые числа, причем В > 1, то правильная цепная дрсбь для числа Х = //Вн ., В // имеет засыенты А„= В„для 1 < и < нз, 7. (М26) Найдите все перестановки р(1)р(2)... р(и) целых чисел (1, 2,..., и), таких, что Ко(хм хг,..., хо) = Кь(хми, хмгн ..,, храп) является тождеством для всех хи хг,, х,. 6. (МЯО] Покажите, что если при разложении в иравнльиую цепную дробь числа Х определено Х„, то -1/Х„= //А„,..., А„-Х//.