Числова́ систе́ма зали́шків (ЧСЗ, англ. Residue number system) — непозиційна система числення. Представлення числа в системі засноване на китайській теоремі про залишки, а операції з числами виконуються за правилами модульної арифметики. Використовується для представлення великих цілих чисел у вигляді набору невеликих цілих чисел, що дозволяє оптимізувати операції з великими цілими числами.
ЧСЗ визначається набором взаємно простих чисел
, які називаються базисом. Позначимо добуток базиса через
. Тоді кожному цілому числу
з відрізка
ставиться у відповідність набір залишків
, де
![{\displaystyle x_{i}\equiv x{\pmod {m_{i}}},\ i=1,\dots ,n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3481b69ecab1304c6c1f4b7619abae0a24139b35)
Зауважимо, що китайська теорема про залишки гарантує однозначність представлення для чисел з відрізка
.
Якщо базис складається не з взаємно простих чисел, то його можна використовувати для представлення чисел з відрізка
, де
. НСК — це найменше спільне кратне.
Наприклад, в базисі
числа 3 і 7 однаково записуються:
Однакове представлення виникло тому, що найбільше число, яке може бути записане в цьому базисі, це найменше спільне кратне чисел (2, 4). НСК (2, 4)=4. Відповідно
.
У ЧСЗ арифметичні операції (додавання, віднімання, множення, ділення) виконуються поелементно, якщо про результат відомо, що він є цілочисловим і також лежить в
.
Нехай задані числа
та
, компоненти яких записуються як
. Тоді
![{\displaystyle Z=X\pm Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2f897d273544e93c74053d10f0f4db78c6eef4b)
обчислюється як
.
Аналогічно виконується множення.
Можливе не для всіх чисел. По-перше,
повинно бути цілим числом. По-друге, поелементне ділення можна виконати лише за умови, що запис числа
не містить компонент рівних нулю
. Тоді компоненти числа
![{\displaystyle Z=X:Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cac99978b7924304f3c40d2a18af23ee05845332)
обчислюються як
![{\displaystyle z_{i}\equiv x_{i}\cdot y_{i}^{-1}{\pmod {m_{i}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84baf6b205a488c1bc8f430cfb27aa5743af5633)
де
— обернене за модулем число до
, тобто
Алгоритм ділення у випадку коли дільник містить нульові елементи, можна знайти у статті [1].
- Обмеження на величину чисел.
- Відсутність ефективних алгоритмів для порівняння чисел, представлених у ЧСЗ. Порівняння зазвичай здійснюється через переклад аргументів з ЧСЗ у змішану систему числення з основами
.
- Повільні алгоритми перекладу з позиційної системи числення в ЧСЗ і назад.
- Складні алгоритми ділення.
- Труднощі у виявленні переповнення.
ЧСЗ широко використовується в мікроелектроніці в спеціалізованих пристроях — ALU, ЦОС, де потребується:
- Контроль за помилками, за рахунок введення додаткових надлишкових модулів.
- Висока швидкість роботи, яку забезпечує паралельна реалізація базових арифметичних операцій.
У модулярної арифметиці існують спеціальні набори модулів, які дозволяють частково нівелювати недоліки ЧСЗ і для яких існують ефективні алгоритми порівняння чисел та зворотного перекладу чисел в позиційну систему числення. Однією з найпопулярніших систем модулів є набір з трьох взаємно простих чисел вигляду {2n−1, 2n, 2n+1}
Розглянемо ЧСЗ з базисом
. У цьому базисі можна однозначно представити числа з проміжку від
до
, так як
. Таблиця відповідності чисел з позиційної системи числення та системи залишкових класів:
![{\displaystyle 0=(0;0;0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf808ddf87248a8d3f0ba38d6e29b07ce0a16dcb) |
![{\displaystyle 1=(1;1;1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7d64c0dbb42e478e2cd21bf57c88615719f59b3) |
![{\displaystyle 2=(0;2;2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f48ae9d9fed714432084e94fce1a982fe1f9fad3) |
![{\displaystyle 3=(1;0;3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1494f418f1c53713f4c10551817ab5a201773935) |
|
![{\displaystyle 5=(1;2;0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd8ff339c260d11439df5052a55b62caaeb14e31) |
![{\displaystyle 6=(0;0;1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/146bc73f850b7efa3a7ea68211a1310b629ffaae) |
![{\displaystyle 7=(1;1;2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3b5f242f3d1a756476fbbf1cd8d8e9fca3df50f) |
![{\displaystyle 8=(0;2;3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa2d1bb5ed6514dbbda232a66fc0788e80b8bf3a) |
|
![{\displaystyle 10=(0;1;0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a25e2f8af1246786545cd98e2ffb079b31856801) |
![{\displaystyle 11=(1;2;1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c83d6ec5cd0601c5adafa0d6655d918cef1b9f2b) |
![{\displaystyle 12=(0;0;2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a9dd1b101cfd0d9ae091b4b6e31d49de5692cef) |
![{\displaystyle 13=(1;1;3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bcf5f640db16791d380176f2dbaafa7a52c71f8) |
|
![{\displaystyle 15=(1;0;0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4869c4eb2ea2f5998cac8b2b74aa2991ff813500) |
![{\displaystyle 16=(0;1;1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b14a5662d74a5182917a9396bc23102fa5d5de8) |
![{\displaystyle 17=(1;2;2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ebcb80b7eeb5a63cdcea01ea7af4f34de60f85a) |
![{\displaystyle 18=(0;0;3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3675e03593bb6fc369809db874fae1a54f40b05c) |
|
![{\displaystyle 20=(0;2;0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a4581d14b833090060822f94a39f976c310b3b9) |
![{\displaystyle 21=(1;0;1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0889752a976acc115a978a30c162ba132f0da897) |
![{\displaystyle 22=(0;1;2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd0a62457bae2f19d76c29fbf830c940ca1788a1) |
![{\displaystyle 23=(1;2;3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/086e3eb49acbc712323d4ae50b7a0977ff3b8f2e) |
|
![{\displaystyle 25=(1;1;0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ecfc69a741293ad5e8f23e5a751691cd6d676d2) |
![{\displaystyle 26=(0;2;1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de5e0b5bf8b0864e351500905a7e7a5c7389c147) |
![{\displaystyle 27=(1;0;2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd0118b187dec88b646e081583b31e20e2d0f7af) |
![{\displaystyle 28=(0;1;3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b724e634c96dc12f0dd47b611db0152f74f943f4) |
|
Складемо два числа 12 і 7 у базисі
. Їх представлення в заданому базисі
i
(див. таблицю вище). Скористаємося формулою для складання:
![{\displaystyle z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}}\equiv (0+1){\pmod {2}}=1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e46beab5152be1b1653a13acbcb3094b64b0164)
![{\displaystyle z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}}\equiv (0+1){\pmod {3}}=1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51abd76359dd3ae6f3f2fb6d260eb1a5c4a6914f)
![{\displaystyle z_{3}\equiv (x_{3}+y_{3}){\pmod {m_{3}}}\equiv (2+2){\pmod {5}}=4;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcea9e0e6a39910c2e9ce04f89c8f8206e3fc3d6)
— за таблицею переконуємося, що результат дорівнює 19.
Помножимо два числа 3 і 7 в базисі
. Їх представлення в заданому базисі
та
(див. таблицю вище). Скористаємось формулою для множення:
![{\displaystyle z_{1}\equiv (x_{1}*y_{1}){\pmod {m_{1}}}\equiv (1*1){\pmod {2}}=1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7a6de9853acdddcd6b873939f6a8e61fcff6979)
![{\displaystyle z_{2}\equiv (x_{2}*y_{2}){\pmod {m_{2}}}\equiv (0*1){\pmod {3}}=0;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93640299e3b24ccdd09be84abd9dd470204239fd)
![{\displaystyle z_{3}\equiv (x_{3}*y_{3}){\pmod {m_{3}}}\equiv (3*2){\pmod {5}}=1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/471705b07a4052c14475aa7c0162f81bdce81fec)
— за таблицею переконуємося, що результат дорівнює 21.
Зауваження: якби множити або складати числа, які дають в результаті число більше або рівне
, то отриманий результат збігатиметься по модулю числа
з результатом операції в позиційній системі числення. При відніманні це правильно, коли отримуємо від'ємне число.