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

Материал из ТолВИКИ
Перейти к: навигация, поиск

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

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

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

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