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

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

Для дальнейшего важно ещ,е и следующее обстоятельство. Комбинацию цифр множителя 10 мы расшифровали так, что суммирование производилось во втором из двух ближайших циклов умножения, а в следующую пару разрядов единица не передавалась. Вместо этого можно было, бы во втором из двух ближайших циклов умножения выполнить вычитание и передать единицу в следующую пару разрядов, т. е. представить комбинацию 10 в виде ..10= = 1..10. Пока в схему управления поступают только пары разрядов множителя, такое изменение никакой роли не играет. Но если бы при расшифровке данной пары разрядов было сразу известно, какова комбинация цифр в следующей паре разрядов, для комбинации laquo;10 raquo;можнО было бы подбирать каждый раз свой, наиболее выгодный способ расшифровки. Например, если в следующей паре разрядов имеется комбинация laquo;00 raquo;, то из данной пары разрядов в нее лучше не переносить единицу, если же в ней имеется комбинация laquo;И raquo;, то лучше перенести.

Это дает основание надеяться, что при увеличении количества разрядов, расшифровываемых единовременно можно получить дальнейшее сокращение среднего количества тактов суммирования-вычитания.

Однако непосредственным подсчетом (аналогичным проведенному выше для пар разрядов) нетрудно убедиться, что при группировке разрядов множителя в тройки получили бы в среднем тоже 0,375 такта суммирования-вычитания на1 разряд множителя, пригруппировке по четверкам- 0,359 такта, пригруппировке по пятеркам - 0,356 такта ит.д. С увеличениемколичества разрядов в группе среднее Y количествотактов суммирования-вычитания, приходящееся на 1 разряд множителя, убьшает очень медленно; в 4.2.4 мы покажем, что оно в пределе стремится к 0,333... Однако тот жерезультат можетбыть достигнут более простым путем - методом последовательного преобразования множителя, о котором говорится ниже. Группировать разряды более чем по два не имеет, вероятно, смысла.

Теперь рассмотрим применение метода группировки разрядов множителя в тех случаях, когда умножение начинается от его старших разрядов. Вернувшись несколько назад, разрешим при группировке разрядов по парам воз-

можность двоякого представления комбинации 10 (в виде 10 или 1..10). Тогда правило расшифровки пар разрядов, которым мы пользовались выше, для умножения от младших разрядов, можно сформулировать следующим образом:*)

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

- есЛи старшая цифра соседней справа пары разрядов , есть единица, то добавить к имеющейся в данной

паре разрядов комбинации величину ..01.

Тождественность предлагаемых преобразований множителя очевидна: величина 1..00 для соседней справа пары разрядов равна величине ..01 для данной пары. В то же время, как нетрудно проверить простым перебором всех комбинаций, в результате указанного преобразования в любой паре циклов умножения может быть не более одного такта сложения или вычитания, а в среднем на каждый разряд множителя придется 0,375 тактов сложения-вычитания. В схеме управления, конечно, добавление величины ..01 или вычитание 1..00 фактически не производится: это преобразование выполняется дешифратором, в который должны поступать теперь не 2 разряда множителя, как прежде, а три: кроме данной пары разрядов, необходима также цифра старшего разряда следующей пары. Но ЭТО ведет не к усложнению, а, возможно, даже к некоторому упрощению схемы управления, так как отпадает необходимость в формировании, запоминании и расшифровке цифры, переносимой из предыдущей пары разрядов.

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

*) Заимствовано из работы КухарчукаА. Т. и Процен-ко Н. М., laquo;Методы ускоренного умножения со старших разрядов множителя raquo; (сб. laquo;Труды конференции laquo;Новые разработки по вычислительной математике и вычислительной технике raquo; raquo;, Киев, 1960), где приводимая формулировка предлагается для умножения от старших разрядов.

Разбивка разрядов по парам в любом случае должна быть такой, чтобы в старшую пару входили несуществующий разряд целых и первый (старший) из значащих разрядов числа. Поскольку разряд целых содержит всегда цифру laquo;О raquo;, невозможна такая комбинация, при которой из старшей пары разрядов вычиталась бы величина 1..00 (допускать этого нельзя, так как вычитание из старшей пары разрядов величины 1..00 не могло бы быгь скомпенсировано добавлением величины . . 01 к разрядам, находящимся слева от нее,- умножение на эти разряды уже не выполняется).

Может оказаться, что при преобразовании старшей пары разрядов появляется единица в ее левом разряде, т. е. в разряде целых. Применительно, скажем, к первому варианту вьшолнения умножения (см. 4.1.2) это указывает на необходимость добавить множимое к сумме частичных произведений после последнего сдвига вправо суммы частичных произведений; применительно, например, к четвертому варианту выполнения] умножения такая единица указывает на необходимость вьшолнения суммирования до первого сдвига множимого вправо.

Пример. Пусть, как и в примере на стр. 367, множитель первоначально имеет вид

(0). 101111100110011101(0).

Действуя описанным способом, получим:

(группировка разрядов по парам)

01 01 И И 00 И 00 И 10 10

(преобразование пар разрядов в любом порядке)

+0 +1 +1 +0 +i +0 +1 +1 +1

-О 0 -1..00 -1..00 -О -1..00 -О -1..00 -1..00 -1..00

(преобразованный множитель)

0.1 10 00 01 01 Й 01 00 оТ 1о

Здесь мы получили 8 положительных и отрицательных единиц в преобразованном множителе вместо 12 единиц в исходном и 9 единиц в примере на стр. 367. Однако последнее различие носит случайный характер: при других