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

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

Если п четно, то среди всех возможных цифр имеется одна, а именно Д, с которой при преобразовании можно

обращаться - двояко: представляя ее либо в виде (0) ,

либо в виде (1) ; при этом количество тактов суммирования или вычитания при умножении на данный разряд множителя получается одинаковым. Это позволило нам на стр. 376 сформулировать такое правило преобразования множителя для четного п, которое удобно было применять и при умножении от старших разрядов, и при умножении от младших разрядов. В соответствии с указанньм правилом цифра в некотором разряде преобразованного множителя зависела только от цифры данного разряда и от одной соседней справа цифры непреобразованного множителя и не зависела от всех других цифр. Если, в частности, i-й разряд (нумерация разрядов - слева направо) содержал до преобразования цифру /г, то к (/ - 1)-му разряду при его преобразовании добавляется единица, а в i-u разряде получится (в зависимости от (t + 1)-го разряда) либо

- /г, либо -если же t-й разряд до преобразования

содержал цифру Уг, то к {i - 1)-му разряду единица не добавляется, а в (-м разряде может получиться (в зависимости oT:{i 4- 1)-го разряда) либо Д. либо Уг.

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

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

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

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

При нечетном п нет цифр, допускающих двоякую расшифровку, и указанные возможности отсутствуют.

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

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

Пусть каким-либо образом любое т-разрядное п-ичное число а преобразуется к виду

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

ма 21 raquo; I минимальна, т. е. что минимальным является

количество тактов суммирования или вычитания, необходимых при умножении на а. Определим:

1) каково математическое ожидание величины

для всевозможных а при данных т я п, в предположении, что все значения а равновероятны;

2) как зависит математическое ожидание величины

т

2 I 1 от основания системы счисления п (при

указанном выше условии для т) и при каком основании системы счисления Попт оно минимально;

3) каково математическое ожидание величины 21 1

при использовании системы счисления с основанием Попт-

Решение первого вопроса даст нам ответ о предельном ускорении умножения, которое возможно при использовании логических методов, при условии, что основание системы счисления п задано заранее. Второй вопрос фактически должен расширить наши представления о влиянии величины п на скорость вьшолнения операций (см. 1.2.3); величина Попт. которую мы хотим определить,- это то оптимальное основание системы счисления, использование Которого позволяет логическими методами достигнуть максимальной скорости вьшолнения умножения с заданной точностью. Наконец, ответ на третий вопрос должен дать представление об абсолютном пределе скорости вьшолнения умножения, которая может быть получена применением