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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Визначення[ред.ред. код]

ЧСЗ визначається набором взаємно простих чисел , які називаються базисом. Позначимо добуток базиса через . Тоді кожному цілому числу з відрізка ставиться у відповідність набір залишків , де

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

Не простий базис[ред.ред. код]

Якщо базис складається не з взаємно простих чисел, то його можна використовувати для представлення чисел з відрізка , де . НСК — це найменше спільне кратне.

Наприклад, в базисі (2,4). Числа 3 і 7 однаково записуються:


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

Арифметичні операції[ред.ред. код]

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

Додавання, віднімання та множення[ред.ред. код]

Нехай задані числа та , компоненти яких записуються як . Тоді

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

.

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

Ділення[ред.ред. код]

Можливе не для всіх чисел. По-перше, повинно бути цілим числом. По-друге, поелементне ділення можна виконати лише за умови, що запис числа не містить компонент рівних нулю . Тоді компоненти числа

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

де  — обернене за модулем число до , тобто

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

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

  • Обмеження на величину чисел.
  • Відсутність ефективних алгоритмів для порівняння чисел, представлених у ЧСЗ. Порівняння зазвичай здійснюється через переклад аргументів з ЧСЗ у змішану систему числення з основами .
  • Повільні алгоритми перекладу з позиційної системи числення в ЧСЗ і назад.
  • Складні алгоритми ділення.
  • Труднощі у виявленні переповнення.

Застосування числової системи залишків[ред.ред. код]

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

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

Спеціальні системи модулів[ред.ред. код]

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

Приклади[ред.ред. код]

Розглянемо ЧСЗ з базисом . У цьому базисі можна однозначно представити числа з проміжку від до , так як . Таблиця відповідності чисел з позиційної системи числення та системи залишкових класів:

Приклад додавання[ред.ред. код]

Складемо два числа 12 і 7 у базисі . Їх представлення в заданому базисі i (див. таблицю вище). Скористаємося формулою для складання:

 — за таблицею переконуємося, що результат дорівнює 19.

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

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

 — за таблицею переконуємося, що результат дорівнює 21.

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