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

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.4.3, но понижение основания системы счисления стали производить не к целому п, п gt; 2, а к дробному п, 1 lt; п lt;Г 2. При этом об основании системы счисления мы говорим теперь в смысле второго определения, приведенного в 1.2.1 (стр. 16), ко-торьш мы до сих пор на протяжении почти всей книги пользовались мало.

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

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

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

Введем для данного п, 1 lt; п lt; 2, еще одну численную характеристику kn определяемую по соотношению

- Wn-

По смыслу kn есть минимальное расстояние между двумя п-ичными разрядами, которые могут содержать единицы в изображении любого числа А. Это следует непосредственно из рассмотрения алгоритма перевода некоторого числа

в n-ичную систему счисления. В самом деле, к началу любого цикла перевода (преобразования множителя А в ходе умножения в п-ичную систему) остаток от предьщущего цикла, умноженный соответствующее количество раз на п, может оказаться по величине заключенным в интервале О -V- 1. Допустим, что выданном f-м цикле очередная п-ич-ная цифра получается равной единице, т. е. что произведение предьщущего остатка на п в данном случае получается больше или равньм единице. Но произведение предыдущего остатка на п не может быть больше, чем п (так как предьщущий остаток не больше единицы). Очередным остатком будет при этом дробная часть указанного произведения, т.е. величина, непревышающая п-1. В следующем (f-bl)-M цикле этот остаток умножается на п. Если п (п - 1) 1, то следующая п-ичная цифра будет непременно нулем. Затем в (t -Ь 2)-м цикле величина п{п - 1) умножается на п; если {п - 1) lt; 1, то и (t -Ь 2)-я цифра будет непременно нулем. Следующая единица может получиться, очевидно, не раньше (i + k) -го цикла, где

Интересно подсчитать, при каких значениях п получаются целые значения kn. Непосредственно из выражения для kn можно найти :

kn=\ при п1,62, fe =4 при п?=;1,32, yfe = 2 при п яг 1,47, й = 5 при п 1,28, kn. = 3 при п ~ 1,38, й = 6 при п 1,25

(см. также таблицу 4-4).

Это значит, что, когда основание системы счисления п заключено в интервале от 1,62 до 2, в п-ичном изображении любого числа две соседние цифры могут быть единицами; когда 1,47 lt; п 1,62, между двумя единицами в п-ичном представлении любого числа должен находиться по меньшей мере один разряд, содержащий laquo;О raquo;; когда 1,38 lt; п lt;

1,47, между двумя единицами в п-ичном представлении любого числа находятся по меньшей мере 2 разряда, содержащие нули, и т. д.

Сравнивая выражения для m( ) и для Щп), нетрудноубедить-ся, что, каково бы ни было число тр), всегда можно найти такое значение п, достаточно близкое к единице, чтобы выполнялось соотношение

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

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

является оптимальньш. Иначе говоря, при заданной точности (при заданном количестве десятичных разрядов то)) оптимальное основание системы счисления nopt находится по соотношению

. (.О) lt; - Ig ( opt - 1)

n pt lt;l + 10- ( ).

Принципиальное значение полученного результата состоит в следующем. Если nopt является особым шoжитeлeм для некоторой исходной системы счисления с основанием п, то умножение в системе счисления с основанием п можно свести к умножению в системе счисления с основанием nopt, причем количество оборудования для этого будет пропорционально количеству разрядов в исходной системе