7.3. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

При однозначном изображении диапазон допустимых в СОК чисел определяется соотношением

где — произведение всех весов разрядов, называемое периодом

Для доказательства этого положения возьмем взаимно простые числа при этом из трех последних образуем модули, имеющие общий делитель:

Для двух чисел А и В, представленных в можно тогда записать:

Предположим, что числа А и В записаны в СОК одинаково, т. е. представлены одинаковыми цифрами. Тогда

Следовательно,

Так как все есть взаимно простые числа, то эти равенства могут быть удовлетворены только при условии:

где какие-то целочисленные коэффициенты. Отсюда следует

так как очевидно, что Поэтому или

При имеем , при если при этом и то Таким образом, произведение взаимно простых чисел (модулей) определяет диапазон однозначно представимых чисел от 0 до Числа, отличающиеся друг от друга на величину представляются в СОК одинаково. Далее, не имеет смысла брать модули, имеющие общий делитель, так как при этом не происходит увеличения диапазона представимых чисел. Количество разрядов, однако, уменьшится, но эти разряды будут иметь большее основание, что не выгодно из-за усложнения схем.

Следует отметить, что в СОК необязательно в качестве модулей брать простые числа в их естественной последовательности Для обеспечения достаточно большого диапазона представимых чисел необходимо выбирать модули-основания, достаточно большие по величине, причем только один из них может быть четным. Например, если взять модули 38, 41, 43, 53, 59, то будет обеспечено представление чисел в диапазоне .

СОК допускает расширение или сокращение набора оснований, не искажая при этом исходное число. Так, если в СОК с весами брать число то, введя новые веса и то же А - изображается в виде

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

Знак числа в СОК может быть задан несколькими способами. Обычно отрицательное число представляют как дополнение его модуля до М, т. е. Так как то изменение знака числа можно реализовать путем вычитания заданного числа из нуля, т. е. путем вычитания вычета из нуля с последующим его дополнением до по Тогда в качестве положительных чисел можно взять числа натурального ряда, лежащие на отрезке т. е. интервал представления целых чисел со знаком составляет

Пример. Для требуется представить числа Так как то диапазон представления положительных чисел есть отрицательных от —15 до —1

Число В представляется в виде дополнения до М, т. е. Тогда Если т. е. (0,02), то А получим следующим образом:

В СОК так же, как и счет, поразрядными являются арифметические операции сложения, вычитания и умножения. Они базируются на следующих свойствах сравнений.

К Сравнения можно почленно складывать. Если

то с учетом того что получим

Отсюда следует, что слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, поменяв при этом его знак, т. е.

или

2 Два числа, сравнимые с третьим числом, сравнимы и между собой если

то

3. Сравнения можно почленно перемножать. Пусть

Это можно представить в алгебраической форме

После умножения получаем где — частное от деления произведения на

В общем случае имеем

Отсюда следует, что обе части сравнения можно умножить на одно и то же же целое число.

Если

4. Из свойства 3 следует также, что сравнения можно возводить в степень. Если то Из свойства 4 следует, что над сравнениями можно произвести операцию извлечения корня степени.

Значение этих свойств состоит в том, что при рассмотрении различных числовых арифметических выражений входящие в эти

выражения числа можно заменять на другие, сравнимые с ними по данному модулю 5. В частности, каждое число может быть заменено своим вычетом. Поэтому в СОК арифметические операции сложения, вычитания и умножения являются поразрядными.

При

т. е. необходимо сначала произвести умножение вычетов, а затем деление произведения на . Таким образом, остаток от деления суммы, разности и произведения двух чисел на равен соответственно сумме, разности и произведению по модулю остатков от деления на исходных чисел.

Пример. Перевести числа в Найти их сумму, разность и произведение:

Перевод числа А из однородной позиционной системы счисления с основанием Р в систему остаточных классов может производиться различными способами. Один из алгоритмов перевода состоит в том, что число А делится последовательно на модули каждый из которых представлен в -ичной позиционной системе счисления. Деление производится по правилам -ичной арифметики. Полученные значения остатков а представляются также в -ичной системе счисления. По-другому алгоритму перевода все действия выполняются по правилам арифметики остаточных классов. Каждая цифра -ичной системы счисления и основание представляются в системе остаточных классов, т. е.

Затем в общее выражение полинома, который задает значение числа А в однорорной позиционной системе, подставляются эти значения и

полином вычисляется по схеме Горнера по правилам умножения и сложения в системе остаточных классов.

Пример. Для числа найти изображение в

Так как то А не выходит из области допустимых чисел. По условию имеем: .

Для перевода необходимо вычислить полином

Если последовательно определять вычеты от числа по модулям 2, 3, 5, получим тот же результат.

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

Число представим как произведение на число которое имеет только один единичный ненулевой вычет, занимающий -й-разряд.

Тогда

Векторам, имеющим один единичный вычет, соответствуют определенные численные значения, которые заранее известны и представляются в -ичноЙ системе счисления так же, как и Тогда, выполнив действия в соответствии с выражением (7.4) по правилам -ичной арифметики, получим промежуточный результат перевода числа А из в -ичную систему счисления. Для получения окончательного результата необходимо найги вычет от полученного числа по модулю М.

Пример. Заданы числа и в системе вычетов по моду Перевести эти числа в десятичную систему счисления?!

Для данного случая Численный эквивалент вектора есть 15, вектора , вектора Тогда согласно (7.4) получим

Тик то для получения В необходимо еще найти но . Тогда окончательно имеем

Гак как желательно, чтобы М было возможно большим, можно модули выбирать следующим образом: — наибольшее нечетное число, соответствующее машинному слову; — наибольшее нечетное число взаимно простое с — наибольшее нечетное число взаимно простое с пока не будет набрано количество достаточное для образования требуемого М.

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

следующим образом:

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

Достоинство СОК заключается в том, что результат, получаемый при сложении, вычитании и умножении цифр в любом из разрядов, никак не зависит от результатов аналогичных операций в других разрядах чисел Следовательно, операции во всех разрядах можно реализовать одновременно и независимо друг от друга, что значительно увеличивает скорость их выполнения по сравнению с позиционной системой счисления. Причем, они могут быть реализованы сравнительно простыми техническими средствами (например, таблицами), так как количество возможных остатков при делении числа на небольшое по величине основание ограничено.

К основным недостаткам символических систем счисления вообще и СОК в частности относятся:

а) отсутствие удобного способа сравнения чисел, так как поразрядное сравнение не дает требуемой информации;

б) затруднение перевода из позиционной системы счисления в СОК, еще сложнее обратный перевод;

в) осутствие простого алгоритма деления;

г) сложность выполнения операций, которые требуют округления результата;

д) отсутствие удобного способа определения переполнения разрядной сетки машины, так как все операции в СОК являются поразрядными

СОК применяется в специализированных вычислительных машинах, для которых: 1) одним из основных требований является получение высокого быстродействия; 2) диапазон исходных чисел и промежуточных результатов строго фиксирован; 3) операция деления встречается крайне редко. Кроме того, СОК применяется в ЭВМ для контроля цепей передачи и переработки информации.