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

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

к группам по р разрядов не возрастало, здесь будем иметь увеличение на 1; в тех случаях, когда в комбинациях, начинающихся с laquo;О raquo;, мы имели увеличение количества суммирований-вычитаний на 1, в комбинациях, начинающихся с laquo;1 raquo;, увеличение количества суммирований-вычитаний составит 2. Учитывая, кроме того, что суммарная вероятность

комбинаций, начинающихся с laquo;1 raquo;, равна -, найдем величину, которая вносится в разность Ар -Ар, всеми этими комбинациями:

ДО) д(о)+ 1,

Точно так же

Д(2) Д(0) 1 Д(3) Д(0) 1

и -2

д2 Д(0) А .

Для комбинаций, начинающихся с цифры g, можно

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

п - 2

Затем, аналогично предыдущему,

я -2

Д(-1) = Ат)-- д(о) ,1

/7. I ..п

Теперь можем получить (для р gt; 2)

л ffl - ,

4 2(и+ 1)

Наконец,

Подставляя вычисленные выше значения А и Ар - Ар-, после некоторых преобразований найдем, что для любого четного п

Для нечетных п, как мы говорили, при любых q

Объединяя эти результаты, получим (для любых п я q) А, 1

4( laquo;+1)

X [! (- laquo;)-.]+ [1-( 1)п]

Отсюда

/I? 1

lim =

4(re+l)

2 + 2 + plusmn; J[l ( l) laquo;],

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

корения умножения), в среднем равно примерно m lim

Иначе говоря, на каждый /г-ичный разряд множителя в среднем придется по ( lim ) суммирований-вычитаний; вели-

чина т lim -7 равна примерно математическому ожида-

нию суммы цифр 2 Iil В оптимальном представлении мно-

жителя. Выражения эти тем точнее, чем больше т. Однако, имея приведенцое строчкой выше выражение для AJq, нетрудно подсчитать, что даже при небольших значениях q = т отношение Amitn весьма близко к предельному значению.

В частности, для двоичной системы, подставляя п = 2,

(А \ 1

lim = -5-, для троичной системы

AimJjli.) =Л,для четверичной системы [lim .) =

= jg-,..., ДЛЯ десятичной

flim А

П=10

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

Аналогичным образом, скажем, в десятичной системе наиболее сильные логические методы ускорения могут дать /ц 2,45 суммирований-вычитаний на десятичный разряд - примерно столько же, сколько дае! сравнительно простой метод перехода к симметричному диапазону цифр (2,5 суммирований-вычитаний на разряд); впрочем, в 4.2.3, где описывался этот метод, мы упоминали уже о том, что при большом п дальнейшее усложнение логических методов ускорения умножения не может дать значительного эффекта.