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

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

5.1.8. Выполнение деления в системе счисления с основанием raquo;г gt;2. Способы выполнения деления в системе счисления с основанием п не содержат каких-либо существенно новых идей по сравнению с рассмотренными ранее способами деления в двоичной системе.

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

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

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

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

laquo; - 2, td это значит, что она есть п - 1 (других возможностей не остается), и я-е сравнение производить уже не имеет -смысла.

Таким образом, каждый цикл выполнения деления в системе счисления с основанием п содержит от одного до (п - 1) сравнений и от нуля до laquo; - 1 вычитаний (вычита--ний обычно на одно меньше, чем сравнений, кроме случая, когда очередная цифра частного оказывается равной п - 1). Подобно тому как laquo;-ичное умножение сводится к серии сдвигов и суммирований (до п - 1 суммирований в каждом цикле), так п-ичное деление сводится к серии сдвигов и сравнений-вычитаний (до п - 1 сравнений-вычитаний в каждом цикле).

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

В полном соответствии с тем объяснением второго способа деления, которое приведено в 5.1.3 (стр. 504-506), этот способ применительно к laquo;-ичной системе счисления должен быть изложен следуюш,им образом. Если к началу некоторого цикла деления предыдущий остаток положителен, то в данном цикле должна производиться серия вычитаний делителя из остатка; вычитание нужно производить до тех пор, пока не получится отрицательный результат (но не более laquo;-1 раз, хотя бы результат и остался положительным). Если к началу некоторого цикла деления предыдущий остаток отрицателен, то в данном цикле деления должна производиться серия сложений делителя с остатком; сложение нужно выполнять до тех пор, пока не получится положительный результат, но не более п - 1 раз (хотя бы результат и остался отрицательным). Количество вычитаний, произведенных в данном цикле деления, есть количество положительных единиц, содержащихся в очередной цифре частного, количество сложений - количество

отрицательных единиц; результат сложении или вычитаний в любом случае представляет собой очередной остаток, который перед следующим циклом должен быть сдвинут на 1 разряд влево (или делитель нужно сдвинуть на разряд вправо). Частное получается в форме записи цифрами - (п - 1), - (п - 2), . . . , -2, -1, +1, +2, . . + ( laquo; - 2), + ( laquo; - 1); впрочем, нетрудно предусмотреть преобразование частного в обычную форму записи (с цифрами О, 1, 2, . . ., (п - 1)) по ходу выполнения деления - так, как в 5.1.1 это сделано для двоичной системы.

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

Примеры (в десятичной системе счисления).

1-й цикл

(старшая цифра-(-1)

2-й цикл

(вторая -цифра -9)

0,025 0,625

(1-й остаток) -0,600

(сдвиг влево) -6,000 +0,625

-5,375 +0,625

-4,750 +0,625 -4,125 +0,625

-3,500 +0,625 -2,875 +0,625 -2,250 +0,625 -1,625 +0,625 -1,000 +0,625

(2-й остаток) -0,375

0,625