1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 63
Текст из файла (страница 63)
а,1=[011010101]. В строке 6 находим, что [О!1010101]е[!001100!] (т. е. 213Ф153 в десятичной записи) равно 32589, тогда иак 2'»=32768, Поэтому цикл в строках 5 — 7 добавляет 1 к 213, что дает 214, или 1011010110] в двоичной записи. С] Теорема 8.1. Алгоритм 8.1 находит «юкос число [а» а»... а„1, что [а»аэ... аэ]Ф[р,рэ...
рэ! 2'»"э — 5 и Ы 5([рэ р,...рэ]. Д о к а з а т е л ь с т в о. Доказательство проводится индукцией по й. Базис, т. е. случай А=1, тривиален в силу строки 1. Для проведения шага индукции положим С=[с»сэ...сэж], Р,=1р,р,... ...рэж] И Р»=[рц»+~ рм»+а ..р»1. ТОГда Р=1рэр» .р»1=Р»2М»+Р» По предположению индукции СР,=2" ' — 5, где Оч 5(РИ В силу строки 30=Ы» э(».. л!»А] определяется равенством Π— С2 »1» С (Р»2»!»+Р,), (8.3) Так как р,=1, то Р~)2А1»-' и, значит, С(2АI». Отсюда следует, что 0(2»», и потому для представления 0 достаточно 2й битов. Рассмотрим произведение РР (Р»2»~»+Р»)О, равное в силу (8.3! РЭ = СР,.2" +СР,2™» — (СР,2»" + СР,]'. (8.4) Подставив 2"-' — 5 вместо СР, в (8,4) и сделав некоторые алгебраические упрощения, получаем Р0 2»э-» (52А1» СР )» (8.5) Разделив (8.5) на 2" э видим, что 2'" '= — +Т, (8.6) 2»"» где Т=(52»!' — СР»)»2 — э~ — 'э.
По предположению индукции и в силу неравенства Р»(2»~э имеем 5(2»!». Так как С(2»!» и Р,(2эlэ, то 0КТ(2»+э. в.я эмножаниа н даланив палых чисел В строке 4 А=[а»аь ..а»1=( О/2»-»3. Далее, ~в~ Р~в так что из (8.6) вьггекает 2»»> — '~Р~ — ~> — — Р=2» ' — Т вЂ” Р> 2»-» 1 2»-11 2»-» > 2*» ' — 2»+' — 2".
Р ~ — ~ = 2'» ' — Ю', где Оч=З'(2»+'+2». Так как Р>2» ', то прибавление к ) О/2»-' ~ числа, не превосходящего 6, дает число, удовлетворяющее предположению индукции для й. Поскольку именно это и делается в строках 5 — 7, то шаг индукции выполнен. С) Теорема 8.2, Существует такая постоянная с, что /г' (и)( ~сМ (и). Д о к а з а т е л ь с т в о.
Достаточно показать, что алгоритм 8.! тратит Оа(М (и)) времени, На строку 2 уходит Я (й/2) битовых операций. Строка 3 состоит из возведения в квадрат и умножения, что требует соответственно М(й/2+1) и М (й+2) времени, а также вычитания, расходующего Оз(/») времени. Заметим, что умножение на степени числа 2 не тратит битовых операций; мы считаем, что разряды сомножителей просто занимают новые положения, т.
е. они будто бы сдвигаются. В силу нашего предположения о М справедливо неравенство М(й/2+1)~(»/,М(й+2). Кроме того, М(й+2) — М(й)= =Оэ(й) (см., например, равд. 2.6) и, значит, сложность строки 3 ограничена величиной '/,М(й)+с'й для некоторой постоянной с'. Сложность строки 4 равна, очевидно, Ов(я). Может показаться, что цикл в строках 5 — 7 требует три умножения, но можно проделать необходимые вычисления за одно умножение (а,а,...а»)»(р,р,...р»1 и несколько сложений и вычитаний не более чем 2й-разрядных двоичных целых чисел. Поэтому сложность строк 5 — 7 ограничена величиной М(Й)+с'Й для неко. торой постоянной с'.
Объединяя все эти сложности, заключаем, что К(й)-Ж Я+ ~ М Я+с,й (87) для некоторой постоянной с,. Мы утверждаем, что найдется такая постоянная с, что /т(я) = (сМ(й). Можно выбрать с так, чтобы было с>Я(1)/М(1) н с> >5+2с,. Докажем наше утверждение индукцией по й. Базис, т. е. случай й=1, очевиден. Шаг индукции получается в силу (8.7), по- 3»г гл. а. двифыатичвскив опвплции скольку К(й)=асм й)+ТМ(й)+ей, (8.8) Так как М(й/2~ЧеМ(й) в силу нашего предположения о М, а оценка й(М(й) очевидна, можно переписать (8.8) в виде м (й) ~ ( о + ч + сз) М (й). (8.9) Поскольку с)5+2сь то из (8.9) следует, что Я(й)(сМ(й).
П Ясно, что алгоритмом 8.2 можно вычислить ПР с и значащими двоичными цифрами, если Р имеет столько же цифр, при этом неважно, где расположена запятая. Например, если '/з(Р(1 и Р имеет и битов, можно очевидным образом изменить масштаб и представить 1!Р как 1 и последующие л — 1 битов дробной части. Теперь покажем, что время В(л), необходимое для возведения в квадрат целого числа размера л, не превышает по порядку времени К (л) обращения целого числа размера л.
Метод основан на тождестве Р' = — Р. (8.10) Р Р+1 Приведем алгоритм, использующий (8.10) с подходящим изменением масштаба. ') Процедура ОБРАТНОЕ определена в алгорнтме ЗЛ только для целых чисел, длнна которых равна степени числа 2. Обобшенне на любые целые числа должно быть очевндным: добавляем нули н, если надо, изменяем масштаб. Заа Алгоритм 8.2. Возведение в квадрат с помощью обратных величин Вход. и-разрядное целое число Р в двоичной записи. Выход. Двоичная запись числа РУ. Метод.
1. Применяем алгоритм 8.1 для вычислении А=~ 2ьч ЧР ~. Для этого добавляем 2а нулей к Р, применяем процедуру ОБРАТНОЕ ') для вычисления1 2ая ЧР2зя ) и сдвигаем результат. 2. Аналогично вычисляем В=( 2'"-Ч(Р+1) 1'. 3. Полагаем С=А — В. Заметим, что С=2'"-Ч(Рв+Р)+Т, где 1Т) (1. Слагаемое Т возникает из-за того, что отбрасывание знаков при вычислении А и В может привести к ошибке вплоть до 1. Тая как 2ав з(.Ра+Р(2зв то 2ев+')С -2'" ' 4. Вычисляем Р=1 2а"-ЧС~ — Р. 5.
Пусть Я вЂ” четыре последние бита числа Р. Увеличиваем или уменьшаем Р на минимально возможную величину так, чтобы последние четыре бита результата совпали с последними четырьмя битами в ссз. ьз в.е имножвнив и деление целых чисел В $2м)[1110] ] [100100100100] С = А — В = [10110100]. Далее, Тогда О=[2 7С] — Р =[101101(0] †[1)]=[10101001]. Таким образом, О=169 — квадрат числа 13, и на шаге 5 не нужна никакая коррекция.
П Теорема 8.4. Найдется такая постоянная с, что Я (п)(сй (и). До к а з а тел ь с т в о. В алгоритме 8.2 трижды вычисляются обратные к числам, задаваемым цепочками длины не более Зп. Вычитания на шагах 3 и 4 требуют Ов (и) времени,а на шаге 5 выполняется работа фиксированного объема, не зависящего от и. Следовательно, В(п) (~3)с (Зп)+с,п (8.11) для некоторой постоянной с,. Таким образом, В (п)(27К (п)+сьп.
Так как Й (и)'= и, то, полагая с=27+с„получаем нужное неравенство. П Теорема 8,5. М(п), Я(п), 0(п) и З(п) равны с точностью до постоянных множителей. Д о к а з а т е л ь с т в о. Мы уже показали, что )с (п)(с,М (и) и З(п)(сЯ(п) для некоторых постоянных с, и с,. Легко вывести Теорема 8.3. Алгоритм 8.2 вычисляет Рз. Д о к а з а т ел ь с т в о, В силу способа, которым отбрасываются цифры на шагах 1 и 2, можно ручаться лишь за то, что С = рт+ — + Т, где ~ Т ( ( 1. Так как 2'"-~(С(2'"+1 и ошибка в С заключена между — 1 и 1, то связанная с ней ошибка в 24" НС не превосходит ! — "-'— '-'!=!':-'! Так как С' — С ь2т-ь, то зта ошибка не превосходит 4. Отбрасывание цифр в строке 4 может увеличить ошибку до 5.
Таким образом, (Р' — Р~(5. Следовательно, вычисление последних четырех цифр в Рт на шаге 5 гарантирует, что 0 корректируется так, что становится равным РД П Пример 8.2. Путь п=4 и Р=(1101). Тогда А — [ 2мй[1101] ] [100111011000] гл. к лпиомптичнскнн опяплцми неравенство М (п)я-сз5 (п), заметив, что АВ ~ !(А+ В)' — А' — Вз). Таким образом, М, )с н 5 равны с точностью до постоянных множнтелей.
Когда мы обсуждаем деление и-разрядных двоичных чисел, мы фактически подразумеваем деление числа, содержащего до 2п батов, на число, содержащее в точности п битов, причем ответ содержит не более п+1 битов. Очевидно, что )с(и~Р(и), так что М(п)( (с,с,Р (п). Более того, с помощью тождества А/В=Ап(1/В) можно показать, изменяя подходящим образом масштаб, что для некоторой постоянной с Р (и) ( М (2п)+ й (2п)+си. (8.!2) Поскольку Я(2п)(с,М(2п) н, как легко показать, М(2и~4М(п), можно переписать (8.12) в виде Р(п)(4(! +с,) М (п)+сп. (8.13) Так как М (и))и, то в силу (8.13) справедливо неравенство Р (и)«„ (с,М (п), где с.=4+4с,+с. Итак, мы доказали, что все рассматрнваемые функции заключены между дМ(п) н еМ(и) для некоторых положительных постоянных д н е.
П Следствие. Деление 2п-разрядного двоичного целого числа на и- разрядное можно выполнить за время Ов (п !оЕ п 1ой 1ой п). Доказательство. В силу теорем 7.8 н 8.5. П В.З. УМНОЖЕНИЕ И ДЕЛЕНИЕ ПОЛИНОМОВ Вся техника предыдущего раздела переносится на арнфметнческне операции над полнномамн от одной переменной. В этом разделе функции М(п), Р(п), К(и) н 5(и) обозначают времена, требуемые соответственно для умножения, деления, обращения н возведения в квадрат полнномов степени и. Как н раньше, мы предполагаем, что а'М (и))М (аи)~аМ(и) для а- 1 н подобные неравенства справедлнвы н для других функций.
Под "обратным" к полнному р(х) степени и мы понимаем полянам ( х*"/р(х) ~т). Р(и) — этовремя нахождения полннома( з(х)/р(х) ~, где р(х) имеет степень п, а з(х) — степень, не превосходящую 2и. Заметим, что подобно тому, как в предыдущем разделе мы изменяли ') По аналогии с обозначением для пелыз чисел для обозначения частного от деления полиномов употребляется зфункпия диез. Инымн словами, если р(х) ие постоянная, то ! з(х)/р(х) ) — зто единственный полипом о(х), для которого з(х)=р(х)о(х)+г(х) и СТ(г(х))<СТ(р(х)).
в.а. умнОжение и деление полинОмОЕ масштаб целых чисел с помощью степеней числа 2, можно "изменять масштаб" полиномов, умножая и деля их на степени переменной х. Так как результаты настоящего раздела очень похожи на резуль- таты для целых чисел, изложим в деталях только один из них: алгоритм обращения полнномов, аналогичный алгоритму 8.1 для целых чисел. Алгоритмы для полиномов в какой-то мере проще со- ответствующих алгоритмов для целых чисел — в основном благо- даря тому, что в степенных рядах в отличие от целых чисел нет пере- носов. Поэтому в алгоритмах для полиномов не надо корректиро- вать младшие значащие разряды, как это требовалось, например, в строках 5 — 7 алгоритма 8.1. Алгоритм 8.3.
Обращение полиномов Вход. Полином р(х) степени л — 1, где и — степень числа 2 (т. е. р(х) имеет 2' членов, где 1 — некоторое целое число). Выход. Обратный полинам ( хео */р(х) ~. Мел!Од. На рис. 8.2 приведена новая процедура /й-1 ОБРАТНЫЙ ~~ а;х', 1=о где й — степень числа 2 и ай,ФО. Эта процедура вычисляет ~! а;хй Заметим, что при А=1 аргументом будет постоянная а„а ее обратным — другая постоянная 1/а,. Предполагается что каждую операцию над коэффициентами можно выполнить за один шаг, и поэто- /й-1 ргоседпге ОБРАТНЫЙ ( ~~Р ~а,х': 1=0 1. И й=! 1Ьеп ге1нгп 1/а е(ее Ьеи!и / й-1 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
