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

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

Учитьшая, что Ci = 2 С, перепишем это равенство в виде

В = С{ао - 2-Ч - 2-Ч -. .. -2- а 0 -fB +i.

Отсюда видно, что единственное условие, которое следует соблюсти при выборе очередных цифр частного, состоит в том, чтобы остатки Bi от шага к шагу (с ростом номера i) убывали: если последний остаток окажется достаточно малой величиной, то двоичное число А, записанное цифрами laquo;0. laquo;1. gt; (Л = Go + 2-ici + . . . + 2- с ),будег с достаточной степенью точности представлять частное от

доения В : С (так как А= ---)- того чтобы

погрешность частного не превышала единицы младшего разряда, необходимо, чтобы выполнялось условие

-~ lt;2- или \Bm+i\ lt;2--C =Ст.

Рассмотрим с этой точки зрения первый из методов двоичного деления, изложенный в 5.1.1. Возможными цифрами частного на каждом шаге являются О и 1. Если бы на некотором шаге оказалось, что Bi-x gt;2Cj i, то, выбрав максимально возможную цифру частного - единицу (с тем, чтобы следующий остаток был возможно меньше), мы все равно получили бы

Bi = В, 1 - 1 С, 1 gt; С, 1 = 2Сл

Такое же положекиесохранялосьбы и для всех последующих шагов, так что в конечном итоге оказалось бы, что

Следовательно, получить частное с заданной точностью не удалось бы. Точно так же деление не дало бы правильного результата, если бы на каком-либо шаге оказалось, что Вг 1 lt;С 0: если бы мы дальше выбрали в качестве цифры частного aii = 1, то следующий остаток снова получился бы отрицательньш и возрос бы по абсолютной величине, если бы в качестве всех дальнейших цифр частного выбирались нули, то величина остатка не убывала бы. Таким образом, выбирая каждый раз очередную цифру частного а,-, мы должны заботиться о том, чтобы следующий остаток

В(4-1 = Bi - aiCi был заключен в пределах

тогда в конце окажется, как это и требуется, что iBm+i I

Поскольку исходные числа нормализованы, т.е.

1 lt;В lt;1 и 4 lt;С lt;1.

то на первом шаге (5 = В и Со = С) указанное условие выполняется. Чтобы оно выполнялось и дальше, цифры частного на каждом шаге должны выбираться по правилу:

если Bi lt;; С/, то at = О

если Bi gt; d, то а,- = I.

Если Bi = d, то очередную цифру частного можно принять равной либо О, либо 1; в первом случае следующий остаток равен Bj+i = Bi = Q = 2Ctn, и все последующие цифры частного окажутся единицами; во втором случае следующий остаток Bi+i получится равным нулю, и все последующие цифры частного будут нулями. (Возможность различно выбирать очередную цифру частного в случае Bi = d отмечалась в 5.1.1 в связи с вопросом о том, как производить сравнение делителя с делимьш - через дополнительные или через обратные коды.)

Приведенное здесь объяснение можно считать общим обоснованием первого метода деления, изложенного в 5.1.1.

Теперь рассмотрим с этой точки зрения приведенный в 5.1.1 второй метод вьшолнения деления.

Возможными цифрами частного в нем являются фактически неОи 1, а -1и +1. Этому соответствует то обстоятельство, что на каждом шаге очередной остаток вычисляется либо добавлением, либо вычитанием величины С,- из предыдущего остатка (Bj+i = Bi - CiC,-, где щ = -1 или at = + 1). Когда в 5.1.1 мы предполагали записывать в регистр частного цифры О или 1, то при этом по ходу дела в сущности производилось преобразование частного из формы записи цифрами -1, +1 в форму записи цифрами О, 1.

*) Более строгое обоснование этого положения имеется на стр. 506-507.

Приведенное правило деления включало это преобразование. Когда, например, в соответствии с указанным правилом на первом шаге, производится вычитание делителя из делимого, то тем самым уже предопределено, что в форме записи цифрами -1, 1 старшая цифра частного есть 1. Од-, нако эту цифру мы не спешили вносить в регистр частного; вместо этого мы дожидались получения следующей цифры. Если первый остаток получался положительным, то при .атом на следующем шаге вновь выполняется вычитание, т. е. следующий разряд частного в форме с цифрами - I, 1 вновь содержит 1; тогда и в форме записи цифрами О, 1 первый разряд содержит единицу, и эту единицу уже можно заносить в регистр частного. Если же первый остаток отрицателен, то в форме записи цифрами -1, 1 следующий разряд частного содержит -1 (так как на втором шаге производится добавление сдвинутого делителя), а при преобразовании в форму записи цифрами 0,1 в первом разряде

окажется О (потому что (-- 1) -1 + (-1) -- 4- . - . = (0) 1 -Ь

+ (Оу . или, иначе, 1.1... = 0.1...). Точно так

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

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

- 2C, lt;B, lt;--2C (oнo аналогично условию О Bf 2Cj для первого метода). На первом шаге {Вд = В, Cq= С, где В и С -делимое и делитель) это условие выполняется. Чтобы оно выполнялось и дальше, цифры частного на каждом шаге должны выбираться по правилу:

если Вг lt;0, то а,= -1; если В/ gt;0, то а;=--1.