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

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

Вычитание делителя

1-й остаток

удвоение 1-го остатка добавление делителя

2-й остаток

удвоение 2-го остатка \j вычитание делителя

3-й остаток

удвоение 3-го остатка добавление делителя

4-й остаток

удвоение 4-го остатка вычитание делителя

5-й остаток

удвоение 5-го остатка добавление делителя

6-й остаток

.01111 * ~ .11000

(- .01001)

, (-.10010) + .11000

( + .0.0110)

(-f .01100) ~ .11000

(- .01100)

,(-.11000) + .11000

( + .00000)

(+ .00000) ~ .11000

( - .11000)

1.10000) 11000

(-.11000)

11000

0.10100.

(-1.10000)

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

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

5.1.2. Логический метод ускорения двоичного деления.

Один из немногих известных логических методов ускорения деления *) основывается на следующих соображениях.

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

Точно так же в случае, когда очередной, i-й остаток Bi очень велик (близок к числу С,-, находящемуся в регистре делителя), так что разность Bi - С,- содержит перед первой значащей цифрой на k нулей больше, чем число С,-, по крайней мере k очередных цифр частного будут единицами. При этом (i + Щ-й остаток можно получить, сдвинув разность на k разрядов влево (или делитель на k разрядов вправо) и добавив делитель к разности. Действительно, если бы мы, например, в каждом цикле деления сдвигали остаток влево, то (i -\- остаток (после получения k единиц в частном) был бы равен

2(...(2(2В,-С)-С). ..)-С =

= 2Bi - - 2 -2 С - . . . -2С - С.

Сдвинув на k разрядов влево разность Bf - С и добавив к ней делитель С, получим ту же величину:

2\Bi - С) + С = 2Bi - ( - 1 )С =

= 2 lt;В,-2 -С -2-2С- . . . 2С-С.

Следовательно, и в этом случае k очередных сдвигов остатка влево или делителя вправо можно выполнять без пропуска тактов для сравнений или сложений-вычитаний.

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

*) См. К л я м к о Э. И., М о и а X о в Г. Д., Метод ускоренного двоичного деления в цифровых вычислительных машинах, laquo;Приборостроение raquo;, 1957, № 2.

а деление выполняется по первому варианту (т. е. со сдвигами остатков влево, а не делителя вправо). Можно подсчитать, что применение такого метода сократило бы количество тактов сравнения или сложения-вычитания примерно на 40%.

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

Для простоты предположим, что речь идет о делении нормализованных чисел и что в процессе деления производятся сдвиги делителя вправо, а не сдвиги остатков влево. Ограничения эти вообще несущественны. Обозначим делимое и делитель соответственно через В и С, остатки - через Bi (1= О, 1, 2, 3, . . . ; Во = В), а величины, получающиеся при последовательных сдвигах делителя вправо - через Ci (при этом Q = С, Q = 2 ! С,..., Q =;= 2 С,...).

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

В,+1 = Вг-аА-

Определив каким-либо способом цифры частного laquo;о, а, . . . мы в конечном итоге получим

Вт+1 - В,п GmCifi -

~ Bin-l Clm-lCm-~l ClmCm ~

= В - ооСо ~ ajCi -... - CmC

*) Впервые, вероятно, эта идея высказана М. Надлером - см. Acta Techn., 1956, 1, № 6, стр. 464-478 (Чехословакия). Она разрабатывалась также в нескольких работах автора настоящей книги (напр., laquo;Об одном методе дюичного деления raquo;, сб. laquo;Труды конференции laquo;Новые разработки по вычислительной математике и вычислительной технике raquo;, Киев, I960). Сходные идеи, но относящиеся к системам счисления с более высокими основаниями, излагались также в докладе проф. Роберт-сона Дж. И. (США), сделанном в Москве в 1958 г. -