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

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 deg; и 2 справедливы не только для однородных, по и вообще для любых систем счисления. Например, если цифры п-ичной системы счисления кодируются при помощи минимального количества двоичных цифр, то в любом случае (в том числе и при возможности использования смешанных -систем) наилучшими с точки зрения затрат оборудования являются системы счисления с основаниями 2,4,8,16.....а также системы с очень высокими основаниями.

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

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

1 deg;. Скорость выполнения умножения очень Значительно сказывается на общем быстродействии машины. Как показывает рассмотрение многих разнообразных задач, умножение приходится выполнять в общем несколько реже, чем сложение или вычитание. Но так как выполнение одного умножения требует большего времени, чем выполнение одного сложения или вычитания, то оказывается, что при решении многих задач машина в основном занята выполнением умножений.

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

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

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

Следующий пример иллюстрирует этот метод на примере умножения 2-разрядных десятичных чисел:

94.-множимое 23-множитель

ОООО - начальное состояние регистра частичных произведений

+94

0094

4-94

? - умножение на 1-ю цифру множителя (3)

-Ь94 0282 .

- умножение на 2-ю цифру множителя (2) 4-94

-162--результат

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

Максимальная цифра множителя - это п - I. Например, в двоичной системе максимальная цифра есть 1, в десятичной системе 9. Поэтому и максимальное количество сложений, которые потребуются при умножении на один разряд множителя в системе счисления с основанием п, равно п - 1.

Предположим далее, как это мы делали в 1.2.2, что точность вычислений характеризуется количеством N различных чисел, с которыми оперирует машина, и что соответствующее количество разрядов в п-ичной системе счисления равно \ognN. Тогда полное количество сложений, которые максимально могут потребоваться в процессе выполнения одного умножения, равно

(п - 1) -lognN.

В частности, в двоичной системе оно равно 1 logN. Функция

(n-l)log / laquo;-1

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

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

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