Числова система залишків

Числова́ систе́ма зали́шків (ЧСЗ, англ. Residue number system) — непозиційна система числення. Представлення числа в системі засноване на китайській теоремі про залишки, а операції з числами виконуються за правилами модульної арифметики. Використовується для представлення великих цілих чисел у вигляді набору невеликих цілих чисел, що дозволяє оптимізувати операції з великими цілими числами.

ЧСЗ визначається набором взаємно простих чисел ${\displaystyle (m_{1},m_{2},\dots ,m_{n})}$, які називаються базисом. Позначимо добуток базиса через ${\displaystyle M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n}}$. Тоді кожному цілому числу ${\displaystyle x}$ з відрізка ${\displaystyle [0,M-1]}$ ставиться у відповідність набір залишків ${\displaystyle (x_{1},x_{2},\dots ,x_{n})}$, де

${\displaystyle x_{i}\equiv x{\pmod {m_{i}}},\ i=1,\dots ,n.}$

Зауважимо, що китайська теорема про залишки гарантує однозначність представлення для чисел з відрізка ${\displaystyle [0,M-1]}$.

Якщо базис складається не з взаємно простих чисел, то його можна використовувати для представлення чисел з відрізка ${\displaystyle [0,M-1]}$, де ${\displaystyle M=HCK(m_{1},m_{2},\ldots ,m_{n})}$. НСК — це найменше спільне кратне.

Наприклад, в базисі  ${\displaystyle m_{1}=2,\ m_{2}=4}$ числа 3 і 7 однаково записуються:
${\displaystyle 3_{10}=(x_{1}=1,\ x_{2}=3)=(1,\ 3),}$
${\displaystyle 7_{10}=(x_{1}=1,\ x_{2}=3)=(1,\ 3).}$

Однакове представлення виникло тому, що найбільше число, яке може бути записане в цьому базисі, це найменше спільне кратне чисел (2, 4). НСК (2, 4)=4. Відповідно ${\displaystyle 3\equiv 7{\pmod {4}}}$.

У ЧСЗ арифметичні операції (додавання, віднімання, множення, ділення) виконуються поелементно, якщо про результат відомо, що він є цілочисловим і також лежить в ${\displaystyle [0,M-1]}$.

Нехай задані числа ${\displaystyle X}$ та ${\displaystyle Y}$, компоненти яких записуються як ${\displaystyle (x_{1},x_{2},\dots ,x_{n})}$ ${\displaystyle (y_{1},y_{2},\dots ,y_{n}))}$. Тоді

${\displaystyle Z=X\pm Y}$

обчислюється як

${\displaystyle z_{i}\equiv (x_{i}\pm y_{i}){\pmod {m_{i}}}}$.

Аналогічно виконується множення.

Можливе не для всіх чисел. По-перше, ${\displaystyle X/Y}$ повинно бути цілим числом. По-друге, поелементне ділення можна виконати лише за умови, що запис числа ${\displaystyle Y}$ не містить компонент рівних нулю ${\displaystyle (y_{i}\not =0)}$. Тоді компоненти числа

${\displaystyle Z=X:Y}$

обчислюються як

${\displaystyle z_{i}\equiv x_{i}\cdot y_{i}^{-1}{\pmod {m_{i}}},}$

де ${\displaystyle y_{i}^{-1}}$ — обернене за модулем число до ${\displaystyle y_{i}}$, тобто ${\displaystyle y_{i}\cdot y_{i}^{-1}\equiv 1{\pmod {m_{i}}}.}$

Алгоритм ділення у випадку коли дільник містить нульові елементи, можна знайти у статті [1].

• Обмеження на величину чисел.
• Відсутність ефективних алгоритмів для порівняння чисел, представлених у ЧСЗ. Порівняння зазвичай здійснюється через переклад аргументів з ЧСЗ у змішану систему числення з основами ${\displaystyle (m_{1},m_{1}\cdot m_{2},\dots ,m_{1}\cdot m_{2}\cdot \dots \cdot m_{n-1})}$.
• Повільні алгоритми перекладу з позиційної системи числення в ЧСЗ і назад.
• Складні алгоритми ділення.
• Труднощі у виявленні переповнення.

ЧСЗ широко використовується в мікроелектроніці в спеціалізованих пристроях — ALU, ЦОС, де потребується:

• Контроль за помилками, за рахунок введення додаткових надлишкових модулів.
• Висока швидкість роботи, яку забезпечує паралельна реалізація базових арифметичних операцій.

