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

Turbo в 09:07, 21 декабря 2015

2015-12-21T09:07:32Z

Turbo в 14:01, 20 ноября 2013

2013-11-20T14:01:32Z

Turbo в 14:00, 20 ноября 2013

2013-11-20T14:00:52Z

Turbo в 15:48, 23 апреля 2013

2013-04-23T15:48:16Z

Turbo в 06:43, 11 февраля 2013

2013-02-11T06:43:24Z

Turbo в 06:32, 6 февраля 2013

2013-02-06T06:32:06Z

Turbo в 07:29, 4 февраля 2013

2013-02-04T07:29:52Z

Turbo в 13:04, 30 января 2013

2013-01-30T13:04:53Z

Turbo в 13:03, 30 января 2013

2013-01-30T13:03:28Z

Turbo в 13:02, 30 января 2013

2013-01-30T13:02:39Z

@@ Строка 14: / Строка 14: @@
 : ...
 : <math>z_n \equiv (x_n + y_n) \pmod{m_n};</math>
 Аналогично выполняются вычитание, умножение и деление.
 == Недостатки системы остаточных классов ==

@@ Строка 30: / Строка 30: @@
 == Специальные системы модулей ==
 В модулярной арифметике существуют специальные наборы модулей, которые позволяют частично нивелировать недостатки и для которых существуют эффективные алгоритмы сравнения чисел и для прямого и обратного перевода модулярных чисел в позиционную систему счисления. Одной из самых популярных систем модулей является набор из трех взаимнопростых чисел вида '''{2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1}'''
 == Численный пример ==

@@ Строка 30: / Строка 30: @@
 == Специальные системы модулей ==
 В модулярной арифметике существуют специальные наборы модулей, которые позволяют частично нивелировать недостатки и для которых существуют эффективные алгоритмы сравнения чисел и для прямого и обратного перевода модулярных чисел в позиционную систему счисления. Одной из самых популярных систем модулей является набор из трех взаимнопростых чисел вида '''{2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1}'''
 == Выполнение арифметических операций ==

@@ Строка 19: / Строка 19: @@
 * Возможность представления только ограниченного количества чисел.
 * Отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям <math>(m_1, m_1\cdot m_2, \dots, m_1\cdot m_2\cdot\dots\cdot m_{n-1})</math>.
-* Сложные реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
+* Медленные и требующие работы с большими числами реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
 == Применение системы остаточных классов ==
@@ Строка 25: / Строка 27: @@
 * контроль за ошибками, за счет введения дополнительных избыточных модулей
 * высокая скорость работы, которую обеспечивает параллельная реализация базовых арифметических операций
 == Основные определения ==
@@ Строка 84: / Строка 89: @@
 Замечание: если бы мы умножали или складывали числа, которые дали в результате умножения число больше или равное <math>M = 30</math>, то полученный результат <math>RES \equiv REAL \pmod{M}</math>, где <math>REAL</math> - результат операции в позиционной системе счисления.
-== Литература ==
+=== Пример деления, при условии, что оно делится нацело ===
-# {{книга
+Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.
- |автор         = С. Ленг
+<br />
- |часть         =
+Для модулей <math>(29;31;32)</math> разделим число 1872 на 9.<br />
- |заглавие      = Алгебра
+Делим <math>1872=(16;12;16)</math> на <math>9=(9;9;9)</math>.<br />
- |оригинал      =
- |ссылка        =
+Воспользуемся формулой<br />
- |издание       =
+<math>z_i \equiv (x_i * y_i^{-1}) \pmod{m_i};</math>
- |ответственный =
+<br /><br />
- |место         =
+Здесь надо сказать, что <math>y_i^{-1}*y_i=1 \pmod{m_i}</math>, что не то же самое, что просто разделить x на y.<br />
- |издательство  = [[МИР]]
+По формуле <math>y_i^{m_i-1}=1 \pmod{m_i}</math> получаем<br />
- |год           = 1968
+<math>9^{29-2} \pmod{29} = 13</math><br />
- |том           =
+<math>9^{31-2} \pmod{31} = 7</math><br />
- |страницы      =
+<math>9^{32-2} \pmod{32} = 17</math><br />
- |страниц       = 564
- |isbn          =
- |ref           = Ленг
+<math>z_1 \equiv (16*13) \pmod{29} = 5</math><br />
-}}
+<math>z_2 \equiv (12*7) \pmod{31} = 22</math><br />

@@ Строка 8: / Строка 8: @@
 == Преимущества системы остаточных классов ==
 * В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в <math>[0,M-1]</math>.
 == Недостатки системы остаточных классов ==
