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

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

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

4.4.2. Особые множители. Особым множителем мы будем называть число, представляющее собой произведение любых целых степеней простых делителей основания системы счисления п. Если

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

q = nlmlK.Mlk,

где каждый из показателей степени Si - целое число (положительное, отрицательное или нуль). Например, для десятичной системы п = 10 = 2 -5; особыми множителями являются числа 2 = 21 -5 , 4 = 2 -б raquo;, 5 = 2 raquo; -б, 8 = 2 raquo; -5 , 10=21.51 ig=2* 5 ,20=22.51,25=2 5...,чиcлa 1/2=2-1 -б , 1/4 = 2 -5 , 1/б = 2 5~, . . ., а также такие числа, как

= 21 -5-1, laquo;/s = 2 -5-1, 7s = 2 raquo; -5-1, = 2-i -51, s/4 = 2-2 -51, = 2-s .52 и др.

Мы докажем сейчас, что при умножении любого числа, представленного позиционной п-ичной системой с естественными весами разрядов и неотрицательными цифрами, на особый множитель q = nl г. . . п* каждая цифра результата зависит не более чем от 1 + [ + Sg + ... + \sk\ цифр исходного числа и не зависит от всех других его цифр. При этом на цифру данного разряда результата могут влиять цифры того же разряда исходного числа и цифры % I + I Sa I +. .. + I Sft I соседних разрядов; если Bces,- положительны, то речь идет о соседних справа разрядах, если все si отрицательны - то соседних слева; если5/ st . . .,Sj

положительны, а s, Sm . . ., Sm отрицательны, то влия-



ние могут оказать st + Si, + . . . + S/ соседних справа и Sffli+ Snu + . + Si \ соседних слева разрядов *).

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

n deg; i / /+1 а - Д- * десятичной системы, например, имеется два особых множителя указанного вида: 2 и 5. \, Поскольку, как мы условились, мы пользуемся п-ичной системой счисления с неотрицательными цифрами, в любом из разрядов исходного числа цифра а может принимать одно из п значений: О, 1,2,.. ., (п - 1).

Рассмотрим прежде всего все возможные произведения вида am. Поскольку гц - простой делитель п, то наверняка щ lt; п (тривиальный случай, когда п - простое число и его простые делители равны % = 1, Пг = п, не принимается во внимание); отсюда видно, что произведение am наверняка меньше, чем п, и в п-ичной системе представляет собой однозначное или двузначное число.

Левая цифра в его изображении показывает, сколько раз п содержится в произведении апг, так как максимальное произведение вида am есть (п - - пт - т, то левая цифра в любом произведении ащ не превышает т - 1.

Тем же свойством обладали бы левые цифры произведений am и в том случае, если бы щ не было простым делите- лем п (но П[ lt; п).

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

п1пг чисел натурального ряда 0,1,2,..., (~--Л.

\ laquo;г j

Правые цифры указанных произведений равны соответственно О, пг, 2т, п - т. При умножении на т следу-

*) Материал разделов 4.4.2, 4.4.3,4.4.4 был впервые опубликован . в докладе Карцева М. А. и ГливенкоЕ. В., laquo;Дробные основания системы счисления и их использование для ускорения операций в цифровых машинах raquo;. Colloquium on the Foundations of Mathematics, Mathematical Machines and their Applications, Будапешт 1965, стр. 215-226.



ющего числа из натурального ряда (числа nltii) получим в качестве произведения число п, для которого правая цифра п-ичного представления есть снова 0; при умножении следующего числа \~--1 ] получим (n-\-ni), где правая

цифра в п-ичном представлении есть опять щ, и т. д.

Итак, при умножении любой п-ичной цифры а на особый множитель т получаем одно- или двухзначное число, в котором левая цифра не превышает гц - 1, а правая цифра не превышает п - гц. Например, при умножении десятичных цифр 0,1, 2, . . ., 9 на 2 левая цифра произведения не превышает 1, а правая цифра не превышает 8; при умножении тех же цифр на 5 левая цифра произведения не превышает 4, а правая цифра не превышает 5.

Пусть теперь на щ умножается многоразрядное п-ичное число А. Умножив каждую из его цифр на т, выпишем отдельно число, состоящее из правых цифр этих произведений, и отдельно.число, состоящее из левых цифр произведений; в первом из них каждый разряд определяется соответствующим разрядом исходного числа, во втором - соседним справа разрядом исходного числа. Для того чтобы получить полное произведение Лп эти два числа нужно между собой сложить. При этом, поскольку любая из цифр первого числа не превышает п - т, а любая из цифр второго числа не превышает гц-- 1, сумма цифр в любом разряде не превышает п - 1, т. е. сложение вьшолняется без переносов из разряда в разряд. Следовательно, любая цифра в произведении Л п/зависит только от цифры соответствующего разряда и цифры одного соседнего справа разряда исходного числа, ноне зависит от цифр всех остальных его разрядов. Пусть, например, десятичное число 875 039 466 умножается на 2:

(произведения отдельных цифр на 2)

(число, составленное из правых цифр)

(число, составленное из левых цифр) (полное произведение) 17 5 О U

6 6

12 12

2 2



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