У модулярної арифметиці існують спеціальні набори модулів, які дозволяють частково нівелювати недоліки ЧСЗ і для яких існують ефективні алгоритми порівняння чисел та зворотного перекладу чисел в позиційну систему числення. Однією з найпопулярніших систем модулів є набір з трьох взаємно простих чисел вигляду {2ⁿ−1, 2ⁿ, 2ⁿ+1}

Розглянемо ЧСЗ з базисом ${\displaystyle (2;3;5)}$. У цьому базисі можна однозначно представити числа з проміжку від ${\displaystyle 0}$ до ${\displaystyle 29}$, так як ${\displaystyle M=2\times 3\times 5=30}$. Таблиця відповідності чисел з позиційної системи числення та системи залишкових класів:

${\displaystyle 0=(0;0;0)}$	${\displaystyle 1=(1;1;1)}$	${\displaystyle 2=(0;2;2)}$	${\displaystyle 3=(1;0;3)}$	${\displaystyle 4=(0;1;4)}$
${\displaystyle 5=(1;2;0)}$	${\displaystyle 6=(0;0;1)}$	${\displaystyle 7=(1;1;2)}$	${\displaystyle 8=(0;2;3)}$	${\displaystyle 9=(1;0;4)}$
${\displaystyle 10=(0;1;0)}$	${\displaystyle 11=(1;2;1)}$	${\displaystyle 12=(0;0;2)}$	${\displaystyle 13=(1;1;3)}$	${\displaystyle 14=(0;2;4)}$
${\displaystyle 15=(1;0;0)}$	${\displaystyle 16=(0;1;1)}$	${\displaystyle 17=(1;2;2)}$	${\displaystyle 18=(0;0;3)}$	${\displaystyle 19=(1;1;4)}$
${\displaystyle 20=(0;2;0)}$	${\displaystyle 21=(1;0;1)}$	${\displaystyle 22=(0;1;2)}$	${\displaystyle 23=(1;2;3)}$	${\displaystyle 24=(0;0;4)}$
${\displaystyle 25=(1;1;0)}$	${\displaystyle 26=(0;2;1)}$	${\displaystyle 27=(1;0;2)}$	${\displaystyle 28=(0;1;3)}$	${\displaystyle 29=(1;2;4)}$

Складемо два числа 12 і 7 у базисі ${\displaystyle (2;3;5)}$. Їх представлення в заданому базисі ${\displaystyle 12=(0;0;2)}$ i ${\displaystyle 7=(1;1;2)}$ (див. таблицю вище). Скористаємося формулою для складання: ${\displaystyle (z_{1},z_{2},z_{3})=(0,0,2)+(1,1,2)}$

${\displaystyle z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}}\equiv (0+1){\pmod {2}}=1;}$

${\displaystyle z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}}\equiv (0+1){\pmod {3}}=1;}$

${\displaystyle z_{3}\equiv (x_{3}+y_{3}){\pmod {m_{3}}}\equiv (2+2){\pmod {5}}=4;}$

${\displaystyle (z_{1},z_{2},z_{3})=(1,1,4)}$ — за таблицею переконуємося, що результат дорівнює 19.

Помножимо два числа 3 і 7 в базисі ${\displaystyle (2;3;5)}$. Їх представлення в заданому базисі ${\displaystyle 3=(1;0;3)}$ та ${\displaystyle 7=(1;1;2)}$ (див. таблицю вище). Скористаємось формулою для множення:

${\displaystyle z_{1}\equiv (x_{1}*y_{1}){\pmod {m_{1}}}\equiv (1*1){\pmod {2}}=1;}$

${\displaystyle z_{2}\equiv (x_{2}*y_{2}){\pmod {m_{2}}}\equiv (0*1){\pmod {3}}=0;}$

${\displaystyle z_{3}\equiv (x_{3}*y_{3}){\pmod {m_{3}}}\equiv (3*2){\pmod {5}}=1;}$

${\displaystyle (z_{1},z_{2},z_{3})=(1,0,1)}$ — за таблицею переконуємося, що результат дорівнює 21.

Зауваження: якби множити або складати числа, які дають в результаті число більше або рівне ${\displaystyle M=30}$, то отриманий результат збігатиметься по модулю числа ${\displaystyle {M}}$ з результатом операції в позиційній системі числення. При відніманні це правильно, коли отримуємо від'ємне число.