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

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.1.3, п. 3 deg;).

Вследствие этого представление чисел в остатках использовалось до сих пор либо в малых вьиислительных

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

2 deg;. Приведем для справок один из алгоритмов сравнения чисел в остатках, предложенный некогда М. Л. Цейт- линым.

Пусть числа представлены остатками от деления на s, S2,....,Sm, где51, S2,...,Sm-взаимно простые числа % gt; S2 gt; ... gt;Sm, максимально возможное число равно N - 1 = = ss.-.Sm - 1. Ограничение в применении алгоритма сое:

ТОИТ в том, что должно быть Sm = 2.

Задачу сравнения двух чисел можно свести к задаче определения того, меньше ли некоторое число, чем N/2 = = SiS2...Sm-i если одно из двух сравнимаемых чисел меньше, чем N/2, а другое больше, то ответ сравнения ясен; если оба числа меньше N/2 или оба больше N/2, то для выполнения сравнения нужно определить, какова их разность по модулю N (если разность меньше N/2, то уменьшаемое больше или равно вычитаемому).

Итак, пусть имеем число Ci, а2,...,ат, где а,- - остаток от деления на s;, щ S; - 1; требуется определить, меньше ли это число, чем N/2.

Отбросим (заменим звездочкой) последнюю цифру числа Ci, a2,...,am-i,*. Заметим, что по одному числу вида их, ...,am i,* имеется как среди чисел, меньших Л 2, так и среди чисел, больших или равных N/2; одно из этих двух чисел четно, другое нечетно (ср. левую и правые части таблицы 1-5).

Сделаем предположение, что исходное число меньше N/2. Будем вычитать из числа Ci, a2,...,a i,* единицу (т. е. число 1,1,..., 1,1) до тех пор, пока во втором справа разряде не получится О, т. е. пока не получится число Ь, Ь, .. уЬщ-г, О,*. При каждом таком вычитании четность числа будет изменяться на противоположную. Далее, полученное

число разделим на Sm i (оно делится нацело, поскольку в (т - 1)-м разряде стоит 0). При этом цифру т-то разряда определить нельзя, поскольку уже в исходном числе в т-м разряде стоит звездочка; цифру (т - 1)-го разряда нам также определить не удастся, и мы ее тоже заменим звездочкой. В остальных же разрядах правило деления обратно правилу умножения: к цифре нужно добавить целое количество {г) раз число s/так, чтобы rsi + fej делилось нацело на Smi, после чего выполнить деление. В результате получится число а\ аат-2, *, *, четность которого совпадаете четностью 6i,62,...,6m2,0,* и о котором известно, что оно меньше N/2sm-.i.

В следуюш,ем шаге из числа dp, а2\...,а?2*,* будем вычитать единицу до тех пор, пока в (т - 2)-м разряде не получится О (т. е. Ст-г раз). В реззльтате этих вьщитаний получим число bl, bi,..., 6m-3, О, *, *; при этом каждое вычитание единицы меняет четность числа на противоположную. Аналогично предыдущему разделим его затем на

Sm 2, в результате чего получится число dl, cli\...,dm-s, *, *, *, четность которого совпадает с четностью числа

bi \ b2\---,bm-3. О, *, * и о котором известно, что оно меньше W2Sm iSm-2.

Продолжим этот процесс до тех пор, пока не будет получено число а-~\ *, *, о котором известно, что оно меньше N/2sm-iSm-2---S2, т. е. меньшей! (поскольку

Вьиитая из Heroaf-2) раз единицу, получим нуль. Нуль- число четное. В зависимости от того, четным или нечетным было общее количество вычитаний в описанном выше процессе, соответственно четным или нечетным должно быть то из чисел ai,a2,...,am-i, *, которое меньше Л 2; сли цифра в т-м разряде исходного числа (Ст) совпадает с определенной таким образом четностью {йщ - остаток от деления на 2 - равен О для. четных чисел и 1 -для нечетных), то исходное число на самом деле меньше N/2; в противном случае оно больше или равло N/2.

Пример. Пусть Si = 7, = 5, Sg = 3, S4 = 2; Л/ = S1S2S3S4 = (210)io; W2 = (105)io. Задано число 40П. Меньше ли оно, чем iV/2?