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

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

Визначення

ЧСЗ визначається набором взаємно простих чисел $(m_1,m_2,\dots ,m_n)$, які називаються базисом. Позначимо добуток базиса через $M=m_1\cdot m_2\cdot \dots \cdot m_n$. Тоді кожному цілому числу $x$ з відрізка $[0,M-1]$ ставиться у відповідність набір залишків $(x_1,x_2,\dots ,x_n)$, де

$x_i\equiv x(\mathrm{mod}{m}_i),i=1,\dots ,n.$

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

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

Якщо базис складається не з взаємно простих чисел, то його можна використовувати для представлення чисел з відрізка $[0,M-1]$, де $M=HCK(m_1,m_2,\dots ,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(\mathrm{mod}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)(\mathrm{mod}{m}_i)$.

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

Ділення

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

$Z=X:Y$

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

$z_i\equiv x_i\cdot y_i^{-1}(\mathrm{mod}{m}_i),$

де $y_i^{-1}$ — обернене за модулем число до $y_i$, тобто $y_i\cdot y_i^{-1}\equiv 1(\mathrm{mod}{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)(\mathrm{mod}{m}_1)\equiv (0+1)(\mathrm{mod}2)=1;$

$z_2\equiv (x_2+y_2)(\mathrm{mod}{m}_2)\equiv (0+1)(\mathrm{mod}3)=1;$

$z_3\equiv (x_3+y_3)(\mathrm{mod}{m}_3)\equiv (2+2)(\mathrm{mod}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)(\mathrm{mod}{m}_1)\equiv (1*1)(\mathrm{mod}2)=1;$

$z_2\equiv (x_2*y_2)(\mathrm{mod}{m}_2)\equiv (0*1)(\mathrm{mod}3)=0;$

$z_3\equiv (x_3*y_3)(\mathrm{mod}{m}_3)\equiv (3*2)(\mathrm{mod}5)=1;$

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

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