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

системы счисления п. Как функция fo{n), так и функция foa(n), которыми мы пользовались ранее для оценки скорости выполнения умножения, монотонно убывают с уменьшением п. Для целочисленных п эти функции имеют наименьшие значения при- п == 2; но брать п lt; 2 мы не пытались. Мы покажем сейчас, как можно использовать системы счисления с дробными основаниями; при этом очевидно, наибольший интерес будут представлять случаи, когда 1 lt;п lt;2.

4.4,4. Применение дробных оснований систем счисления. Предельная оценка для методов 1-го порядка. Допустим, что в исходном представлении чисел основание системы счисления п {п - целое, п gt; 1) не является простым числом, или целой степенью простого числа. При этом всегда имеется ряд особых множителей, находящихся в интервале от 1 до 2. Например, в десятичной системе имеются .особые множители 1,25 (или 2 -Ъ); 1,6 (или 2 -Ъ ) и др.

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

Заменим в схеме десятичного множительного устройства, изображенной на рис. 4-8 (стр. 422), цепи удвоения в регистре А цепями умножения на 1,6 , а цепи деления пополам в регистре С - цепями деления на 1,6.

Далее будем действовать в точности по аналогии с разделом 4.4.3. Произведя первое умножение на 1,6в регистре А, мы узнаем, превосходит ли исходный множитель величину (1,6)~1, т. е. найдем первый коэффициент в разложении множителя по степеням числа 1,6. В зависимости оттого, каков этот коэффициент - 1 или О,- мы либо произведем суммирование В -\- С, либо не произведем (в регистре С в это время находится результат первого деления множимого на 1,6, т. е. число (1,6)-1 С). Далее вновь произведем умножение на 1,6 в регистре Л и деление на 1,6 в регистреС; разряд целых регистра Л даст при этом второй коэффициент в разложении множителя по степеням числа 1,6 (при члене (1,6)-*), а в регистреС получится произведение множимого С на (1,6)-*, которое либо будет суммироваться с регистром В, либо не будет и т. д.



Количество циклов умножения т,), которые нам придется выполнить, определяется соотношением

гае) = n(io)/lg 1,6,

где /И(]о) - количество десятичных разрядов в множителе.

Действительно. Отыскивая коэффициенты полинома по степеням 1,6, мы каждый раз умножаем на 1,6 число, оставшееся в регистре Л от предыдущего цикла. Непосредственно по смыслу выполняемых преобразований очевидно, что величина, остающаяся в регистре А после m;i,g)-ro цикла, заключена в интервале от О до 1 (потому что в регистре Л остается дробная часть предыдущего результата) и является последним остатком, умноженным на 1,6 - (так как в каждом из предыдущих циклов очередной остаток умножался на 1,6). Таким образом, погрешность представления числа с помощью m;i,G) членов полинома по основанию 1,6 меньше, чем 1,6 *). Для получения той же точности, что и при изображении числа десятичными разрядами, необходимо, чтобы

1,6 ( gt;- lt;5) = 10 (w),

откуда и следует приведенное выше соотношение для m.g)-Например, точности в три десятичных разрядасоответствует, примерно 15 членов в разложении по степеням числа 1,6; следовательно, количество циклов умножения в рассматриваемом выше примере должно было бы стать примерно равным 15.

Труднее подсчитать, каково в среднем количество суммирований, которые придется при этом выполнить. Хотя каждый из коэффициентов в разложении по степеням 1,6 может принимать одно из двух возможных значений - 1 или О (так же, как в двоичной системе), цифры эти - в отличие от двоичной системы - не равновероятны.

Предположим, что исходное значение множителя может быть с равной вероятностью любым числом из интервала О -г- 1. Тогда вероятность равенства единице первого коэффициента в разложении по степеням 1,6 есть 0,375: для того чтобы результат первого умножения множителя на 1,6 был больше или равен единице, исходная величина множителя должна быть заключена в интервале 0,625 1; если исходная величина множителя заключена в интервале



от о до 0,625, то в результате умножения на 1,6 получим число меньше единицы.

Если первый коэффициент оказался равным О, то в регистре А после первого умножения на 1,6 с равной вероятностью может оказаться любое число из интервала 0-ь 1; если же первый коэффициент оказался равным 1, то в регистре А остается одно из чисел из интервала О ~ 0,6 (Л -1,6- 1, где Л -исходное число, 0,625 Л lt; 1). Поэтому вероятность равенства единице второго коэффициента равна произведению 0,375 на вероятность того, что первый коэффициент равен нулю, т. е. 0,375 X 0,625 = fc= 0,234.

Число, остающееся в регистре Л после второго умножения на 1,6, с вероятностью 0,625 заключено в интервале 0-- 1, с вероятностью 0,375-в интервале от О до 0,6 х X 1,6 = 0,96, с вероятностью 0,625-0,375 - в интервале О 0,6. Поэтому вероятность получить единицу после третьего умножения на 1,6 равна

0,6252-0,375 -f 0,375 0,278.

Рассуждая аналогичным образом, найдем, что вероятность равенства единице четвертого коэффициента в разложении по степеням 1,6 есть 0,264, пятого коэффициента- 0,254 и т. д.

Полагая - с некоторым запасом,- что вероятность равенства единице каждого из коэффициентов в разложении по степеням 1,6 не превышает в среднем 0,3, найдем, что при умножений, скажем, 3-значных десятичных чисел указанным способом среднее количество суммирований не превысит 0,3-15, т. е. 4,5 (15 -это количество членов разложения по степеням 1,6). Для сравнения напомним, что при переходе к двоичной системе среднее количество суммирований для этого случая оказалось равным 5 -ь- 5,5, а в десятичной системе оно было еще больше.

Читателю предлагается самостоятельно повторить данным методом пример, выполненный в 4.4.3 методом удвоений и делений пополам: умножить 0,738 X 0,476, пользуясь умножениями и делениями на 1,6; количество суммирований, которые придется при этом произвести за 15 циклов умножения, окажется равным всего 5 (против 7 в том же



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