Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 2
Текст из файла (страница 2)
(39) Пусть т(х) = д(х) = 1 — постоянная функция. Тогда для 0 < х < 1 имеем 11г < у < 2К, откуда 55 "д. < 15 "у < 1(/"у < У"у < 1(/"у < «2 "у < ~12 "~. Из равенства (35) следует, что й()п2)зб-я < ( 1)«Вя(х) < ье(1п2)з2-~ для 0 < х < 1. Таким образом, из (32) и (36) следует, что доказана следующая теорема. Теорема %'. Прп и -+ оо распределение Р„(х) равно 18(1+ х) + О(2 "). В действительности Р„(х) — )8(1+ х) лежит между 1з3(-Ц"+'5 "(1п(1+ х)) ()п2/(1+ х)) и ~1(-Ц"+'2 "(1п(1+ х)) (1п 2/(1+ х)) для О < х < 1. $ Если несколько изменить функцию у, можно получить более сжатые границы (см. упр. 2Ц.
На самом деле Вирсинг пошел гораздо дальше, доказав в своей работе, что Р'„(х) = )8(1+ х) + (-Л)" Ф(х) + О(х(1 — х)(Л вЂ” 0.03Ц"), (40) где Л = 0,30366 30028 98732 65859 74481 21901 55623 31109- = //3,3,2,2,3,13,1,174,1,1,1,2,2,2,1,1,1,2,2,1,...//. (4Ц Это фундаментальная постоянная (к счастью, никак ие связанная с более известными постояниыми), где Ф вЂ” интересная функция, аналитическая в комплексной плоскости за исключением отрицательной вещественной оси от -1 до -оо. Функция Вирсинга удовлетворяет соотношениям Ф(0) ж Ф(Ц = О, Ф'(0) < О и ЯФ = — ЛФ. Таким образом, с учетом (37) зта функция удовлетворяет тождеству Ф(г) — Ф(г+ Ц = -Ф~ — ).
1 г 1 -Л Ь1+г . (42) Далее Вирсинг показал, что г и ( х Ф ~- - + — ) = сА " 1ой Н + О(Ц при Н -+ оо, (43) Н)- где с — константа, а и = Т(и, о) — число итераций алгоритма Евклида при выполнении операций иад целыми числами и > е > О. Полисе решение проблемы Гаусса было иайдеио несколькими годами позже К. И. Бабенко ]Д4Н СССР 238 (1978), 1021-1024], который использовал мощный аппарат функционального анализа для доказательства следующей формулы: Г„(х) = 18(1+ и) + ) Л" Фу(х) (44) у>з для всех 0 < х < 1, и > 1.
В втой формуле ]Лг] > ]Лг] > ]Лг] > " каждая из функций Фз(г) — аналитическая функция иа комплексной плоскости за исключением (-оо.. — 1]. Функция-Фг — зто функция Вирсингв Ф, а Лг = -Л, в то время кзк Лг м 010088 Лч м -003550 Лг м 0.01284 Ле м -0.00472, Лг «~ 000175. Бабенко установил также дополиительиые свойства собственных значеиий Л, доказав, в частности, что оии являются зкспоиенциальио убывающими при т' -~ оо и что их сумма в (44) при 1' > й ограничена величиной (тг/6)]Лг]" ~ ппп(х, 1 — х). ]Дополнительная ииформация содержится в работах Бабенко н Юрьева, опубликованных в ДАН СССР 240 (1978), 1273-1276, в работах Ыайера (Мауег) и Роепсторфа (Йоерзгогй'), 7.
Яабзбса) РЬуасз 47 (1987), 149-171; $0 (1988), 331-344; Д. Хеисли (Б. Непа!еу), 7. Ншпбег ТЬеогу 49 (1994), 142-182; а также в работах Доде (Ваидй), Флажоле (Г1а)о!ег) и Валле (Ъа114е), Сотб(пагог(сз, РгоЬаЬНйу аш1 Сотрибп8 6 (1997), 397-433; Г1а)о)еЬ ЛаНбе, ТЬеогебсз1 Сотр, Яс(. 194 (1998), 1-34.] Джон Хершбергер (ЗоЬп НегзЬЬегйег) вычислил 40-зиачное значение Л в (4Ц, От непрерывного к дискретному. Выше были получены результаты, относящиеся к распределению вероятностей для цепных дробей в случае, когда Х— вещественное число, равномерно распределенное в интервале [О,.
1). Однако вероятность того, что вещественные числа являются рациональными, равна нулю (почти все числа являются иррациональными), так что эти результаты непосредственно к алгоритму Евклида неприменимы. Прежде чем применять теорему 1«' для решения задачи„необходимо преодолеть некоторые технические затруднения. Рассмотрим следующий результат, основанный на элементарной теории меры.
Лемма М. Пусть /1 „ /ю...,,/м зю... — попарно непересекающиеся лодынтервалы, содержащиеся в интервале [О., 1), и пусть Х= Ц/„,Т= ДЗ,, К=[О.. ]1(Х~.Т). »>1 »>1 Предположим, что К имеет меру нуль. Пусть Р„означает множество (О/и, 1/и, ..., (и — 1)/и). Тогда я [ХОР„] (45) Здесь р(Х) — мера Лебега множества Х, т. е. 2„»> )епй«11(/»), а ]ХО Р„[ обозначает число злементов множества Х О Р„. Доказательство.
Пусть Хи = (.)15»бм 1» и 7и = Ц<»<м У» Для заданного «> 0 найдем гг'„достаточно большое, чтобы выполнялось соотношение р(Хм) + р(уи) > 1 — «, и положим КО=КО О/» О [/.7. »>Ф»>г« Ясно, что если Х вЂ” любой из интервалов (а..Ь), [а..'Ь), (а..Ь] и [а..Ь], то р(У) = Ь вЂ” аи пр(У) - 1 < ]/О Р„[ < пр(Т) + 1.
Пусть теперь г„= ]Хм О Р ], в„= [Дч О Р„], Ф„= ]Ки О Р„]; тогда гв + ап+Сп = и~ нр(Хи) — К < г„< пп(Хм) + Ю; пр(,7р~) — Ф < в„< пр(яч) + д'. Значит, Ю /г' г„г„+ 1„ р(Х) — — —. < р(Хи) — — « — и и и и »в Х г1 = 1 — —" <1 — и(Я~)+ — < р(Х)+ — +«. и и Это неравенство справедливо для всех и и для любого «; следовательно, Иш г /п=р(Х) $ В упр. 25 показано, что лемма 54 нетривиальна в том отношении, что для справедливости формулы (45) необходимо принимать какие-то довольно ограничивающиее предположения.
Распределение частичных отношений. Объединив теорему % и лемму М, докажем теперь несколько фундаментальных свойств, касающихся алгоритма Евклида, Теорема Е. Пусть и н к — положительные целые числа; пусть также р»(о,и)-— вероятность пио„что (/г + 1)-е частное А»+1 в алгоритме Евклида равно а, когда с = н и и выбирается случайно.
Тогда 1 1нн р»(а,я) = Р»(-) — Р»( — ), 1 где Г»(х) — функция распределения (22). Доказагнельсгнео. Множество Х всех Х в (0..1), для которых А».»1 = а, есть объединение ненересекающихся интервалов, как и множество 7 всех Л, для которых А»»г ~ а. Поэтому применима лемма М, причем множество /С вЂ” множество всех Л, для которых А»+» не определено.
Далее, Р»(1/а) — Р»(1/(а + 1)) есть вероятность того, что 1/(а+ 1) < Л» < 1/а, а это не что иное, как р(Х), т. е. вероятность того, что А»+1 = а, $ Из теорем Е и гу следует, что частное, равное а, встречается с вероятностью !8(1+ 1/а) — 18(1+ 1/(а+ 1)) = )8((а+ 1) /((а+ 1) — 1)).
Так, частное 1 встречается примерно в 18(4) = 41.504% случаев; частное 2 встречается примерно в 18Я) = 16.993% случаев; частное 3 встречается примерно в 18(»аэ) = 9.311% случаев; частное 4 встречается примерно в 18(Я) = 5.889% случаев. В действительности, если алгоритм Евклида формирует частные Ам Аю ..., Ао приведенное доказательство гарантирует такое поведение только для тех А», 7г которых мал цо сравнению с и На значения А~ и А» ю ... это доказательство не распространяется. Однако можно показать экспериментально, что распределение последнего ряда А» ы А1 т, ...
частных, по существу, такое же, как и первого ряда. Рассмотрим, например, разложение в правильную цепную дробь ряд правильных дробей со знаменателем, равным 29. э = //29/! ээ = //3,1,1,1,2// ф =//1,1, 14// Я = //1,3,7// ~Дэ =//14,2// Д =/!3,4,2!! жы =!1,1,4,3! ~~р — — !/1,3,1,5// т э = //9 1 2!! за = !/2,1,9// зэ =//1,1,2,2,2/! ~д =//1,4,1,4/! ~д = //7,4// Я = //2,1,1,1,3// Я = //1,1,1,1„1,3/! ф = //1,6,4// Й = !!5,1,4!/ Я = !~2,2,2,2! В = //1,1,1,9// Й = //1,8,1,2// = //4, 1~5/! ~р = !!2~4~3// тэ = //1~2~4~2/! щ = !! 1113~2// тэ = //4,7// Я = //2,14// Я = //1,2,1,1,1,2/! Я = !/1,28// В этой таблице следует обратить внимание на несколько моментов. а) Как указывалось ранее, последнее частное всегда равно 2 или более. Далее, имеем очевидное тождество !!хм..., х„м х„+1// и //хм...,х„мх„,1//, (46) показывающее, каким обраэоч связаны цепные дроби, в которых последнее частное равно единице, с правильными цепными дробями, Ь) Имеется простая связь значений, расположенных в правых столбцах, со зна чениями, расположенными в левых столбцах.
Видит ли читатель зту связь? Она заключается вот в чем: 1- //яп кз,..., лв// = //1, хг -1, хз,..., х„//; см, упр. 9. с) Между левыми и правыми числами в первых двух столбцах наблюдается симметрия: если встречается //Аы Ат,..., А~//, то встречается также //Аг, ° °, Аз, А~//. Так происходит всегда (см. упр. 26). д) Если исследовать все частные в таблице, то обнаружится, что всего их имеется 96 и из них зез =40.6%равны 1, 1ы = 21.9% равны 2, з = 8,3% равны 3. Эти данные хорошо согласуются с приведенными выше значениями вероятностей. х1исно шагов деления.
Вернемся теперь к исходной проблеме и исследуем вели- чину ҄— среднее число шагов деления при с = п (см. формулу (19)). Приведем отдельные значения Т„. 102 103 104 105 4.6 5.3 4.7 4.6 9999 10ЙЮ 10001 8.6 8.3 9.1 99999 100000 100001 10.7 10,3 11.0 95 96 97 98 99 100 101 5.0 4.4 5.3 4.8 4.7 4.6 5.3 996 997 998 999 1000 1001 6.5 7.3 7.0 6.8 6.4 6.7 49998 49999 50000 5(Ю01 9.8 10.6 9.7 10.0 (48) Отсюда следует, что (49) Обратите внимание на некоторую неустойчивость поведения.
Если и простое, то соответствующее ему значение Т больше соседних значений. И зто значение соответственно меньше соседних. если и содержит много делителей. (В приведенном списке числа 97, 101, 103, 997 н 49999 — простые числа; 10001 = 73 137; 49998 ж 2 3 13 641; 50001 = 3 7.2381; 99999 = 3 3 41 271 и 100001 = 11 909Ц Нетрудно понять причину такого поведения. Если йети(н, с) = 6, то алгоритм Евклида выполняет операции с числами н и е так же, как и с числами и/о и с/и. Позтому, когда число и = и имеет несжиько делителей, существует много способов выбора такого и, для которого и ведет себя так, как будто его значение меньше значения, которое есть на самом деле. Соответственно рассмотрим другую величину, г„, которая является средним числом шагов деления, для случал, когда с = и и и есть число, взаимно вросшее с и.
Тогда Ниже приводится таблица значений тв для тех же значений п, которые были рас- смотрены выше. пш тв = и= ти— Очевидно, что т„ведет себя значителыю лучше, чем Т„, и оно должно значительно легче поддаваться анализу. При внимательном изучении таблицы значений т„ при малых и обнаруживается ряд серьезных отклонений, например тю = гию и тю = тгээ. Но по мере роста числа и значения т становятся вполне нормальными, как это видно в приведенной выше таблице, и не указывают ни на какую особую зависимость от свойств разложимости на простые множители числа п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
