AOP_Tom2 (1021737), страница 196
Текст из файла (страница 196)
1ппй ~с„(-Лзй.йг/Лзй — !) = 1/тг . 26. Согласно (39) левая часть равна 25(1/х)-55(1/2х)+25(1/4х)-2о(х)+5о(2х) — 2Я(4х)) согласно (44) правая часть равна Я(2х) — 2л(4х) + 2$(1/х) — Я(1/2х) — 2о(х) + 4Я(2х)— 4Я(1/2х) + 2Я(1/4х). Самыми интересными являются, вероятно, случаи, когда х = 1, х = 1/ч/2 и х = ф. Например, при х = ф получаем 2С(4ф) — 5С(2ф) + С(4! /2) — С(ф ) = 2С(2ф') 27. При и > 1 в соответствии с упр.
1.2.11.2-4 имеем 2' †! 2-! й 2ф„= ( ") ~ 2-'й ~ ~(/ /2")' = ~ 2-"'"+" ~ т" ' й>а т=е г>а й>! — ! / 2 й!"+!) ч В)2 Г' )/и й>! !=а 3/2.!. 2 й( )1 ( ) — 1 3/2+ йй С( )Р( ) т т>1 22! сч/22' 1 2)тт / 2212 — ) 2лт / 22-2 т>! /3/2 — ' ./З/2-* й Интеграл равен сумме вычетов 2 + 2яс/с/1п 2, т. е. произведению и 2 и кз/(б!п 2) + /(и)! где /(и) = 2~ ~Я(й(2+2ят/с/1п2)Г(2+2яс/с/1п2)ехр( — 2тг/с!би)/1п2) й>! есть периодическая функция 16 и со "средним" значением, равным нулю.
29. (Решение П. Флажале (Р. Р!а)о)ес) и Б. Валле (В. Ъа!16е).) Если при соответствующих условиях /(х) = 2 й>, 2 йд(2йх) и д*(з) = (а д(х)х' 'г!х, то /*(з) = 2 „>, 2 йр+')д (з) = д (з)/(2'+! — 1) и /(х) = —,', /;~' /*(з)х 'дз. В атом случае, полагая, чта д(х) = 1/(1+х), найдем преобразование в виде д (з) = тг/гбп тгз при 0 < Яз < 1. Таким образом, =Е 1 1 1 /'/"! ях-тде /(.) = , 2" 1+ 2йх 2л1,/,/2 г (2'е! — 1)гбптгз и, конечно, 2"й>, 2 "О+') = 1/(2'т' — 1).
26. Следуя обо!качениям упр. 6.3" 34(Ь), положим, что Я (ти) = 2 ~ !'(1-/с/ти)" и Тч(из) = 1/(е "/ш — 1). Получаем 5„(тп) = Т (ти) + О(е "/"'и/тиз) и 2фче! = х т>, 2 ~/Я (2') = т + О(и з), где т„= 2 >, 2 2'Т„(2'). Из того, что тч.~! < т, а 4тз„— т„= 1/(е" — 1) положительное, ио малое число, следует т„= 6(и 2). Более подробную инфармацию МОЖНО ПачУЧнтйч ЕСЛИ Заннеатй Отсюда следует что /(х) — сумма вычетов,— и. х '/(2а ы — 1) при Из < О, т е. 1+ х 18 х+ -'х + хР()бх) — 1х2+ -"хз — йгхс + ., где функция 2гг т-а пи2япсе 1и 2 л зсиЬ(2исяс/1и 2) есть периодическая функция, абсолютные значения которой никогда не превыигают 8 х 10 '2.
(Ввкиу малости функции Р(2) Брепт в своей первой работе не обратил на нее внимания.) Преобразование Меллина функции /(1/х) имеет вид /" ( — з) = я/((1 — 2' ') зси яв) при — 1 < 312 < О, поэтому /(1/х) = — ',. / 1' +,',—,.„'„,х 'ай/(1 — 2' '). Найдем теперь при Кв < — 1 вычеты подынтегральяой функции /(1/х) = !я — ух + . [Эта формула может быть получена и непосредствепио.) Имеем Вг (х) = 1 - /(х), и отсюда следует 1 2 Сг(х) = /(х) — /(1/х) = х 18х+ -х+ хР(18х) — — + (1 — х )ф(х), 2 1+х где ф(х) = 2» „(-1)" хй/(2»а' — 1).
80. Имеем С2(х) = Е! (х) — Е! (1/х) + Е2(х) — Е2(1/х), где Преобразования Меллипа будут иметь вид Вг (в) = а(й)/(2'+' — 1), Ез(з) = — Ь(й)/(2а ы — 1), 21и па Згп Яй где Таким образом, при 0 < х < 1 получаем следуюгцие выражеиия. г"-' Е!(х) = а(0) + а( — 1) х(18х+-') — а'(1)х/1и 2 + хА(18 х) — ) „, а( — lс)(-х)й, й>2 2й-1 Вз(х) = Ь(О) +Ь( — 1)х(18х+2) — Ь (1)х/)и2+ хВ(18х) — ~ „, Ь( — Ь)( — х), й>2 Е!(1/х) = ~ й>1 В2(1/х) = Х' й>1 а — 2 Ь(2) 1 1 ч-1 1 2»м 1+2'(1+2"х)' л- 2» 1+2! !.2»х ».1>1 »,1>1 »=Е('"'и) =К(' ') „,' Ь(2)=) (2 +1)' '=~~ ( ) !>1 »>е ( — х) нй 2»»1 — 1 1 * — Ь(Ь) — — —:+ Р (1 х) 2 2"+' — 1 1и 2 А(1) = — ~ ~3! / гяг 1п 2 л-г \, э!пЦ2тяг/!и 2) йг В(!) = ~ В(' 1 ч- / 2ггг !п2 х '1 яп1г(2гпкг/!п2) Рь(!) Я 1 г / 2яг' !п2 л \,в!и!г(2тяг/!п2) а( — 1+ 2тгп/!и 2) е 5(-1+ 2тггг/!п2) е ( )-™ й — 1 — 2тггг/!и 21 / е — шм™ )г — 1 34.
Бригитта Валле (Впб!!ге ла!!бе) с помощью приближения, существенно отличающегося от приближения, использованного Брентом, предложила изящный и строгий аначиз алгоритма В, который опубликован в журнале А!8опййписа 22 (1998), ббО-б85. Действительно, ее методы доказательства существенно отличаются от известных до сих пор методов предсказания поведения алгоритма В наподобие эвристических моделей Брента. Таким образом, впервые была строго решена задача анализа бинарного алгоритма нахождения наибольшего общего делителя, которая до сих пор доставляла математикам массу хлопот. 35.
По индукции при т >п длина равна т+ (и/2) + 1 — [т ми = Ц. Однако из результата упр. 37 следует, что алгоритм не может выполняться столь медленно. 36. Пусть а„= (2" — ( — 1)")/3; тогда ао, аг, аг, ... = О, 1, 1, 3, 5, 11, 21, (В двоичном представлении этой последовательности чисел содержится интересный набор нулей и единиц. Обратите внимание на то, что о„= а г + 2а г и а + аьчг = 2".) Положим. чта и = 2'"+' — а„+г, и = а„чг при гп > и.
При пл = и > О положим и = шах(алчг,2а +г) и и = о +з — и, Еще адин пример для случая, когда т = и > О, имеет вид и = 2юы — 2> и = 2"+' — 1. При таком выборе требуется выполнить больше сдвигов, что дает В = 1, С = и+ 1, Р = 2п, Е = и. Это наихудший с точки зрения времени выполнения случай для алгоритма В. 37. (Решение предложено Дж. О. Шэллитам (Ю. О. БЬа!Й).) Это одна из тех задач, в которых для того, чтобы доказать то, что требуется, необходнлго показать больше того, чта требуется.
Пусть Я(и, и) — число шагов, на которых осуществляется операция вычитания, выполненных алгоритмом В над входными величинами и и щ Докажем, что Я(и, с) < !8(и+ и). Отсюда следует что Я(и и) < (!8(и+ с)) < (!82 шах(и и)) = 1+ (!8 шах(и иЦ па построению. Заметим, чта Я(и, и) = 5(с, и). Если и четно, та Я(и, и) = Я(и/2. и). Следовательно, можно положить, что и н а нечетны. Можно также положить, что и > с, поскольку Я(и и) = 1. Тогда по индукции 5(и и) = 1+5((и-и)/2 и) < 1+!8((и-и)/2+и) = !8(и+и). А это означает, что наименьшей парой чисел, требующей и шагов вычитаний, будет и — 2л — +1 с — 2 -г 38, При формировании матрицы А (размера 2 х 2) целых чисел наподобие А(") = ("„,~), таких, что ш — размер машинного слова, следим эа наиболее значимыми и наименее значимыми словами операндов (наиболее значимые используются для обозначения знака Г, а наименее значимые — для определения общего числа сдвигов вправо).
где и' н иг меньше и и ш (Вместо того чтобы разделить моделируемые нечетные операнды на 2, умналагем четные операнды на 2 до тех пор„пока не вычишгим число, кратное ш, в результате выполнения точно !8ш сдвигов ) Проведенные эксперименты показали, что хотя бы на одном компьютере этот алгоритм выполняетсн в четыре раза быстрее алгоритма Е. При использовании подобного алгоритма в уп р. 40 отпадает необходимость в наиболее значимых словах. Алгоритмы, возможно, более быстрые описаны в работах 3, Богепьап, в'.
А)бог1Иипь 16 (1994), 110-144; БЬа!!!З апб Багепьоп, Лес!иге Негев 1п Сотр. Бсб 677 (1994), 169 — 183. 39. (Решение предложено Майклом Пенкам (Мссбае! Репй).) Х1. [Найти степень 2.] То же, что на шаге В1. Х2. (Начальная установка) Присвоить (ис, иг, из) с — (1,0, и) и (ам аз,аз) с — (и, 1-и,а). Если число и нечетна, присвоить (!с,гг, зз) с — (О, -1, -а) и перейти к шагу Х4. В противном случае присвоить (эм Зг, Зз) +- (1, О, и). хз. (Выполнить половинное деление гз ] если зс и гг четны, присвоить (гг, зг,гз) <— (зс,гз,гз)/2; иначе — присвоить (гс,зг,гз) с — (гс + а,!г — и,эз)/2 (В последнем случае гг + а и гг — и будут оба четными.) Х4.
(гз четнау] Если гз четно, вернуться к шагу ХЗ. Х5. [Переустановить снах(из, ез).] Если гз положительна, присвоить (иг, иг, из) +- (!с, !г, гз); иначе — присвоить (ис, иг, аз) Ф- (а — гм — и — 1г, -гз). Хб. [Вычесть.] Присвоить (гг,!г,гз) с- (им из,из) — (ас,аг,аз). Затем, если гг < О, присвоить (Зг, гг) с — (!с+с, гг-и). Если!в ЭЬ О, вернуться к шагу ХЗ, В противном случае закончить выполнение алгоритма с результатом, равнылс (иы иг, из 2").
Ясно, что взаимосвязи в (16) сохраняются; кроме того. после каждого иэ шагов Х2-Хб 0 < ис, аг,гг < а, 0 > из, аз, гг > -и, 0 < из < и, О < из < и. Если после спага Х2 число и четно, та можно упростить шаг ХЗ, так как оба числа гс и !г четны тогда и талька тогда, когда четка гг. Точно так, если а нечетно, оба числа Зс и Зг четны тогда и только тогда, когда четно зм Значит, как и в алгоритме Х, вычисления, связанные с получением чисел иг, аг и гг, выполняемые для нечетных чисел и после шага Х2, можно пропустить. Это условие зачастую известна наперед (т. е. если и четно, а вычисляется и ' по модулю а).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
