10  АЛГОРИТМИ ВИКОНАННЯ АРИФМЕТИЧНИХ ОПЕРАЦІЙ

Для більшості сучасних комп’ютерів загальноприйнятим є такий формат з фіксованою комою (ФК), коли кома фіксується праворуч від молодшого розряду коду числа. З цієї причини відповідні операційні пристрої (ОПр) називають цілочисельними. У формі з ФК можуть бути представлені як числа без знаку, коли всі n позицій числа відводяться під значущі цифри, так і зі знаком. У останньому випадку старший (n – 1)-й розряд числа займає знак числа (0 – плюс, 1 – мінус), а під значущі цифри відведені розряди з (n – 2)-го по 0-й. Під час запису від’ємних чисел використовується доповняльний код.

Цілочисельний ОПр повинний забезпечувати виконання таких арифметичних операцій над числами без знаку і зі знаком: додавання /віднімання; множення; ділення.

10.1 Алгоритми виконання операцій додавання і віднімання

На рис. 10.1 наводяться приклади додавання цілих чисел, поданих у доповняльному коді (нагадаємо, що під час додавання в доповняльному коді знаковий розряд бере участь в операції нарівні з цифровими).

Під час додавання n-розрядних двійкових чисел (біт знака і n – 1 значущих цифр) можливий результат, який містить n значущих цифр.

Ця ситуація відома як переповнення. «Зайвий» біт займає позицію знака, що приводить до некоректності результату. Природно, що ОПр повинний виявляти факт переповнення і сигналізувати про нього. Для цього використовується наступне правило: якщо додаються два числа і вони обидва додатні або обидва відємні, переповнення має місце тоді і тільки тоді, коли знак результату протилежний знаку доданків.

Рисунок 10.1 – Приклади виконання операції додавання в доповняльному коді:

а, б, в, г – додавання без виникнення переповнення; д, е – додавання з переповненням

Рисунки 10.1, д і 10.1, е показують приклади переповнення. Звернемо увагу, що переповнення не завжди супроводжується перенесенням із знакового розряду. Віднімання виконується відповідно до правила: для віднімання одного числа (від’ємника) з іншого (зменшуваного) необхідно взяти доповнення від’ємника і додати його до зменшуваного. Під доповненням тут розуміється від’ємник з протилежним знаком, поданий у доповняльному коді. Віднімання ілюструється прикладами (рис. 10.2). Два останні приклади (рис. 10.2, д і 10.2, е) демонструють раніше розглянуте правило виявлення переповнення.

Рисунок 10.2 – Приклади виконання операції віднімання в доповняльному коді:

а, б, в, г - віднімання без виникнення переповнення; д, е - віднімання з переповненням

Щоб спростити виявлення ситуації переповнення, часто застосовується так званий модифікований доповняльний код, коли для зберігання знака відводяться два розряди, причому обидва беруть участь в арифметичній операції нарівні з цифровими розрядами.

10.2. Алгоритми множення кодів чисел з фіксованою комою

У порівнянні з додаванням і відніманням, множення – складніша операція як у разі програмного, так і в разі апаратного втілення. В комп’ютерах застосовуються різні алгоритми реалізації операції множення і, відповідно, декілька схем побудови операційних блоків, що забезпечують виконання операції множення.

Традиційна схема множення схожа на відому процедуру запису «в стовпчик». Обчислення добутку Р ( p2n-1 p2n-2 ... p1 p0 ) двох n-розрядних двійкових чисел без знака A ( an-1 an-2 ... a1 a0 ) і В ( bn-1 bn-2 ... b1 b0 ) зводиться до формування часткових добутків (ЧД) Wi, поодинці на кожну цифру множника, з подальшим підсумовуванням отриманих ЧД. Перед підсумовуванням кожен частковий добуток повинен бути зсунутим на один розряд щодо попереднього згідно з вагою цифри множника, якій цей ЧД відповідає. Оскільки операндами є двійкові числа, обчислення ЧД спрощується – якщо цифра множника bi дорівнює 0, то Wi теж дорівнює 0, а при bi = 1 частковий добуток дорівнює множеному (Wі = A). Множення двох n-розрядних двійкових чисел Р = А × В приводить до отримання результату, що містить 2n бітів. Таким чином, алгоритм множення припускає послідовне виконання двох операцій – додавання і зсуву (рис. 10.3).

Рисунок 10.3 – Загальна схема множення із зсувом суми часткових добутків вліво або вправо

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

Залежно від способу отримання суми часткових добутків (СЧД) можливі чотири варіанти реалізації «традиційної» схеми множення:

1. Множення починається з молодших розрядів множника, і зсув суми часткових добутків відбувається вправо у разі нерухомого множеного.

2. Множення починається із старших розрядів множника, і зсув суми часткових добутків відбувається вліво у разі нерухомого множеного.

3. Множення починається з молодших розрядів множника, і зсув множеного відбувається вліво у разі нерухомої суми часткових добутків.

4. Множення починається із старших розрядів множника, і зсув множеного відбувається вправо у разі нерухомої суми часткових добутків.

Варіанти із зсувом множеного на практиці не використовуються, оскільки для їх реалізації регістр множеного, регістр СЧД і суматор повинні мати розрядність 2n, тому зупинимося на найбільш розповсюдженому 1-му варіанті, який має назву алгоритм із зсувом вправо (алгоритм А).

Множення чисел без знака

