Представление числа в системе остаточных классов
Представление чисел в виде набора остатков от деления на выбранные натуральные модули - основания системы называется системой остаточных классов - СОК (residue number system - RNS) или модулярной системой счисления - МСС (modular system).
Такие системы счисления являются непозиционными кодами с параллельной структурой, которые позволяют реализовать идею распараллеливания операций на уровне выполнения элементарных арифметических действий.
Пусть заданы положительные числа , которые называют основаниями или модулями системы. Обозначим .
Эта величина характеризует объём диапазона системы. Под системой остаточных классов понимают такую непозиционную систему счисления, в которой целое неотрицательное число А можно представить в виде набора остатков от деления этого числа на выбранные основания системы, т. е.
, где (1).
Возможность такого представления числа определяется теоремой о делении с остатком в кольце целых чисел. Напомним формулировку этой теоремы (в обозначениях этого раздела).
Теорема
Если , то существуют единственные , такие, что .
Несложно заметить, что каждый остаток получается независимо от других и содержит информацию обо всём числе.
Установить взаимно-однозначное соответствие между целыми числами из диапазона и их остатками позволяет китайская теорема об остатках.
Возможность применения СОК в вычислительных алгоритмах обуславливается наличием определённого изоморфизма между математическими операциями над целыми числами и соответствующими операциями над системой целых неотрицательных остатков по отдельным модулям. Причём сложение, умножение, возведение в целую положительную степень любых целых положительных чисел совершенно идентичны соответствующим операциям, выполняемым над системой остатков.
Пусть операнды и , а также результаты операций сложения и умножения и A\cdot B</math> представлены соответственно остатками
по основаниям , причём оба числа и результаты находятся в диапазоне , то есть
,
,
,
,
и
, , , .
Эти выражения можно переписать в виде
; ;
; ;
Справедливость этих правил выполнения арифметических действий в СОК непосредственно вытекает из свойств сравнения.
Действительно, равенства можно переписать в виде
.
Из представления и по теореме о делении с остатком следует, что
, ,
где , , .
Тогда , ,
Откуда .
В случае умножения
.
Тогда , .
Следовательно, .
Примеры
Дано:
.
.
Найти:
.
Решение:
.
.
.
.
Выводы
В отличие от позиционной системы счисления (ПСС), в которой число представляется в виде
, где – основание ПСС,
значение числа в модулярном коде не зависит от местоположения каждого разряда в его представлении, а зависит от значения основания соответствующего разряда. Поэтому модулярный код является непозиционным. Таким образом, выполнение арифметических операций в модулярном коде производится независимо по каждому из модулей, что и указывает на параллелизм данной системы. Это обстоятельство определяет поразрядное выполнение операций. Это свойство избавит от необходимости «занимать» или «переносить» единицу старшего разряда, что приводит к появлению кодов с параллельной структурой. Это позволяет распараллелить алгоритмы при выполнении арифметических операций.
Перевод чисел из ПСС в СОК при помощи выражения (1) связан с реализацией операции деления, поэтому использование данного метода неэффективно. Итак, операции сложения и умножения над числами, представленными в СОК, сводятся к соответствующим операциям над цифрами этого представления. Это относится и к возведению в степень, к вычислению значений многочлена и т. п. Операция вычитания в СОК заменяется сложением с аддитивной инверсией отрицательного числа. Все эти операции модульные, т. е. не требуют позиционных характеристик обрабатываемых чисел.