Система остаточных классов

Материал из ТолВИКИ
(Различия между версиями)
Перейти к: навигация, поиск
 
(не показаны 7 промежуточных версий 1 участника)
Строка 1: Строка 1:
Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей (m1,m2....mn) с произведением M=m1*m2*mn  так, что каждому целому числу x из отрезка [0,M − 1] ставится в соответствие набор вычетов (x1,x2....xn)
+
Автор-составитель:
При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [0,M − 1].
+
Русачкова Елена
 +
 
 +
Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей [[Изображение:123.png]] с произведением [[Изображение:234.png]] так, что каждому целому числу x из отрезка [0,M − 1] ставится в соответствие набор вычетов [[Изображение:345.png]]При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [0,M − 1].
 +
[[Изображение:456.png]]
 +
[[Изображение:567.png]]
  
 
В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [0,M − 1].
 
В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [0,M − 1].
  
Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основани
+
Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям [[Изображение:678.png]]
[[Изображение:сок.png]]
+
 
 +
Перевод чисел из СОК в десятичную систему счисления
 +
Формула перевода имеет вид:
 +
 
 +
 
 +
A = a1*B1+a2*B2+…+an*Bn-r*P, где a1, …, an
 +
— представление числа А в СОК с основаниями p
 +
1, p2, …, pn;
 +
P = p1* p2* …* pn;
 +
 
 +
r = 0,1,2,… (целые числа), причём r выбирают так, чтобы разность между левой и правой частью выражения была меньше P;
 +
 
 +
 
 +
Bi = (P/pi)*ki, где ki = 1, 2, …, pi
 +
, причём
 +
ki
 +
выбирается таким, чтобы остаток от деления
 +
Bi/pi
 +
был равен 1.
 +
Пример:
 +
 
 +
 
 +
А = (2,4,6) в системе с основаниями: p1 = 3, p2 = 5, p3 = 7.
 +
P = p1*p2*p3 = 3*5*7 = 105.
 +
 
 +
B1 = 105/3*k1 = 35*2 =70;
 +
 
 +
B2 = 105/5*k2 = 21*1 =21;
 +
 
 +
B3 = 105/7*k3 = 15*1 =15;
 +
 
 +
A = 2*70+4*21+6*15 — r*105;
 +
 
 +
A = 314 — r*105 = 104, где r=2.
 +
 
 +
 
 +
--------------------------------------------------------------------------------
 +
 
 +
 
 +
[[Категория:Информатика и ИКТ]]
 +
[http://master-test.net/ru/teacher/quiz/editor/run/1/id/9875#quiz_item_1 тест]

Текущая версия на 12:55, 28 сентября 2011

Автор-составитель: Русачкова Елена

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей 123.png с произведением 234.png так, что каждому целому числу x из отрезка [0,M − 1] ставится в соответствие набор вычетов 345.pngПри этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [0,M − 1]. 456.png 567.png

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [0,M − 1].

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям 678.png

Перевод чисел из СОК в десятичную систему счисления Формула перевода имеет вид:


A = a1*B1+a2*B2+…+an*Bn-r*P, где a1, …, an — представление числа А в СОК с основаниями p 1, p2, …, pn; P = p1* p2* …* pn;

r = 0,1,2,… (целые числа), причём r выбирают так, чтобы разность между левой и правой частью выражения была меньше P;


Bi = (P/pi)*ki, где ki = 1, 2, …, pi , причём ki выбирается таким, чтобы остаток от деления Bi/pi был равен 1. Пример:


А = (2,4,6) в системе с основаниями: p1 = 3, p2 = 5, p3 = 7. P = p1*p2*p3 = 3*5*7 = 105.

B1 = 105/3*k1 = 35*2 =70;

B2 = 105/5*k2 = 21*1 =21;

B3 = 105/7*k3 = 15*1 =15;

A = 2*70+4*21+6*15 — r*105;

A = 314 — r*105 = 104, где r=2.



тест

Личные инструменты
наши друзья
http://аудиохрестоматия.рф/