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

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

в случае Bi = О очередную цифру частного можно выбрать произвольно; приняв, в частности, laquo;г = + 1, получим

Bt+i = Bi - UiCi = - Ci,

в результате чего все последующие цифры будут -1; приняв fli = - 1, получим

Bi+i = Bi - aiCi = + Ci, так что все последующие цифры частного будут равны +1.

Перейдем теперь непосредственно к изложению идеи использования избьггочных цифр частного. Идея эта состоит в том, что для каждого разряда частного допустимыми считаются не две возможные цифры (скажем, О и 1, или -1 и +1), а три или больше различных цифр. При этом мы рассчитьшаем на то, что за счет избыточных возможностей мы получим несколько большую свободу в выборе очередных цифр частного. При наличии всего двух допустимых цифр можно было выбирать любую из них лишь при одном определенном значении остатков {Bi = d для первого метода или Bi = О для второго метода) и не более чем один раз за весь процесс деления; при наличии большего количества допустимых цифр такая возможность встретится чаще.

При рассмотрении логических методов ускорения умножения мы уже встречались с формой записи двоичного числа (множителя), когда для каждого разряда допускалисьне две, а три различные цифры:--!, О, +1 (см. 4.2.2). Преобразование чисел в указанную форму оказьшалось неоднозначным; например, число /а можно представить либо в

виде 0-1 + 1- + 1- (т. е. О.П), либо в виде М -f 0- +

+ (- 1)- (т. е. 1.01), либо в виде 1 1 -f (- 1)- -f 1

(т. е. l.fl). В сущности эта неоднозначность записи и позволит получить некоторую свободу в выборе цифр частного.

Итак, пусть для любого разряда допустимьши цифрами частного являются ttg, . . ..а, причем - наименьшая из них, aUk - наибольшая (в алгебраическом смысле).

Рассмотрим некоторый /-й шаг. Для того чтобы во всех последующих шагах {i gt; j) остатки Bi убьшали с той же

скоростью, с какой убывают величины G, необходимо и достаточно, чтобы на /-М шаге выполнялись условия

Достаточность этих условий вытекает из того, что их выполнение на j-м шаге позволяет выбрать очередную цифру частного С/ так, чтобы аналогичные условия выполнялись и для (/ -- 1)-го шага. Например, если В/минимально, Bf = 2aiCj, то, выбрав минимально возможную цифру частного а,- = (с тем, чтобы следующий остаток уменьшился возможно слабее), получили бы

= Bj - cLjCj - 2cfCj - аС/ = laquo;хС/ = 2сХхС/+х.

Точно так же если Bj ма ксимально, Bj = 2а Cj, то для О/ нужно выбрать максимально возможное значение а] = сс;, в результате чего получится В/+х = 2afeC/+i.

Для доказательства необходимости указанных условий предположим, что на /-м шаге они не выполняются; пусть, скажем, Bj = (2aft -f 8/)С/, где е,- gt; 0. Выбрав для этого случая максимальную цифру частного с/ = ад, (с тем, чтобы возможно сильнее уменьшить следующий остаток), мы тем не менее получили бы

= Bj - a,Cj = {2ak -Ь е,-) Q -аС/ = (а + 8,)С/ =

= {2ан + 2б;) Су+х,

так что 8/+X = 2е/ и вообще для всех последующих шагов = 28г (t gt; /).

На первом шаге деления нормализованных чисел, когда Во = В, Со = С, имеет место соотношение О lt; 2Со. Чтобы оно было эквивалентно указанному условию, необходимо, чтобы наименьшая из возможных цифр частного (ох) была не больше О, а наибольшая из возможных цифр частного (ttft) - не меньше 1. Это - единственное ограничение, накладьгоаемое на набор возможных цифр частного laquo;х, ог. ., Kft. (Отсюда, в частности, видно, что количество возможных цифр должно быть не меньше двух; например, годятся наборы цифр ах = О, ag = 1 - как в первом из описанных ранее методов деления, или ах = - I, = Л - как во втором методе.) Далее каждую очередную цифру частного ш следует выбирать из имеющегося набора допустимых

цифр а, ttg, . .,aft по правилу:

если 2aiQ lt; Bi lt; (а + ay) Ci, то а,- = ai, если {aci + laquo;а) С; lt; Bi lt; (ос + а) d, то а,- = Оз, если (ai + аз) Q lt; В; lt; (ocfe + аз) С/, то С/= ад,

если (ai + aft)C/ lt;B, lt;2aftCj, то ai = ak.

Так как для следующего шага Bii = Bi - CjC,-, а Cj+i = = -Ci , то соблюдение этого правила на t-м шаге обеспечит для следующего (i -f 1)-го шага вьшолнение аналогичного условия (2aiQ+i lt; Bj+i lt; SaQ+i), как это и требуется.

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

если 2aiQ lt; В/ lt; (cXi -- а) Ci, то с,- = laquo;1; если (а -- a2)Ci lt; Bi lt; 2a2Q, то щ =

свобода в выборе очередной цифры частного существовала только в одном частном случае, когда В[ = (а + щ) Сс. Например, если = О, = I, то при О lt; В,- lt; Q выбирается а,- - О, при Q Bi 2Ci - щ - 1; если = = -I, laquo;2 = 1, то при - 2Ci В/ О выбирается Cj = -1, а при О lt; В,- lt; 2Ci - а, = 1). Допустив существование большего количества возможных цифр частного, получим большую свободу в выборе очередной цифры; например, имея набор из трех возможных цифр, = - I, а2 = О, аз = 1, получим следующее правило:

если - 2Ci lt; Bi lt; О, то а/ = - 1, если -CiBi d, то щО, если О lt; В/ lt; 2С/, то а, = 1;

в интервалах значений В/ от -2С[ до -С; и от -f Ci до -Ь- 2Ci очередная цифра частного выбирается всегда однозначно; в интервале от - С,- до О в качестве с,- можно выбрать и -1, и О, а в интервале от О до + С,- - либо О, либо + 1. Чем больше разных возможностей допускается для цифр частного, тем шире интервалы значений В/, в которых возможен неоднозначный выбор значения щ.