Представление числа в системе остаточных классов — различия между версиями

Версия 12:33, 11 сентября 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$ .

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

Теорема

Если $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}]$ ;

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

@@ Строка 43: / Строка 43: @@
 <math>0\le A<P</math>, <math>0\le B<P</math>, <math>0\le A+B<P</math>, <math>0\le A\cdot B<P</math>.
+Эти выражения можно переписать в виде
+<math>c_i=a_i+b_i\pmod{p_i}</math>;
+<math>d_i=a_i\cdot b_i\pmod{p_i}</math>;
+<math>c_i=a_i+b_i - [\frac{a_i+b_i}{p_i}]</math>;
+<math>d_i=a_i\cdot b_i - [\frac{a_i\cdot b_i}{p_i}]</math>;
+Справедливость этих правил выполнения арифметических действий в СОК непосредственно вытекает из свойств сравнения.

Представление числа в системе остаточных классов — различия между версиями

Версия 12:33, 11 сентября 2014

Навигация

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

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

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты