Главная Промышленная автоматика.

В строке 4 A=[a(fti. . .al=\ D/2-i J. Далее, так что из (8.6) вытекает

2*-1

Поэтому

> 2"*-! -2*+1-2*. D

2к-1

где 0<S<2*+4-2*. Так как P>2*-S то прибавление к LD/2*-i J числа, не превосходящего 6, дает число, удовлетворяющее предположению индукции для k. Поскольку именно это и делается в строках 5-7, то шаг индукции выполнен. □

Теорема 8.2. Существует такая постоянная с, что R{n) <сЛ1 (п).

Доказательство. Достаточно показать, что алгоритм 8.1 тратит Об {М (п)) времени. На строку 2 уходит R {k/2) битовых операций. Строка 3 состоит из возведения в квадрат и умножения, что требует соответственно Л1 (Л/2-1-1) и M(k+2) времени, а также вычитания, расходующего Об (k) времени. Заметим, что умножение на степени числа 2 не тратит битовых операций; мы считаем, что разряды сомножителей просто занимают новые положения, т. е. они будто бы сдвигаются. В силу нашего предположения о М справедливо неравенство М{к/2+\)Ч2М{к+2). Кроме того, М {k+2)-М {k) = =Оъ{к) (см., например, разд. 2.6) и, значит, сложность строки 3 ограничена величиной */2M{k)+ck для некоторой постоянной с. Сложность строки 4 равна, очевидно. Об (Л).

Может показаться, что цикл в строках 5-7 требует три умножения, но можно проделать необходимые вычисления за одно умножение [flofli. • -flft] * IpiPi-. .Pft] и несколько сложений и вычитаний не более чем 2/-разрядных двоичных целых чисел. Поэтому сложность строк 5-7 ограничена величиной M{k)+ck для некоторой постоянной с*. Объединяя все эти сложности, заключаем, что

R(k)R(±)+M(k) + c,k

(8.7)

для некоторой постоянной Ci.

Мы утверждаем, что найдется такая постоянная с, что R{k) cM(k). Можно выбрать с так, чтобы было cR {1)/М (I) и с> >5-f 2ci. Докажем наше утверждение индукцией по k. Базис, т. е. случай k=l, очевиден. Шаг индукции получается в силу (8.7), по-



скольку

/?(Л)<сЛ1()+л1(Л) + сЛ (8.8)

Так как М {k/2)/J\ii (к) в силу нашего предположения о М, я оценка kM (k) очевидна, можно переписать (8.8) в виде

/?(*)< (y + + Ci)a1 (ft). (8.9)

Поскольку c>5+2ci, то из (8.9) следует, что R{k)cM{k). О

Ясно, что алгоритмом 8.2 можно вычислить 1/Р с п значащими двоичными цифрами, если Р имеет столько же цифр, при этом неважно, где расположена запятая. Например, если /2<P<l и Р имеет п битов, можно очевидным образом изменить масштаб и представить 1/Р как 1 и последующие битов дробной части.

Теперь покажем, что время S (п), необходимое для возведения в квадрат целого числа размера п, не превышает по порядку времени R (п) обращения целого числа размера п. Метод основан на тождестве

Р» = -р-Ц--Р. (8.10)

Приведем алгоритм, использующий (8.10) с подходящим изменением масштаба.

Алгоритм 8.2. Возведение в квадрат с помощью обратных величин

Вход, п-разрядное целое число Р в двоичной записи.

Выход. Двоичная запись числа Р?.

Метод.

1. Применяем алгоритм 8.1 для вычисления А=[ 2*"-ЧР Для этого добавляем 2п нулей к Р, применяем процедуру ОБРАТНОЕ 1) для вычисления 2»»-VP2*" J и сдвигаем результат.

2. Аналогично вычисляем В= 2«»-V(P-fl)J.

3. Полагаем С=А-В. Заметим, что С=2*"-Ч (Р?+Р)+Т, где \Т\ <1. Слагаемое Т возникает из-за того, что отбрасывание знаков при вычислении А п В может привести к ошибке вплоть до 1. Так как 2«-«<P2-fP<2«", то 2«+1>С2»«-1.

4. Вычисляем D= 2««-VCJ-Р.

5. Пусть Q - четыре последние бита числа Р. Увеличиваем или уменьшаем D на минимйльно возможную величину так, чтобы последние четыре бита результата совпали с последними четырьмя битами в Q?. □

) Процедура ОБРАТНОЕ определена в алгоритме 8.1 только для целых чисел, длина которых равна степени числа 2. Обобщение на любые целые числа должно быть очевидным: добавляем нули и, если надо, изменяем масштаб.



Теорема 8.3. Алгоритм 8.2 вычисляет Р?.

Доказательство. В силу способа, которым отбрасываются цифры на шагах 1 и 2, можно ручаться лишь за то, что

С = + Т, гдеТ<1.

Так как 2-C2+ и ошибка в С заключена между -1 и 1, то связанная с ней ошибка в 2*"~ЧС не превосходит

24П-1 2*"-

Так как С*-С2*"~*, то эта ошибка не превосходит 4. Отбрасывание цифр в строке 4 может увеличить ошибку до 5. Таким образом, \Р-D5. Следовательно, вычисление последних четырех цифр в Р? на шаге 5 гарантирует, что D корректируется так, что становится равным Pi. О

Пример 8.2. Путь п=4 и Р=[П01]. Тогда

А= 12Щт1] \ =[100111011000]

в= L2«/[mo]J =[100100100100].

Далее,

С = Л -В = [10110100].

Тогда

D = [2»/C]-P = [10110110]-[1101] = [10101001].

Таким образом, D=169 - квадрат числа 13, и на шаге 5 не нужна никакая коррекция. □

Теорема 8.4. Найдется такая постоянная с, что S (n)cR (п).

Доказательство. В алгоритме 8.2 трижды вычисляются обратные к числам, задаваемым цепочками длины не более Зп. Вычитания на шагах 3 и 4 требуют Об (п) времени, а на шаге 5 выполняется работа фиксированного объема, не зависящего от/г. Следовательно,

S{n)3R{3n) + Cin (8.11)

для некоторой постоянной Ci.

Таким образом, S {n)27R (n)-fCi/i. Так как R {п)п, то, полагая c=27-fci, получаем нужное неравенство. □

Теорема 8.5. М(п), R{n), D(n) и S(n) равны с точностью до постоянных множителей.

Доказательство. Мы уже показали, что R{n)CiM(п) и S (n)C2R (п) для некоторых постоянных Ci и t,. Легко вывести





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 [102] 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0022