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

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

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

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

ЧСЗ визначається набором взаємно простих чисел (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 \pmod{m_i},\ i=1,\dots,n.

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

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

Якщо базис складається не з взаємно простих чисел, то його можна використовувати для представлення чисел з відрізка [0,M-1], де M=HCK(m_1\cdot m_2\cdot \dots\cdot m_n). НСК — це найменше спільне кратне.

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

Однакове представлення виникло тому, що найбільше число, яке може бути записане в цьому базисі, це найменше спільне кратне чисел (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, ЦОС, де потребується:

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

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

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