Представление числа в системе остаточных классов - История изменений

Isaeva в 14:02, 17 декабря 2014

2014-12-17T14:02:23Z

Isaeva в 13:20, 8 октября 2014

2014-10-08T13:20:50Z

Isaeva в 09:13, 8 октября 2014

2014-10-08T09:13:38Z

Isaeva: Isaeva переименовал страницу Представление числа в системе остаточных класов в Представление числа в системе остаточных классов: испр…

2014-10-08T08:39:53Z

Isaeva переименовал страницу Представление числа в системе остаточных класов в Представление числа в системе остаточных классов: испр…

Isaeva в 12:58, 11 сентября 2014

2014-09-11T12:58:56Z

Isaeva в 12:33, 11 сентября 2014

2014-09-11T12:33:24Z

Isaeva: Новая страница: «Представление чисел в виде набора остатков от деления на выбранные натуральные модули - …»

2014-09-11T12:26:18Z

Новая страница: «Представление чисел в виде набора остатков от деления на выбранные натуральные модули - …»

Новая страница

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

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

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

Эта величина характеризует объём диапазона системы. Под системой остаточных классов понимают такую непозиционную систему счисления, в которой целое неотрицательное число А можно представить в виде набора остатков от деления этого числа на выбранные основания системы, т. е.
<math>A = a_1, a_2 , \ldots , a_n</math>, где <math>a_i = A-[ \frac {A}{p_i}]\cdot p_i, i=1,\ldots ,n</math>.

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

'''Теорема'''

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

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

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

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

<math>A=(a_1, a_2, \ldots , a_n)</math>,

<math>B=(b_1, b_2, \ldots , b_n)</math>,

<math>A+B=(c_1, c_2, \ldots , c_n)</math>,

<math>D=(d_1, d_2, \ldots , d_n)</math>,

и

<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>.

@@ Строка 11: / Строка 11: @@
 <math>A = a_1, a_2 , \ldots  , a_n</math>, где <math>a_i = A-[ \frac {A}{p_i}]\cdot p_i, i=1,\ldots ,n</math> (1).
-Возможность такого представления числа определяется [[Теорема о делении с остатком |теоремой о делении с остатком в кольце целых чисел]].
+Возможность такого представления числа определяется [[Теорема о делении с остатком. Алгоритм Евклида|теоремой о делении с остатком в кольце целых чисел]].
 Перевод чисел из ПСС в СОК при помощи выражения (1) связан с реализацией операции деления, поэтому использование данного метода неэффективно. В разделе [[Алгоритмы перехода от позиционного представления к остаткам|Алгоритмы перехода от позиционного представления к остаткам]] рассмотрены эффективные методы перехода к остаткам.

@@ Строка 11: / Строка 11: @@
 <math>A = a_1, a_2 , \ldots  , a_n</math>, где <math>a_i = A-[ \frac {A}{p_i}]\cdot p_i, i=1,\ldots ,n</math> (1).
-Возможность такого представления числа определяется [[Теорема о делении с остатком |теоремой о делении с остатком в кольце целых чисел]]. Напомним формулировку этой теоремы (в обозначениях этого раздела).
+Возможность такого представления числа определяется [[Теорема о делении с остатком |теоремой о делении с остатком в кольце целых чисел]].
 '''Теорема'''
@@ Строка 121: / Строка 125: @@
 Таким образом, выполнение арифметических операций в модулярном коде производится независимо по каждому из модулей, что и указывает на параллелизм данной системы. Это обстоятельство определяет поразрядное выполнение операций. Это свойство избавит от необходимости «занимать» или «переносить» единицу старшего разряда, что приводит к появлению кодов с параллельной структурой. Это позволяет распараллелить алгоритмы при выполнении арифметических операций.
 Итак, операции сложения и умножения над числами, представленными в СОК, сводятся к соответствующим операциям над цифрами этого представления. Это относится и к возведению в степень, к вычислению значений многочлена и т. п. Операция вычитания в СОК заменяется сложением с аддитивной инверсией отрицательного числа. Все эти операции модульные, т. е. не требуют позиционных характеристик обрабатываемых чисел.

@@ Строка 87: / Строка 87: @@
 '''Примеры'''
 '''Выводы'''
-В отличие от позиционной системы счисления (ПСС), значение числа в модулярном коде не зависит от местоположения каждого разряда в его представлении, а зависит от значения основания соответствующего разряда. Поэтому модулярный код является непозиционным.
+В отличие от позиционной системы счисления (ПСС),
 Таким образом, выполнение арифметических операций в модулярном коде производится независимо по каждому из модулей, что и указывает на параллелизм данной системы. Это обстоятельство определяет поразрядное выполнение операций. Это свойство избавит от необходимости «занимать» или «переносить» единицу старшего разряда, что приводит к появлению кодов с параллельной структурой. Это позволяет распараллелить алгоритмы при выполнении арифметических операций.
 Перевод чисел из ПСС в СОК при помощи выражения (1) связан с реализацией операции деления, поэтому использование данного метода неэффективно.
 Итак, операции сложения и умножения над числами, представленными в СОК, сводятся к соответствующим операциям над цифрами этого представления. Это относится и к возведению в степень, к вычислению значений многочлена и т. п. Операция вычитания в СОК заменяется сложением с аддитивной инверсией отрицательного числа. Все эти операции модульные, т. е. не требуют позиционных характеристик обрабатываемых чисел.

← Предыдущая		Версия 12:33, 11 сентября 2014
Строка 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>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>;
		+
		+	Справедливость этих правил выполнения арифметических действий в СОК непосредственно вытекает из свойств сравнения.

← Предыдущая	Версия 08:39, 8 октября 2014
(нет различий)

@@ Строка 8: / Строка 8: @@
 Эта величина характеризует объём диапазона системы. Под системой остаточных классов понимают такую непозиционную систему счисления, в которой целое неотрицательное число А можно представить в виде набора остатков от деления этого числа на выбранные основания системы, т. е.
 <math>A = a_1, a_2 , \ldots  , a_n</math>, где <math>a_i = A-[ \frac {A}{p_i}]\cdot p_i, i=1,\ldots ,n</math>.
 Возможность такого представления числа определяется [[Теорема о делении с остатком |теоремой о делении с остатком в кольце целых чисел]]. Напомним формулировку этой теоремы (в обозначениях этого раздела).
@@ Строка 53: / Строка 54: @@
 Справедливость этих правил выполнения арифметических действий в СОК непосредственно вытекает из свойств сравнения.