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

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

Визначення

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

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

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

Не простий базис

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

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

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

Арифметичні операції

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

Додавання, віднімання та множення

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

$Z=X\pm Y$

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

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

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

Ділення

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

$Z=X:Y$

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

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

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

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

Недоліки числової системи залишків

• Обмеження на величину чисел.
• Відсутність ефективних алгоритмів для порівняння чисел, представлених у ЧСЗ. Порівняння зазвичай здійснюється через переклад аргументів з ЧСЗ у змішану систему числення з основами $(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}

Приклади

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

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

Приклад додавання

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

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

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

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

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

Приклад множення

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

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

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

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

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

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