Динамо-машины  Обратные коды 

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 [ 175 ] 176 177 178 179 180 181 182 183 184 185 186 187 188 189

случае выполняется без дополнительных обращений к запоминающему устройству и поэтому быстрее, чем по подпрограмме. Промежуточные результаты хранятся в регистрах арифметического устройства, а последовательность операций задается схемой управления арифметического устройства.

Наиболее известны итеративные формулы, позволяющие вычислить обратную величину от делителя; процесс деления завершается умножением обратной величины делителя на делимое, в результате чего находится частное.

Обозначим, как обычно, делитель через С. Предположим, что имеется некоторое число xi, представляющее обратную величину делителя 1/С с относительной погрешностью 6/,

Отсюда легко найти искомую величину 1/С:

1 1

С 1-6; ~ 1-(1-СХ;)

Если полагать, что погрешность бг достаточно мала, то хг (1 + 6,) = X, (2 - Схг).

Примем эту величину за следующее приближение к искомой величине 1/С:

х,ч1 = хД2 -Сх/). (*)

Это и есть основная формула итерации.

Нетрудно вычислить относительную погрешность, с которой Xi+i выражает величину 1/С. Если

Xi = -(l~6i),

.41 = (1 - 6,) [2 - С- (1 - 6,)] = (1 - б?)-Таким образом, если относительная погрешность t-ro при-

ближения есть bi, то относительная погрешность (/ + 1)-го приближения будет 6i-1-1 = (i + 2)-го - бг+2 = б* и т. д.

Ясно, что условием сходимости иттераций является такой выбор начального приближения х, для которого относительная ошибка бо по абсолютной величине меньше единицы:

6о = 1-Схо lt;1.

откуда

О lt; Схо lt; 2

0 lt;Xo lt;2/C.

Если С - нормализованное положительное двоичное число, 1/2 С 1, то требуется

О lt; Хо lt; 2.

Например, можно принять Xq = 1 для всех чисел С из указанного диапазона. Однако при этом потребовалось бы очень много итераций для достижения необходимой точности.

Если 6i достаточно мало по сравнению с единицей, то, грубо говоря, количество верных знаков удваивается при каждой итерации.

В составе оборудования арифметического устройства для вьшолнения деления по этому методу нужно иметь таблицу для нахождения начального приближения (Хо), один или, может быть, два дополнительных регистра (для хранения в течение всего процесса деления величины делимого и для хранения промежуточных результатов Cxt и затем 2 - Cxi в каждой итерации), а также, разумеется, соответствующие цепи в схеме управления. Желательно, кроме того, предусмотреть возможность получать результат умножения в дополнительном коде, что позволит в результате умножения С X Xi получать сразу величину 2 - Cxi.

Длительность выполнения деления при этом зависит от точности начального приближения. Если, например, мантиссы нормализованных чисел, с которыми оперирует машина, содержат по 32 двоичных разряда и такова же должна быть точность деления, а первое приближение находится по таблице с 8 верными двоичными знаками, то процесс де-

ления должен включать две итерации; поскольку каждая итерация состоит из двух умножений, а в конце деления требуется еще одно умножение (обратной величины делите-ля на делимое), то всего деление будет выполняться за время 5 умножений.

Поскольку количество оборудования, необходимого для получения начального приближения, растет примерно как kn!, где п - основание системы счисления, k - количество верных знаков в начальном приближении, то иногда выгоднее для ускорения деления использовать более сложные формулы итераций. Например, если вместо приближенного равенства

= /(1+6,)

воспользоваться выражениями

5х,(Ц-6, + 6?) . 1-6.

j-;x,(i+ + 6! + 6?),

то, подставляя б,- = 1 - Cxt, получим вместо итерационной формулы (*) итерационные формулы

х,ч1 = 3 (1 - Cxi) + {CXiY\ (** gt;

Xi+x = xi [6 (4 - CXi) + {Cxtf (4 - CXi) - 20]. (***):

Формулу (***) можно получить также из (*), подставляя в выражение Xi+2 через xi+i выражение Xi+i через xi и затем заменяя индекс t -Ь 2 на t -Ь 1: из

л:/+2 = Xii (2 - Cx;+i)

xi+i -= Xi{2~Cxi)

получим

= Xi (2 - Cxi) [2 - Cxi (2 - Cxi)\, откуда и следует (***),