Представление числа в системе остаточных классов

Представление чисел в виде набора остатков от деления на выбранные натуральные модули - основания системы называется системой остаточных классов - СОК (residue number system - RNS) или модулярной системой счисления - МСС (modular system).

Такие системы счисления являются непозиционными кодами с параллельной структурой, которые позволяют реализовать идею распараллеливания операций на уровне выполнения элементарных арифметических действий.

Пусть заданы положительные числа $p_1, p_2,\ldots , p_n$, которые называют основаниями или модулями системы. Обозначим $p= p_1 \cdot p_2 \cdot \ldots \cdot p_n$.

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

$A = a_1, a_2 , \ldots , a_n$, где $a_i = A-[ \frac {A}{p_i}]\cdot p_i, i=1,\ldots ,n$ (1).

Возможность такого представления числа определяется теоремой о делении с остатком в кольце целых чисел.

Перевод чисел из ПСС в СОК при помощи выражения (1) связан с реализацией операции деления, поэтому использование данного метода неэффективно. В разделе Алгоритмы перехода от позиционного представления к остаткам рассмотрены эффективные методы перехода к остаткам.

Напомним формулировку теоремы о делении с остатком (в обозначениях этого раздела).

Теорема

Если $A\in Z, p\in Z, p\neq 0$, то существуют единственные $q\in Z, a\in Z$, такие, что $A=qp+a, 0 \le a < |p|, q=[\frac {A}{p}]$.

Несложно заметить, что каждый остаток $a_i$ получается независимо от других и содержит информацию обо всём числе. Установить взаимно-однозначное соответствие между целыми числами из диапазона $[0, P)$ и их остатками позволяет китайская теорема об остатках. Возможность применения СОК в вычислительных алгоритмах обуславливается наличием определённого изоморфизма между математическими операциями над целыми числами и соответствующими операциями над системой целых неотрицательных остатков по отдельным модулям. Причём сложение, умножение, возведение в целую положительную степень любых целых положительных чисел совершенно идентичны соответствующим операциям, выполняемым над системой остатков.

Пусть операнды $A$ и $B$, а также результаты операций сложения и умножения $A+B$ и A\cdot B</math> представлены соответственно остатками

$a_i, b_i, c_i, d_i$ по основаниям $p_i, i=1,|ldots,n$, причём оба числа и результаты находятся в диапазоне $[0, P)$, то есть

$A=(a_1, a_2, \ldots , a_n)$,

$B=(b_1, b_2, \ldots , b_n)$,

$A+B=(c_1, c_2, \ldots , c_n)$,

$D=(d_1, d_2, \ldots , d_n)$,

и

$0\le A<P$, $0\le B<P$, $0\le A+B<P$, $0\le A\cdot B<P$.

Эти выражения можно переписать в виде

$c_i=a_i+b_i\pmod{p_i}$; $d_i=a_i\cdot b_i\pmod{p_i}$;

$c_i=a_i+b_i - [\frac{a_i+b_i}{p_i}]$; $d_i=a_i\cdot b_i - [\frac{a_i\cdot b_i}{p_i}]$;

Справедливость этих правил выполнения арифметических действий в СОК непосредственно вытекает из свойств сравнения.

Действительно, равенства можно переписать в виде

$c_i=A+B - [\frac{A+B}{p_i}], i=1,\ldots ,n$.

Из представления $A$ и $B$ по теореме о делении с остатком следует, что

$A=k_i\cdot p_i+a_i$, $B=l_i\cdot p_i+b_i$,

где $i=1,\ldots ,n$, $k_i\in Z, k_i\ge 0$, $l_i\in Z, l_i\ge 0$.

Тогда $A+B=(k_i+l_i)\cdot p_i + a_i + b_i$, $[\frac{A+B}{p_i}]=k_i+l_i + [\frac{a_i + b_i}{p_i}]\cdot p_i$,

Откуда $c_i = a_i+b_i- [\frac{a_i + b_i}{p_i}]\cdot p_i$.

В случае умножения

$d_i = a_i\cdot b_i- [\frac{A\cdot B}{p_i}]\cdot p_i$.

Тогда $A\cdot B=k_i\cdot l_i\cdot {p_i}^2 + (a_i\cdot l_i + b_i\cdot k_i)\cdot p_i + a_i\cdot b_i$, $[\frac{A\cdot B}{p_i}]=k_i\cdot l_i\cdot p_i + a_i\cdot l_i + b_i\cdot k_i + \frac{a_i\cdot b_i}{p_i}$.

Следовательно, $d_i = a_i\cdot b_i- [\frac{a_i\cdot b_i}{p_i}]\cdot p_i, (i=1,\ldots , n)$.

Примеры

Дано:

$p_1=2, p_2=3, p_3=5, p_4=7$.

$A=(0,0,3,4), B=(1,1,2,0)$.

Найти:

$A+B, A-B, A\cdot B$.

Решение:

$P=p_1 \cdot p_2 \cdot p_3 \cdot p_4 = 2 \cdot 3 \cdot 4 \cdot 7 = 210$.

$A+B = (0, 0, 3, 4) + (1, 1, 2, 0) = (1, 1, 0, 4)$.

$A\cdot B = (0, 0, 3, 4) \cdot (1, 1, 2, 0) = (0, 0, 1, 0)$.

$A-B = (0, 0, 3, 4) - (1, 1, 2, 0) = (1, 2, 1, 4)$.

Выводы

В отличие от позиционной системы счисления (ПСС), в которой число $A$ представляется в виде

$A = A_n \cdot N^n + A_{n-1} \cdot N^{n-1} + \ldots + A_0 \cdot N^0 = \sum_{i = 0}^{n} A_i \cdot N^i$, где $N$ – основание ПСС,

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

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

Исследования СОК выявили целый ряд её преимуществ.

• Максимальный параллелизм. Для оценки уровня параллелизма системы счисления вводится специальный показатель

$\Pi(\nu) = \frac {n(\nu)}{k}$,

где $k$ – длина кода системы, $n(\nu)$ – количество поразрядных показателей параллелизма ${\pi}_1, {\pi}_2, \ldots, {\pi}_k$, не меньших заданного порога $\nu : \frac{1}{k} \le \nu \le 1$, причём ${\pi}_i=1-\frac{n_i}{k}, i=1,\ldots,k$, где $n_i$ максимально возможное число пар цифр $(x_j, y_j), j=1,2,\ldots,i-1,i+1,\ldots,k$, оказывающих влияние на значение суммы $Z=X+Y$ в ходе её формирования на языке данного кода. Для СОК показатель параллелизма принимает максимально возможное значение $\Pi(1)=1$. Это говорит об отсутствии межразрядных связей в числе, записанном в СОК.

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

• Реализация принципа конвейерной обработки информации.

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

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