www.chms.ru - вывоз мусора в Балашихе 

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

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

(б) если соседняя справа цифра множителя больше или равна /2, то добавить единицу к величине, полученной в результате (а).

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

Пример. Множитель, записанный по обычной десятичной системе в виде

[0] . 8470251964,

в соответствии с приведенным правилом преобразуется в форму

1.2 5 3 0 3 5 2 0 4 4.

При умножении на непреобразованный множитель потребовалось бы

8-f4+7+0+2+5+1+9+6+4=46

тактов суммирования; при умножении на преобразованный множитель требуется

I+2 + 5 + lSl + 0 + 3 + l5l + 2 + 0 + 4+4 = 29

тактов суммирования-вычитания.

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

Если при четном п нежелательно допускать и цифру - /г, и цифру + /а или если п нечетно, то преобразова-



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

- если цифра данного разряда больше /2, то вычесть из нее п и запомнить единицу, передаваемую в следующий (старший) разряд;

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

Таким правилом преобразования мы тоже пользовались в начале 4.2.2 (стр. 367) для четверичной системы, которая получалась при группировке по парам разрядов двоичного множителя.

Вернувшись к предьщущему примеру, десятичный множитель

[0].8470251964

преобразуем по указанному правилу следующим образом (где в круглых скобках указаны цифры, передаваемые из данного десятичного разряда в следующий старший разряд):

[0] 8470251 9 64

(+0) 6

(+1) 10

(+0) 2

(+0) О .

(+0) 7

(+1)

(+0) 8

(+1)

1. 2 5 3 0 2




Количество необходимых тактов сложения-вычитания теперь оказывается равным

l-f 121 + 5 + 13 1 + 0 + 2 + 5 + 2 + 0 + 131+ 4 = 28

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

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

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

Максимальное количество тактов суммирования-вычитания, приходящееся на один разряд множителя, для

четного п равно Д, Для нечетного - величине

вместо п - 1 для случая, когда симметрирование диапазона цифр не применяется. (При п = 2 снова получаем, что метод симметрирования диапазона цифр ничего не дает, так как Д = laquo; - I )

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



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