17 Арифметичні операції в системі залишкових класів

Розглянемо основні правила виконання арифметичних операцій у системі залишкових класів (див. гл. 2). Нехай задано набор основ: р₁=3;р₂=5;р₃=7.

Тоді діапазон чисел, що можна представити буде дорівнювати Р=р₁р₂р₃=105. Числа будемо представляти в залишках основА=(а₁,а₂,…,а_n),В=(b₁,b₂,…,b_n), при цьому n дорівнює кількості узятих основ-тобто трьом.

Результат будь-якої операції позначимо АВ=С, деС=(с₁,с₂,…,с_n). При цьому, 0<А<Р, 0<В<Р, 0<С<Р.

При виконанні операцій у СЗК, необхідно враховувати наступні особливості:

- між розрядами СЗК відсутні зв’язки;

- всі операції виконуються порозрядно і обчислення можна проводити паралельно;

- для кожного розряду СЗК використають малорозрядні суматори, що працюють по модулю р_і;

- є можливість використати замість суматорів прості таблиці результатів розрядів СЗК.

17.1 Додавання чисел у сзк

Правило додавання двох чисел представлених у СЗК можна сформулювати в такий спосіб:

- числа складаються по розрядах основ, підсумуються їхні залишки;

- з отриманої суми залишків, віднімається основа цього розряду до одержання вирахування (залишку) результату цієї основи.

Формально це можна представити як: С=А+В, або (с₁,с₂,…,с_n) = (а₁,а₂,…,а_n)+(b₁,b₂,…, b_n), де кожний розряд дорівнює:

_{сі=(аі+bі)крі,}

де к=0, 1, 2ціле число раз вирахування основи до одержання залишку.

Приклад 1. Нехай р₁=3,р₂=5,р₃=7,Р=105. Скласти числаА=67,В=13.

Рішення: Представимо числа в СЗК, де залишки записані в десятковій системі. Тоді А=67=(1,2,4),В=13=(1,3,6). Проведемо додавання по незалежних розрядах, тодіс₁=1+1=2р₁= 3, томус₁=2;

с₂=2+3=5=р₂, томус₂=55=0;

с₃=4+6=107=р₃, томус₃=107=3. Тоді:

А = 67 = (1,2,4)

+В = 13 = (1,3,6)

С = 80 = (2,0,3)

Приклад 2. Нехай р₁=7,р₂=9,р₃=11,р₄=13,р₅=17. Скласти десяткові числа.

Рішення:

А = 39031 = (6,7,3,5,16)

+В = 67556 = (6,2,5,8,15)

С= 106587 = (5,0,8,0,14)

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

17.2 Вирахування чисел у сзк

Розглянемо операцію вирахування позитивних десяткових чисел за умови, що зменшуване більше від’ємника. Операція С=АВреалізується порозрядно в такий спосіб:

_{сі=аіbі+крі,}

де к=0, якщоа_іb_і, ік=1, якщоа_іb_і.

Приклад 1. Нехай р₁=3,р₂=5,р₃=7,Р=105. Десяткові числаА=19=(1,4,5),

В=13 =(1,3,6). Потрібно вирахувати:С=А–В.

Рішення:с₁=1–1+0·3=0, с₂=4–3+0·5=1, с₃5–6+1·7=6. Тоді:

А = 19 = (1,4,5)

–В = 13 = (1,3,6)

С = 06 = (0,1,6).

Приклад 2. Нехай р₁=7,р₂=9,р₃=11,р₄=13,р₅=17,Р=153153. Десяткові числаА=67556=(6,2,5,8,15);В=39031=(6,7,3,5,16). Потрібно вирахувати:С=А–В.

Рішення:

А = 67556 = (6,2,5,8,15)

–В = 39031 = (6,7,3,5,16)

С = 28525 = (0,4,2,3,16)

17.3 Множення чисел у сзк

Операція множення чисел у СЗК реалізується порозрядно множенням залишків з наступним відрахуванням Краз основи розряду до одержання залишку результату. Формальне множення

С=АВреалізується за формулою:

_{сі = аі·bі – крі,}

де к=0,1,2…;р_іі-та основа СЗК.

Приклад 1. Нехай р₁=3,р₂=5,р₃=7,Р=105. Помножити числаА=4,В=13.

Рішення. Представимо числа в СЗК: А=4=(1,4,4); В=13=(1,3,6).

Визначимо порозрядні добутки по кожній основі.

с₁= 11=1, що менше р₁, тому с₁= 1;

с₂= 43=12 >25 , томус₂=12–(25)=2;

с₃= 46=24 >37, томус₃=24–(37)=3.

Тоді, АВ=(1,4,4)(1,3,6)=(1,2,3)=52

Взявши ортогональні базиси В₁=70,В₂=21,В₃=15 (див. гл. 2.2), перевіримо: 70+221+315=157105=52.

Приклад2. Нехайр₁=7,р₂=9,р₃=11,р₄=13,р₅=17,Р=153153. Помножити десяткові числа.

Рішення:

А = 407 = (1,2,0,4,16)

*В = 279 = (6,0,4,6,7)

С = 113553 = (6,0,0,11,10)

Самостійно визначити ортогональний базис і перевірити рішення.