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

Версия 12:13, 8 октября 2014

Представление чисел в виде набора остатков от деления на выбранные натуральные модули - основания системы называется системой остаточных классов - СОК (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).

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

Теорема

Если $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$ – основание ПСС,

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

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

@@ Строка 87: / Строка 87: @@
 '''Примеры'''
+Дано:
+<math>p_1=2, p_2=3, p_3=5, p_4=7</math>.
+<math>A=(0,0,3,4), B=(1,1,2,0)</math>.
+Найти:
+<math>A+B, A-B, A\cdot B</math>.
+Решение:
+<math>P=p_1 \cdot p_2 \cdot p_3 \cdot p_4 = 2 \cdot 3 \cdot 4 \cdot 7 = 210</math>.
+<math>A+B = (0, 0, 3, 4) + (1, 1, 2, 0) = (1, 1, 0, 4)</math>.
+<math>A\cdot B = (0, 0, 3, 4) \cdot (1, 1, 2, 0) = (0, 0, 1, 0)</math>.
+<math>A-B = (0, 0, 3, 4) - (1, 1, 2, 0) = (1, 2, 1, 4)</math>.
 '''Выводы'''
-В отличие от позиционной системы счисления (ПСС), значение числа в модулярном коде не зависит от местоположения каждого разряда в его представлении, а зависит от значения основания соответствующего разряда. Поэтому модулярный код является непозиционным.
+В отличие от позиционной системы счисления (ПСС),
+в которой число <math>A</math> представляется в виде
+<math>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</math>,
+где <math>N</math> – основание ПСС,
+значение числа в модулярном коде не зависит от местоположения каждого разряда в его представлении, а зависит от значения основания соответствующего разряда. Поэтому модулярный код является непозиционным.
 Таким образом, выполнение арифметических операций в модулярном коде производится независимо по каждому из модулей, что и указывает на параллелизм данной системы. Это обстоятельство определяет поразрядное выполнение операций. Это свойство избавит от необходимости «занимать» или «переносить» единицу старшего разряда, что приводит к появлению кодов с параллельной структурой. Это позволяет распараллелить алгоритмы при выполнении арифметических операций.
 Перевод чисел из ПСС в СОК при помощи выражения (1) связан с реализацией операции деления, поэтому использование данного метода неэффективно.
 Итак, операции сложения и умножения над числами, представленными в СОК, сводятся к соответствующим операциям над цифрами этого представления. Это относится и к возведению в степень, к вычислению значений многочлена и т. п. Операция вычитания в СОК заменяется сложением с аддитивной инверсией отрицательного числа. Все эти операции модульные, т. е. не требуют позиционных характеристик обрабатываемых чисел.

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

Версия 12:13, 8 октября 2014

Персональные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация