AOP_Tom2 (1021737), страница 107
Текст из файла (страница 107)
Какие выводы можно сделать относительно гг(х), ..., р(х) в уравнениях (36)-(43)7 Прежде всего, из уравнений (38), (40) и (43) имеем Соответственно равенство (42) выполняется тогда и только тогда, когда (45) (46) (47) 2Л(:с) = Л(2х); 2р(х) = р(2х) + Л(2х) — р(2х); 2а (х) = а (2х), 2т,„(х) = т (2х) при т > 1. Из (45) следует, что Л(х) есть просто константа, кратная х; так как она отрицательна, можно записать Л(х) = — Л .
(48) (Соответствующий коэффициент приобретает вид Л = 0.39792 26811 88316 64407 67071 61142 65498 23098+, (49) но способ, которым его можно вычислить, неизвестен.) Из уравнения (46) следует, что рг — — — Л и 2рь = 2ьрь — 2ьрь при )г > 1: другими словами, Из уравнения (47) следует также, что оба степенных ряда (51) тм(х) = тшх ат(х) — атх~ являются просто лииейнымн функциями. (Но это не распространяется на функции 7„,(х) и б (х).) Если в уравнении (44) заменить х на 1/2х, то получим (52) 28(1/2х) = Я(1/х) + С(х/(1 + х)), ко 0.8 0.6 6(),", о.о -о.г -ол -о.ь -о.я — 1.о о о ко г.о з.о ае Х 25(х) = С(1/(1+ 2х)) + 5(2х) = Я(2х) — р(2х). (44) рь = рь/(1 — 2 «) прн й > 2.
(50) а последнее уравнение при х, близком к О, при помощи уравнения (39) преобразу- ется в 20(2х) + 2л(2х) = С(х) + Я(х) + С(х/(1 + х)). (53) После подстановки в это уравнение степенных рядов вместо функций коэффициенты при 18 х в обеих частях должны быть приравнены. Следовательно, (54) 2а(2х) — 4Лх = а(х) — Лх + а(х/(1 + х) ). Уравнение (54), определяющее а(х), — рекуррентное. Действительно, предположим, что функция 1)1(х) удовлетворяет уравнению ~/1(х) = — ~х+ф~-) +~6( — )), 1/1(0) =О, 1п(0) =1. (55) Тогда уравнение (54) означает, что а(х) = -Л11(х). 3 2 Более того, из итерационного уравнения (55) следует х г 1 ~ 1 2 ~ 2" д 21+ух а>О О<1<1 Отсюда получаем, что обобщение 1/1(г) для степенных рядов имеет вид и-1 1/(х) =~~,( — 1)" '/пх", 1/и= — ~, ~,~, ~ )+ — "; п>1 а=о (56) (57) (58) 1 5= Е18(1'/1") = ~~~ 2 1(Ь(0)+~ О(х)/1(х)1(х), Ь>1 е см.
упр. 27. Эта формула удивительно похо1ка на выражение 6.3 — (18), полученное в связи с алгоритмами дискретного поиска в дереве, а в упр. 28 приводится доказательство справедливости формулы 1)1„= О(п ~). Теперь нам известно о(х), за исключением случая, когда Л = — р1 постоянно. Уравнение (50) связывает функции д(х) и р(х), исключая коэффициент д1. Из ответй к упр. 25 видно, что все коэффициенты функции р(х) могут быть выражены через Р1, Рэ, Рм ....
Более того, константы а и г могУт быть вычислены пРи помощи метода, применяемого для решения задачи в упр. 29; при этом между коэффициентами функций Т (х) и 5 (х) сохраняются сложные связи. Тем не менее, похоже, что единственным способом вычисления всех коэффициентов для различных функций. входящих в выражение для С(х), является итеративное решение рекуррентного уравнения (36) численными методами. После вычисления хорошего приближения к С(х) можно оценить среднее время выполнения алгоритма В следующим образом.
Если и > с и если выполнить й сдвигов вправо, то величина 1' = пс будет заменена на У' = (и — е)и/2". Значит, 1'/У' равно 21/(1 — Х), где Л = в/и равно > х с вероятностью С(х). Отсюда следует, что число битов в ив уменыпается в среднел1 на константу где /ь(х) = )8(2ь/(1 — х)). Получаем (59) При и = с ожидаемое значение числа !8ис будет приблизительно равно 0.9779 (см.
упр. 14), поэтому общее количество циклов "вычитание и сдвиг" алгоритма В будет приблизительно равно исходному значению числа !8 пи, умноженному на 1/Ь. Учитывая свойство симметрии, это количество приблизительно равно исходному значению числа !8и, умноженному на 2/Ь. В результате выполненных в 1977 году вычислений Ричард Брент (В!сЬагд Вгеп!) получил для этой фундаментальной константы значение 2/Ь = О. 70597 12461 01916 39152 93141 35852 88176 66677+. (60) В результате более глубокого анализа этих функций Бригитта Валле (Вг!8!!се Ча)!Ье) высказала предположение, что постоянные Л и Ь могут быть сяязаны примечательной формулой Л 21п2 (61) гт Значения, вычисленные Брентом, вполне согласуются с этим далеко нетривиальным утверждением.
Вызывает большой интерес анализ алгоритма В, успешно выполненный Валле на основе строгих "динамических" методов (см. А!8огВЬш!са 22 (1998), 660 — 685) . Вернемся к предположению в (32), состоящему в том, что и и е нечетные н изменяются в интервалах 2 < и < 2 +' и 2" < с < 2"+', Эмпирические испытания алгоритма В, проведенные с несколькими миллионами случайных значений на входе и с различными значениями гп и и, взятыми из интервала 29 < т,п < 37, показывают, что в действительности усредненное поведение алгоритма определяется соотношениями С ю -'го+ 0.203п+ 1.9 — 0.4(0.6)'" ", гп > и, (62) 17 ъ гл + 0.41п — 0.5 — 0.7(0.6)"' при довольно небольшом стандартном отклонении от наблюдаемых средних значений.
Коэффициенты -' и 1 при ш в выражениях (62) могут быть строго проверены (см. упр. 21). Если же предположить, что и и и — любмс целые числа, независимо и равномерно распределенные в интервалах 1<в<2~, 1<с<2~, (63) то можно вычислить средние значения величин С и Р по уже имеющимся данным: С ж 0.7ОУ+ 0(1), 17 е 1,41Х+ 0(1). (64) (См. упр. 22.) Это хорошо согласуется с результатами последующих эмпирических экспериментов, выполненных с несколькими миллионами случайных входных данных для Х < 30. Этн эксперименты показали, что в качестве подходящих значений для заданных распределений входных данных и и и можно взять С = 0.70Аг — 0.5, О = 1.41% — 2.7. (65) Теоретический анализ непрерывной модели Брента алгоритма В предсказывает, что при предположениях (63) величины С и )9 асимптотически равны 2Х/Ь и 4Л/Ь, где 2/Ь - 0.70597-- константа в (60).
Согласование с результатами экспериментов настолько хорошее, что константа 2/Ь Брента должна в равенстве (65) принимать в качестве значения число 0.70, поэтому в уравнении (62) число 0.203 необходимо заменить числом 0.206. На этом анализ средних значений С и 17 завершается. Анализ остальных трех величин, присутствующих в формуле для времени выполнения алгоритма В, выполняется довольно просто (см.
упр. 6-8) . Теперь, когда примерно известно поведение алгоритма В в среднем, рассмотрим сценарий "наихудшего случая". Какие значения и и е являются в некотором смысле наиболее трудно обрабатываемыми? Предположим, как и ранее, что [1йн) = гп и (18и] = и, и попытаемся найти и и е, такие, при которых алгоритм будет выполняться наиболее медленно.
Принимая во внимание, что операции вычитания выполняются несколько медленнее, чем операции сдвига, сформулированный вопрос можно перефразировать так: при каких значениях входных данных и и с потребуется выполнить наибольшее число вычитаний. Ответ звучит несколько неожиданно: максимальное значение величины С равно точно (66) шах(т, и) + 1, хотя поверхностный (наивный) анализ позволил бы предположить, что возможны значительно ббльшие значения С (см. упр. 35). Вывод выражения (66), описывающий наихудший случай, довольно интересен, поэтому он предлагается читателям в качестве занимательной задачи (см.
упр. Зб и 37). УПРАЖНЕНИЯ 1. [М21] Приведите простой способ вывода соотношений (8)-(12) нз соотношений (6) н (7). 2. [М22] Пусть известно, что число и делит щи~... е„. Докажите, что и делит йсб(в,щ) йсб(и,ед)...йети(и,в ). 3. [М22] Покажите, что число упорядоченных пар положительных чисел (в,е), таких, что 1сш(и, в) = в, есть число делителей п . 4. [М21] Покажите, что для любых положительных чисел и в е найдутся такой делитель и' числа в и такой делитель е' числа с, что и' 1.
е' н йи' = 1сш(и, с). 5. [М26] Разрабозвйте алгоритм для нахождения наибольшего общего делителя двух целых чисел, аналогичный алгоритму В, но базирующийся на представлении этих чисел в ураеноеешсвввй троичной системе счисления. Продемонстрируйте выполнение алгоритма на примере вычисления йсб(40902, 24140). 6. [МЯЯ] Пусть и и в — случайные положительные целые числа. Найдите среднее значение и среднеквадратичное отклонение величины А, входящей в формулу для времени выполнения алгоритма В. (Это количество сдвигов вправо чисел и и в во время подготовительной фазы.) 7.
[МЯО] Проанализируйте величину В, входящую в формулу для времени выполнения алгоритма В. 8. [МЯЛ] Покажите, что в программе В среднее значение величины Е приблизительно равно гС,р, где С»р — среднее значение С. 1 9. [12] Найдите 8сд(31408, 2718), выполнив вычисления вручную с использованием алгоритма В. Прн помощи алгоритма Х найдите также такие целые числа т и п, <тобы 31408гл + 2718п = Ясд(31408, 2718). Р 10.
[?ВЩ] Пусть 4„— количество упорядоченных пар целых чисел (и,в), принадлежащих интервалу 1 < и, в < и, таких, что и .1 в. Назначение данного упражнения — доказать, что аппп».»,» 4»/п~ = 6/я, и тем самым сформулировать теорему О. г а) Используя принцип включения н исключения (раздел 1.3.3), покажите, что р~ сю где суммирование выполняется по всем просшим числам р;. Ь) Функция Мебиуса р(п) определяется правилами р(1) = 1~ р(радуг...
р ) = (-1)', если рп рг,..., р, — различные простые числа, и р(п) = О, если и делится на квадрат простого числа. Покажите, что д» = 2 „>, р(2) [и/й]г, с) В качестве следствия из (Ь) докажите, что 1пп, д»/и = 2 ь>г д(к)/?с д) докажите, что (~ ~~, д(?г)/йг)(~„~~ 1/глг) = 1. указание. Если ряды сходятся абсолютно, то 11. [МЯЯ] Чему равна вероятность того, что йод(и, в) < 3? (См. теорему П.) Чему равно среднее значение йсб(и,в)? 12. [М24] (Э. Чезаро (Е. Сеейго).) Пусть и и в — случайные положительные целые числа. Чему равно среднее число их общих (положительных) делителей? [Указание. См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
