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

Материал из ТолВИКИ
(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
Автор-составитель:
 +
Русачкова Елена
 +
 
Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей [[Изображение:123.png]]  с произведением [[Изображение:234.png]] так, что каждому целому числу x из отрезка [0,M − 1] ставится в соответствие набор вычетов [[Изображение:345.png]]При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [0,M − 1].
 
Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей [[Изображение:123.png]]  с произведением [[Изображение:234.png]] так, что каждому целому числу x из отрезка [0,M − 1] ставится в соответствие набор вычетов [[Изображение:345.png]]При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [0,M − 1].
 
[[Изображение:456.png]]
 
[[Изображение:456.png]]
Строка 6: Строка 9:
  
 
Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям [[Изображение:678.png]]
 
Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям [[Изображение:678.png]]
 +
 +
[[Категория:Информатика и ИКТ]]

Версия 12:25, 28 сентября 2011

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

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

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

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

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