Загальну процедуру традиційного множення спочатку розглянемо стосовно чисел без знака, тобто таких чисел, в яких всі n розрядів представляють значущі цифри. Процедура множення ілюструється прикладом обчислення добутку 10 × 11 (рис. 10.4).

Рисунок 10.4 – Приклад множення із зсувом суми часткових добутків вправо

Множення чисел із знаком

Дещо складніше йде справа з множенням чисел із знаком, коли n-розрядні співмножники містять знак (у старшому розряді слова) і n–1 значущу цифру. В подальшому умовимося відокремлювати знаковий розряд крапкою, не забуваючи, проте, що знаковий розряд бере участь в операції разом з цифровими розрядами.

Найбільш очевидна думка – набути абсолютних значень операндів і перемножити їх як числа без знака. Справедливість такого рішення видно з прикладу, приведеного на рис. 10.6, де показаний процес множення чисел +13 і +10.

У всіх ОМ загально прийнято подавати числа із знаком у формі з фіксованою комою в доповняльному коді. Додатні числа в цьому уявленні не відрізняються від запису в прямому коді, від’ємні записуються у вигляді 2n – x, де x – фактичне значення числа. В двійковій системі запис від’ємного числа в доповняльному коді зводиться до інвертування всіх цифрових розрядів числа, представленого в прямому коді, і додавання одиниці до молодшого розряду зворотного коду, що вийшов після інвертування.

Рисунок 4.6 – Множення чисел при додатних співмножниках

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

  Множене довільного знака, множник додатний. У разі від’ємного множеного процедура множення протікає аналогічно розглянутому, з урахуванням зробленого зауваження про арифметичний зсув СЧД (рис. 10.7). 

Рисунок 10.7 – Множення чисел з від’ємним множеним і додатним множником

Оскільки результат множення від’ємний, він виходить у доповняльному коді.

Множене довільного знака, множник від’ємний. На рис. 10.8 і 10.9 приведені приклади множення додатного і від’ємного множеного на від’ємний множник.

Рисунок 10.8 – Множення чисел у разі додатного множеного і від’ємного множника

Рисунок 10.9 – Множення чисел у разі від’ємного множеного і від’ємного множника

Оскільки множник від’ємний, він записується в доповняльному коді:

[В]Д = 2n – |В|, і в цифрових розрядах коду буде подане число 2n-1 – |В|. У разі типового множення (як у випадку В ≥ 0) отримаємо Р  = А × (2n-1 – |В|) = − |В| × А + А × 2n-1. Псевдодобуток  Р  більше дійсного добутка Р на величину А × 2n-1, що і необхідно враховувати під час формування остаточного результату. Для цього перед останнім зсувом з отриманого псевдо добутку необхідно відняти надлишковий член. У приклади множення є згадана корекція результату.

На практиці для пришвидшення перемножування чисел із знаком застосовують інші алгоритми та методи.

10.3 Алгоритми ділення кодів чисел з фіксованою комою

Ділення дещо складніша операція, ніж множення, але базується на тих же принципах. Основу складає загальноприйнятий спосіб ділення за допомогою операцій віднімання або додавання і зсуву (рис. 10.10).

Рисунок 10.10 – Загальна схема операції ділення

Задача зводиться до обчислення частки Q і залишку S:

Ділення виражається як послідовність віднімань дільника спочатку з  діленого, а потім з часткових залишків (ЧЗ), що утворюються в процесі ділення. Ділене Z (z2n-1 z2n-2 … z1 z0) зазвичай записується подвійним словом (2n розрядів), дільник D (d2n-1 d2n-2 … d1 d0), частка Q (q2n-1 q2n-2 … q1 q0) і залишок S (s2n-1 s2n-2 … s1 s0) мають розрядність n.

Операція виконується за n ітерацій і може бути описана таким чином:

Після n ітерацій виходить:

Частка від ділення 2n-розрядного числа на n-розрядне може містити більше, ніж n розрядів. У цьому випадку виникає переповнення, через що перед виконанням ділення необхідна перевірка умови 

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

Крім цієї вимоги, перед початком операції необхідно виключити можливість ситуації ділення на 0.

Реалізувати ділення можна двома основними способами:

- з нерухомим діленим і зсовуваним вправо дільником;

- з нерухомим дільником і зсовуваним вліво діленим.

Недоліком першого способу є потреба мати в пристрої ділення суматор і регістр подвійної довжини. Другий спосіб дозволяє будувати пристрій ділення з суматором одинарної довжини. Нерухомий дільник D зберігається в регістрі одинарної довжини, а ділене Z, що зсовується відносно D, знаходиться в двох таких же регістрах. Цифри частки Q, що утворюються, заносяться в розряди одного з регістрів Z, які звільняються при зсуві розрядів Z.

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

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

-  скорочення часу обчислення часткових залишків в традиційних методах ділення (з відновленням або без відновлення залишку) за рахунок прискорення операцій підсумовування (віднімання);

- скорочення часу обчислення за рахунок зменшення кількості операцій підсумовування (віднімання) під час розрахунку ЧЗ;

- обчислення частки в надмірній системі числення.

Операції над числами у форматі з плаваючою крапкою (ПК) мають істотні відмінності від аналогічних операцій цілочисельної арифметики, тому їх зазвичай реалізують за допомогою самостійного операційного пристрою. Як і цілочисельний ОПр, операційний пристрій для чисел у форматі ПК як мінімум повинен забезпечувати виконання чотирьох арифметичних дій: додавання, віднімання, множення і ділення.