Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 88
Текст из файла (страница 88)
Самыми интересными явлюотся, вероятно, случаи, когда х = 1, х = 1/чг2 и х = ф. Например, при х = 4 получаем 2О(4ф) — 5О(2ф) + О(ф~/2) — О(ф~) = 2О(2фз). 27. При и > 1 в соответствии с упр. 1.2.11.2-4 имеем 2ф (») ~~, '2-ы ч, ч, (. /2з)г и,"~2-з(»«г! ~з -г зйо у=о г>о з>1 з=о 2 зг"+и ~ ~г ~гВ 2зг" и/ зйг г=о г И ' Г>Гзтг (( Р( ) - 1 гзГз+ о (( )г(з)и-« 1>г 2«0 е"Гз"-1 2тз /з7« - 2дз *' 2хг 1згз-г >, з з- » Интеграл равен сумме вычетов 2+ 2х«Л/1п2, т. е. произведению и з и т~/(61и 2) + /(и), где /(и) = 2 ~ ~И((;(2+ 2тгй/!и 2)Г(2+ 2хай/1п 2) ехр(-2т«1г!йи)/!и 2) з>1 есть периодическая функция 18 и со "средним" значением, равным нулю.
29. (Решение П. Флажоле (Р. Р!а)о)ес) и В. Валле (В. Ча!!4е).) Если при соответствующих условиях /(х) = ~ >, 2 ~д(2 х) н д'(з) = / д(х)х' гйз, то/'(з) = Яз>г 2 щ'+цд'(з) = д" (з)/(2'+' — Ц и /(х) = — ' ~'+'~ / (з)х 'аз. В етом случае, полагая, что д(х) = 1/(1+х), найдем преобразование в аиде д (з) = х/яи ггз при 0 < 3(з < 1. Таким образом, / +' 'г(з к-» 2« 1+2>х 2хг / . (2«+' — Цииз.з и, конечно, ) „>, 2 "Г'+" = 1/(2ью — Ц. 28.
Следуя обгцначениям упр, 6 3-34(Ь), положим, что Я„(ги) =) „„,'(1-х/ги)" н Т„(ги) = 1/(е»г — Ц. Получаем Я (ги) = Т„(ги) + О(е "Г и/гпз) и 2ф»+г = 2 .>, 2 зги»(21) = г, + О(п ), где г = ~12«2 гдТ„(21). Из того, что г„+г < г„, а 4гз„— т = 1/(е" — Ц положительное, но малое число, следует г„= В(н ). Более подробную информацию можно получить, если записать Отсюда следУет, что /(х) — сУмма вычетов,— м„х '/(2'+' — Ц пРи Яа < О, т, е.
1+ х )б х+ Ох+ хР((бх) — 1хй+ зйхз — $х~+ . °, где функция 2гг ~-» ив 2хнг! 1п2 л- вгп)г(2нгхй/1п2) 1 хэ бг(х) = /(х) — /(1/х) гх х1бх+ -х+ хР(1бх) — — + (1 — х~)йг(х), 2 1+х где ге(х) ~ Ей а( Цйхй/(2й+! Ц ЗО. Имеем газ(х) = Ег(х) — Ег(1/х) + Вй(х) — ХЪ(1/х), где 1 1 2й+' 1+ 2'(1+ 2йх) ' й,г>! 1 1 2 + +2 й.г>! Преобразования Меллина будут иметь вид Ьт(.)= —.' (.)/(2"'- ), Ь ()= —." Ь()/(2'+'-Ц, эгп гга вщ яа г>! й>а Ь( ) = ~ '(2'+ Ц'-! = ~ '(' ),, ' !>! й>а Таким образом, при 0 < х < 1 получаем следующие выра!кения! Ег(х) ~ а(О) + и(-Цх(!О х+1) — а'(Цх/1п 2+ х 4(1бх) -"! —,о(-Ь)(-х)й, й>з 2й-! Ез(х) гх Ь(0) + Ь(-Цх(!Ох+а) — Ь'(Цх/1п 2+ хВ(1бх) — ~~ й Ь(-Ь)(-х), й>й Ег(1/х) = ~, „+, й>! г г1г*)=й.— (й*-гга--- — + — +ьг!! !).
( — х)й ! - 1 1 Нй-! 2й+! 2 2й+! — 1 (и 2 й>! ~~~- ( Ь ) 2й+' '-1' есть периодическая функция, абсолютные значения которой никогда не превышают 8 к 10"гз, (Ввиду малости фуюгцни Р(г) Врент в своей первой рабате не обратил на нее внимания,) Преобразование Мелляна функции /(1/х) имеет вил /'(-е) = в /((1-2' ') нп яв) при -1 < 3)а < О, поэтомУ /(1/х) = уы / Г +„.' „Ьк„-;х 'г(а/(1 — 2' '). Найдем тепеРь пРи Яз < -1 вычеты цодынтегральной функции /(1/х) = -'х — -'хй+.". (Эта формула могкет быть получена и непосредственно.) Имеем Зг(х) = 1 — /(х), и отсюда следует !п2 ( э!пЬ(2тяг/!и 2) иьг !и 2 1 шпЬ(2тяэ/!в 2) и' гл- -г гр1) .„) !в 2 ~~', ~зшЬ(2тяг/Ьз 2) 1 Ь вЂ” 1 34.
Бригитта Валле (Вг!8!ые Ъ'а(!бе) с помощью приближения, существенно отличающегося от приближения, использованного Брентом, предлогкила изящный и строгий анализ алгоритма В, который опубликован в журнале А!бог!гЛш!са 22 (1998), бб0-885. Действительно, ее методы доказательства существенно отличаются от известных до снх пор методов предсказания поведения а:ггорнтма В наподобие эвристических моделей Брента. Таким образом, впервые была строго решена задача анализа бинаряого алгоритма нахождения наибольшего общего делителя, которая до сих пор доставляла математикам массу хлопот, 33. По индукции при т > и длина равна гп + 1и/2] + 1 — [т = и ха 1].
Однако из результата упр. 37 следует, что алгоритм не может выполняться столь медленно. 36. Пусть а, = (2" — (-1)")/3; тогда ао, аг, аз, ... = О, 1, 1, 3., 5, 11, 21, (В двоичном представлении этой последовательности чисел содержится интересный набор нулей и единиц. Обратите внимание на то, что а„= а„г + 2а„-г н а, + а„+г = 2".) Положим, что и = 2 +' — а„.лз, о = а„+э при т > я, При т = и > О положим и = шах(а„+т,2а„+г) и и = аи+з — и. Еще один пример для случая, когда иг = и > О, имеет вид и = 2"+' — 2, е = 2"+' — 1. При таком выборе требуется выполнить больше сдвигов, что дает В = 1, С = и+ 1, Р = 2я, Е = и, Это наихудший с точки зрения времени выполнения случай для алгоритма В.
32. (Решение предлохгено Дж. О, Шзллитом (Л. О, ЗЬа(!!1).) Это одна из тех задач, в которых для того, чтобы доказать то„что требуется, необходимо доказать больше того, что требуется. Пусп* Я(и, и) — число шагов, на которых осуществляется операция вычитания, выполненных алгоритмом В над входными величинами и н о. Докажем, что Я(и.в) < 18(и+ и).
Отсюда следует; что Я(и о) < (!3(и+ о)] < 1!82 плах(и о)] = 1+ 1!8 плах(и иЦ по построению. Заметим, что В(и, и) = 5(и, и), Если и четно, то В(и, и) = В(и/2, и). Следовательно, можно положить, что и и о нечетиы. Можно также положить, что и > о, поскольку 5(и и) = 1. Тогда по индукции Я(и и) = 1+5((и-и)/2 и) < 1+!8((и — о)/2+о) = !8(и+и). А это означает, что наименьшей парой чисел, требующей и шагов вычитаний, будет 2п-г + 1 2а-г 38. При формировании матрицы А (размера 2 х 2) целых чисел наподобие А("„) = („",„;), таких, что ю — размер машинного слова, следим за наиболее значимыми н наименее значимыми словамн операндов (наиболее значимые используются для обозначения знака г, а нанмелсе значимые — для определения общего числа сдвигов вправо), где и' н и' меньше и и и.
(Вместо того чтобы разделить моделируемые нечетные операнды на 2, умножаем четные операнды на 2 до тех пор, пока не вычислим число, кратное ю, в результате выполнения точно 1бш сдвигов.) Проведенные эксперименты показали, что хотя бы на одном компьютере этот алгоритм выполняется в четыре раза быстрее алгорнтлщ (. При использовании подобного алгоритма в упр. 40 отпадает необходимость в наиболее значимых словах.
Алгоритмы, возможно, более быстрые описаны в рабатах 1. Зогепзоп, э. А!8огззйшэ 16 (1994), 110-144; Бйа)8!с апб Богепэоп, Ьесгиге )11азеэ ш Совр. Зс1. 877 (1994), 169-183. 39. (Решение предложено Майклом Пенкам (ЗВ!с)!ае( Репи).) У1. [Найти степень 2.) То же, что на шаге В1. 'У2. [Начальная установка.) Присвоить (и1, из, из)»- (1, О, и) и (и1, из, из) 1- (и, 1-и, с). Если число и нечетно, присвоить (11,1»,эз) 1 — (О,— 1,-е) и перейти к шагу У4. В п1ютиэном случае присвоить (11, Фз, Зз) + (1гО, и) УЗ. [Выполнить половинное деление 1».] если 11 н зз четны, присвоить (11,1з, зз) +- (11,1з,зз)/2; иначе — присвоить (1111»,зз) +- (11+ е,зз — и!1»)/2.
(В последнем случае $1 + и и Гз — и будут оба четными.) Ъ'4. [Гз четно".) Если 1» четио, вернуться к шагу УЗ. Уб. [Переустановить шэх(из,из) [ Если Зз положктельно, присвоить (из,из,из) 1- (11, Гз, Фз); иначе — присвоить (и1, ез, ез)»- (и — 11, -и — гз, -гз). Ъ~б. [Вычесть.) Присвоить (11 Гз,зз)»- (и1.из,из) — (и»,ез,из) Затем, если 11 < О, присвоить (11, зз)»- (11+ и Зз - и). Если Гз Р О, вернуться к шагу УЗ. В противном случае закончить выполнение алгоритма с результатом, равным (и!, из, из 21). $ Ясно.
что взаимосвязи в (16) сохраняются; кроме того, после каждого из шагов У2-Уб 0 < и1,е1,11 < и, 0 > из,имзз > -и, 0 < из < и, 0 < из < и, Если после шага У2 число и четно, то можно упростить шаг УЗ, так как оба числа 11 и 1з четны тогда и только тогда, когда четно зз. Точно так, если е нечетио, оба числа 11 и зз четны тогда и только тогда, когда четко 11. Значит, как н в алгоритме Х, вычисления, связанные с получением чисел из, из и 1з, выполняемые для нечетных чисел и после шага У2, можно пропустить.
Это условие зачастую известно наперед (т. е, если э четно, а вычисляется и ' по модулю «). См. также А. 1й%. Во)апсзу)с, В. Р. Вгепц Сошризегэ апд Ма!5. 14 (1981), 233. 40. Пусть гл = 18 шах([и[, [е[). По индукции можно показать, что после выполнения з рвз на шаге к3 операции с 1- с+1 получим [и[ < 2 ы"ю!1, [с[ < 2 !1+ю!з. поэтому з < 21п. Если шаг К2 выполняется 1 раз, получим Ф < з+ 2, так как з увелкчивается каждый раз, но не на первом и последнем шагах. [См. 17 Я '83 (Ног!)»-Нойааа, 1983), 145-154.) Примечание. Если и = 1, е = 3 2» — 1 н й > 2, получаем ш = 5 + 2, з = 2й, З = 5 + 4. При и = из и и = 2из-! в последовательности ие = 3, и! = 1, из+1 = ш1и([Зи, — 16и 1[, [5из — 16и, 1[) получаем з = 2/+ 2, Г = 2/+ 3 и (эмпирически) т 6/.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
