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

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

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

один разряд множителя, оказывается равным -{п-и.

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

Займемся поэтому подробнее случаем, когда основание системы счисления п четно.

В качестве отправной точки предположим, что умножение начинается от младших разрядов множителя и для его ускорения применяется метод группировки разрядов. Дальнейший план наших действий будет таков.

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

Ах /4.

Непосредственным перебором всех комбинаций цифр найдем также, каково в среднем минимальное количество суммирований-вычитаний при умножении на пару разрядов, если разряды множителя группируются по два. Эту величину обозначим Л 2-

*) Для частного случая и = 2 эта задача была поставлена и решена автором настоящей книги в 1957 г. (см. диссертацию laquo;Основы построения арифметических устройств и инженерное решение арифметического узла вычислительной машины М-2 raquo;, 1957, а также книгу laquo;Арифметические устройства электронных цифровых машин raquo;, Физматгиз, 1958, стр. 116-122). Судя по ссылкам, имеющимся в литературе, в то же примерно время такой же результат был получен д-ром Reitwissner (США). Постановка и решение полной задачи имеются в работе автора laquo;Логические методы ускорения умножения в цифровых вычислительных машинах raquo; (сб. laquo;Проблемы кибернетики raquo;, вып. 4, 1960, стр. 111-120).



Далее предположим, что всевозможные группы из (р - 1) разрядов множителя преобразованы оптимальным способом и что нам известно, каково в среднем минимальное количество суммирований-вычитаний Лр 1, необходимое при умножении на группу из (р - 1) разрядов; найдем, на СКОЛЬКО увеличится это количество, если разряды будут-теперь группироваться не по (р - 1), а по р, т. е. найдем разность Ар - Лр 1. По этим данным вычислим Ад - среднее значение минимального количества суммирований-вычитаний, приходящееся на группу из q разрядов множителя при группировке разрядов по q, где q - произвольное целое число, q gt;1; вычислим также величину Ag/q, т. е. сред-нее значение минимального количества суммирований-вычитаний, приходящееся на 1 разряд множителя, при условии, что разряды множителя собираются в группы по q, и каждая такая группа преобразуется оптимальным образом.

Далее можно будет найти и lim Поскольку, как

мы увидим, величина Ag/q весьма близка к пределу уже при сравнительно небольших значениях q, можно полагать, что для т-разрядного множителя (т обычно достаточно велико) минимальное количество суммирований-вычитаний при оптимальном преобразовании множителя (если его рассматривать как одну laquo;группу raquo; из т разрядов) равно

mlim- . Этот результат будет иметь уже более общее

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

Приступим к осуществлению этого плана.

Итак, нам известно, что А = Д.

Пусть теперь разряды группируются по два ( = 2).

Пока в каждую laquo;группу raquo; входил один разряд множителя, при наличии в нем цифры /g нам было безразлично, -как вести ближайший цикл умножения: добавлять ли множимое /а раз, ничего не передавая в следующий разряд множителя, или вьиитать множимое /а раз и передавать единицу в следующий разряд. Если теперь разряды множителя группируются по два, то в тех комбинациях, когда



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

Например, в десятичной системе при преобразовании каждого разряда в отдельности комбинация ..4..5 сохраняется без изменений, а комбинация ..6..5 представляется в виде (1)..4.-5 (две точки означают границы групп); в обоих случаях получаем по 9 суммирований-вычитаний при выполнении двух циклов умножения (для комбинации ..4..5..5 суммирований в первом цикле и 4 суммирования во втором; для комбинации ..6..5 5 суммирований в первом цикле и 4 вычитания во втором). Если же разряды группиру- ются по парам, то комбинацию ...45 выгодно по-прежнему оставлять без изменения, а комбинацию ..65 представить в виде (1) ..3 5, в результате чего количество суммирова- ний-вычитаний при выполнении пары циклов умножения уменьяштся для этой комбинации на единицу (5 вычитаний в первом цикле и 3 вычитания во втором).

Так как суммарная вероятность комбинаций, в которых при группировке разрядов в пары можно сэкономить по

одному суммированию-вычитанию, равна 4 i то

Пусть теперь нам известна величина Лр 1; найдем разность Ар - Ар-..

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



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