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

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

ВизначенняРедагувати

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

 

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

Не простий базисРедагувати

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

Наприклад, в базисі    числа 3 і 7 однаково записуються:
 
 

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

Арифметичні операціїРедагувати

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

Додавання, віднімання та множенняРедагувати

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

 

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

 .

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

ДіленняРедагувати

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

 

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

 

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

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

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

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

Застосування числової системи залишківРедагувати

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

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

Спеціальні системи модулівРедагувати

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

ПрикладиРедагувати

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

         
         
         
         
         
         

Приклад додаванняРедагувати

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

 
 
 

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

Приклад множенняРедагувати

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

 
 
 

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

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