Система остаточных классов
| Строка 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
Автор-составитель: Русачкова Елена
Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей 
с произведением 
так, что каждому целому числу x из отрезка [0,M − 1] ставится в соответствие набор вычетов 
При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [0,M − 1].
В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [0,M − 1].
Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям 