@@ Строка 40: / Строка 47: @@
 == Численный пример ==
 Рассмотрим СОК с базисом <math>(2;3;5)</math>. В этом базисе можно взаимооднозначно представить числа из промежутка от <math>0</math> до <math>29</math>, так как <math>M = 2\times 3\times 5 = 30</math>. Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:
@@ Строка 58: / Строка 67: @@
 === Пример сложения ===
 === Пример умножения ===
 == Литература ==

← Предыдущая		Версия 06:32, 6 февраля 2013
Строка 39:		Строка 39:
	Пусть <math>X=Y\cdot Z</math>- полупростое число. Рассмотрим систему остаточных классов <math>p_i,\ldots, p_N</math>, где <math>p_i</math>— <math>i</math>-е простое число.		Пусть <math>X=Y\cdot Z</math>- полупростое число. Рассмотрим систему остаточных классов <math>p_i,\ldots, p_N</math>, где <math>p_i</math>— <math>i</math>-е простое число.

		+	== Численный пример ==
		+
		+	Рассмотрим СОК с базисом <math>(2;3;5)</math>. В этом базисе можно взаимооднозначно представить числа из промежутка от <math>0</math> до <math>29</math>, так как <math>M = 2\times 3\times 5 = 30</math>. Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:
		+	{\| class="wikitable"
		+	\|-
		+	\| <math>0=(0;0;0)</math> \|\| <math>1=(1;1;1)</math> \|\| <math>2=(0;2;2)</math> \|\| <math>3=(1;0;3)</math> \|\| <math>4=(0;1;4)</math>
		+	\|-
		+	\| <math>5=(1;2;0)</math> \|\| <math>6=(0;0;1)</math> \|\| <math>7=(1;1;2)</math> \|\| <math>8=(0;2;3)</math> \|\| <math>9=(1;0;4)</math>
		+	\|-
		+	\| <math>10=(0;1;0)</math> \|\| <math>11=(1;2;1)</math> \|\| <math>12=(0;0;2)</math> \|\| <math>13=(1;1;3)</math> \|\| <math>14=(0;2;4)</math>
		+	\|-
		+	\| <math>15=(1;0;0)</math> \|\| <math>16=(0;1;1)</math> \|\| <math>17=(1;2;2)</math> \|\| <math>18=(0;0;3)</math> \|\| <math>19=(1;1;4)</math>
		+	\|-
		+	\| <math>20=(0;2;0)</math> \|\| <math>21=(1;0;1)</math> \|\| <math>22=(0;1;2)</math> \|\| <math>23=(1;2;3)</math> \|\| <math>24=(0;0;4)</math>
		+	\|-
		+	\| <math>25=(1;1;0)</math> \|\| <math>26=(0;2;1)</math> \|\| <math>27=(1;0;2)</math> \|\| <math>28=(0;1;3)</math> \|\| <math>29=(1;2;4)</math>
		+	\|}
		+
		+	=== Пример сложения ===
		+
		+	=== Пример умножения ===

@@ Строка 1: / Строка 1: @@
 '''Система остаточных классов (СОК)''' (от англ. [http://en.wikipedia.org/wiki/Residue_number_system Residue number system], другое название '''Модулярная арифметика''') - [http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F#.D0.9D.D0.B5.D0.BF.D0.BE.D0.B7.D0.B8.D1.86.D0.B8.D0.BE.D0.BD.D0.BD.D1.8B.D0.B5_.D1.81.D0.B8.D1.81.D1.82.D0.B5.D0.BC.D1.8B_.D1.81.D1.87.D0.B8.D1.81.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F непозиционная система счисления]. Представление числа в системе остаточных классов основано на понятии [http://ru.wikipedia.org/wiki/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E вычета] и [http://ru.wikipedia.org/wiki/%D0%9A%D0%B8%D1%82%D0%B0%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE%D0%B1_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%B0%D1%85 китайской теореме об остатках]. СОК определяется набором [http://ru.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D0%B8%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0 взаимно простых] ''модулей'' <math>(m_1, m_2, \dots, m_n)</math> с произведением <math>M=m_1\cdot m_2\cdot \dots\cdot m_n</math> так, что каждому целому числу <math>x</math> из отрезка <math>[0,M-1]</math> ставится в соответствие набор вычетов <math>(x_1, x_2, \dots, x_n)</math>, где
-: <math>x \equiv x_1 \pmod{m_1};</math>
+: <math>x_1 \equiv x \pmod{m_1};</math>
-: <math>x \equiv x_2 \pmod{m_2};</math>
+: <math>x_2 \equiv x \pmod{m_2};</math>
 : …
-: <math>x \equiv x_n \pmod{m_n}.</math>
+: <math>x_n \equiv x \pmod{m_n}.</math>
 При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка <math>[0,M-1]</math>.