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

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

Как бы мы ни изменили любую цифру в исходном числе, в конечном результате может измениться не более двух цифр.

Иное положение при умножении десятичных чисел, скажем, на число 3, не являющееся особым множителем. Например

333 333 X 3 = 999 999, а 333 334 X 3 = 1 ООО 002;

изменение одной младшей цифры в исходном числе привело к изменению всех цифр произведения.

Точно так же можно доказать, что в произведении произвольного п-ичного числа на ггУ цифра любого разряда зависит только от цифры данного разряда и цифры соседнего слева разряда исходного числа.

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

Теперь уже нетрудно доказать сформулированное в начале раздела положение и для произвольного особого множителя q = nlnl . . . п\. Произведение любого /г-ичного числа Anaqможно рассматривать как результатх последовательных умножений на % (или, если отрицательно, si последовательных делений на п, затем Sg последовательных умножений на laquo;2 (или может быть, последовательных делений на Па, если Sg lt; 0) и т. д. Отсюда и вытекают приведенные выше утверждения.

Указанные свойства особых множителей позволяют получить произведение любого числа на особый множитель сравнительно простыми средствами.

представим себе, например, что основание системы счисления четно - скажем, п == 10. Число 2 является особым множителем, причем таким, что в произведении любого числа на 2 цифра некоторого разряда зависит только от цифры данного разряда и цифры одного соседнего справа разряда исходного числа. Пусть исходное число помещается в триггерный регистр. Присоединив к выходам каждой пары разрядов регистра (1-го и 2-го, 2-го и 3-го, 3-го и 4-го и т. д.) некоторую специальным образом построенную логическую схему, можно на выходах этих схем получить произведение исходного числа, помещенного в регистр, на 2. При этом логические схемы в каждой паре разрядов одинаковы между собой, суммарное количество оборудования пропорционально общему количеству разрядов в регистре, а образование удвоенного числа может происходить в течение одного такта (потому что все логические схемы в каждой из пар разрядов срабатывают одновременно - независимо одна от другой).

Аналогичным образом легко устроить цепи, формирующие произведение числа, находящегося в регистре, на 4, на 5, на 8 или вообще на любой особый множитель.

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

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

ния удвоенного и учетверенного множимого (полученных заранее с помощью сумматора), можно присоединить к регистру С цепи удвоения и учетверения и предусмотреть возможность передачи на сумматор чисел с их выходов. Эффект при этом получится точно такой же, как при наличии регистров С и С , а в схемном отношении такое решение может оказаться более простым. Оно возможно, однако, только при условии, что основание системы счисления четно (например, п ~ 10), вследствие чего 2 и 4 являются особыми множителями; заготовить заранее с помощью сумматора удвоенное и учетверенное множимое в регистрах С и С можно было при любом п.

4.4.3. Понижение основания системы счисления. В системах счисления, для которых основание п не является простым числом, возможен еще один метод ускорения умножения, использующий особые множители. Мы назовем .его методом понижения основания системы счисления. Хотя один из частных случаев этого метода известен по литературе давно (под названием laquo;метода удвоения и деления пополам raquo;), в реальных устройствах он, по-видимому, не применялся. (Зднако с теоретической точки зрения этот метод представляет значительный интерес. Впрочем, не видно причин, почему бы не использовать его и на практике. Идея метода состоит в следующем.

Представим себе для определенности, что речь идет об умножении десятичных чисел, изображенных позиционным способом с естественными весами разрядов и с запятой, фиксированной перед старшим разрядом числа, и что умножение предполагается выполнять в соответствии с четвертым вариантом основного алгоритма (см. 4.1.2); в связи с этим общее построение множительного устройства соответствует рис. 4-2, г на стр. 350. Однако и в способ выполнения умножения, и в общее построение устройства мы внесем некоторые изменения.

Изменения в построении множительного устройства, сведутся к тому, что в регистре множимого (Q цепи сдвига вправо на один десятичный разряд мы заменим цепями деления пополам, а в регистре множителя (А) цепи сдвига влево на один десятичный разряд заменим цепями удвое-