РЕФЕРАТ
на тему:”ВИКОНАННЯ ОПЕРАЦІЙ МНОЖЕННЯ І ДІЛЕННЯ В ДВІЙКОВІЙ СИСТЕМІ ЧИСЛЕННЯ ”
ВИКОНАННЯ ОПЕРАЦІЙ МНОЖЕННЯ І ДІЛЕННЯ В ДВІЙКОВІЙ СИСТЕМІ ЧИСЛЕННЯ
1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО ОПЕРАЦІЮ МНОЖЕННЯ
У програмах розв'язання різних задач операції множення зустрічаються рідше, ніж додавання і віднімання, разом узяті. Проте для багатьох задач виявляється, що більшу частину часу машина зайнята виконанням множень, тому що одне множення вимагає, як правило, більше часу, ніж одне додавання або віднімання. Тому методам виконання множення, способам його прискорення і раціональній побудові пристроїв для множення завжди приділялася значна увага в розробках і в теоретичних дослідженнях з цифрової техніки.
Одним з найдавніших вважається давньоєгипетський спосіб множення, що заснований на використанні операції подвоєння. Для визначення добутку С
додатних чисел А
і В
за цим способом спочатку обчислюють шляхом подвоєння усі можливі значення (і
= 0, 1, 2, .., k
) і А
доти, поки не буде виконана умова 2k
+l
>В.
Значення С
визначають як суму тих часткових добутків А
, для яких входить до представлення числа В.
Хоча в цьому способі використовуються елементи двійкового множення, числа А
и В
представляються в системі числення з довільною основою р
>2.
Приклад 3.1.
Помножити числа А
= 25 і В
= 43.
Розв'язання
. Складаються три стовпчики. В лівому стовпчику розташовуються степені двійки, де зірочками позначені ті числа, з яких складається число В
= 43. У середньому стовпчику перше число дорівнює А
, а кожне наступне є подвоєним попереднім числом. У правому стовпчику знаходяться часткові добутки, що відповідають поміченим числам лівого стовпчику. Результат множення утворюється додаванням чисел правого стовпчику.
Відповідь
: С
= 1075.
Найвідомішим є "шкільний" метод множення в стовпчик. Для двійкової системи числення він має два варіанти.
1. Множення починається з молодших розрядів множнику:
2. Множення починається зі старших розрядів множнику:
В обох випадках операція множення полягає в додаванні часткових добутків, що утворюються множенням цифр множнику на зсунене на відповідну кількість розрядів множене.
Найпростіше множення виконується у прямому коді. У разі представлення чисел з фіксованою комою воно реалізується у два етапи. На першому етапі визначається знак добутку шляхом додавання за модулем два цифр знакових розрядів співмножників (див. табл. 3.1). На другому етапі здійснюється множення модулів співмножників, потім, у разі потреби, округлення модуля добутку, після чого до модуля результату дописується його знак, що визначений на першому етапі. Множення цифр розрядів співмножників виконується згідно таблиці двійкового множення, що наведена у параграфі 2.1.
Таблиця 3.1 - Правила визначення знаку добутку
| Обчислення вручну |
Обчислення в машині |
|
|
|
|
|
|
|
|
|
|
|
|
3.2. МНОЖЕННЯ ЧИСЕЛ, ЩО ПРЕДСТАВЛЕНІ В ФОРМІ З ФІКСОВАНОЮ КОМОЮ
3.2.1. Прості методи множення
Нехай - модуль множеного, - модуль множника. Тоді, у разі представлення чисел у формi з фіксованою комою, модуль добутку визначається за формулою:
. (3.1)
Звідси випливає, що процес множення полягає у нагромадженні часткових добутків , яким керують цифри множника . Керування процесом множення може починатись як з молодших розрядів множнику, так і зі старших.
З урахуванням цього розглянемо прості методи множення.
Метод 1
. Перетворимо формулу (3.1) до такого вигляду:
.
Звідси випливає, що множення зводиться до п
-кратного виконання циклу:
,
де ,
для початкових значень
.
Це означає, що множення починається з молодших розрядiв множника
i множене зсувається вліво
на один розряд в кожному циклi. При цьому до суми часткових добутків додається або зсунене множене, якщо =1, або нуль, коли =0. Після завершення п
-го циклу утворюється остаточний результат множення. Тобто
.
Реалізація даного методу вимагає (рис. 3.1) 2п
-розрядного зсувового регістру множеного РгА, п
-розрядного зсувового регістру множнику РгВ, 2п
схем І, що пропускають код із виходу регістра РгА на вхід 2п
-розрядного нагромаджувального суматора НСМ коли =1 і забороняють його надходження коли =0. Тут чергова цифра множника, що керує додаванням часткових добутків, береться з молодшого розряду регістра множника.
Оскільки зсув кодів у регістрах РгА і РгВ може виконуватись одночасно з додаванням у нагромаджувальному суматорі НСМ, то час множення п
-розрядних кодів за даним методом дорівнює:
. (3.2)
Тут ураховано те, що в машинах завжди час додавання більше, ніж час зсуву коду .
Рис. 3.1. Структурна схема пристрою, що реалізує множення за методом 1
Приклад 3.2.
Помножити числа А
= - 0, 10100 і В
= 0, 10011, використовуючи метод 1.
Розв'язання
. Для даних чисел маємо: =1; = 0, 10100; =0; = 0, 10011. Визначаємо знак добутку: =10=1.
Усі дії, що виконуються в кожному циклі множення, зручно подати у вигляді таблиці (табл. 3.2).
Відповідь
: С
= - 0, 0101111100.
Метод 2
. Представимо (3.1) у вигляді:
.
Обчислення добутку за цією формулою зводиться до п
-кратного виконання циклу:
;
для початкових значень
.
Звідси випливає, що множення починається зі старших розрядiв множника
i множене зсувається вправо
на один розряд в кожному циклi. При цьому до суми часткових добутків додається або зсунене множене, якщо =1, або нуль, коли =0. Після завершення п
-го циклу утворюється остаточний результат множення .
Таблиця 3.2 - Приклад множення за методом 1
Для реалізації даного методу множення потрібні (рис.3.2) 2п
-розрядний регістр множеного РгА з колами для зсуву вправо, п
-розрядний регістр множника РгВ з колами для зсуву вліво, 2п
схем І і 2п
-розрядний нагромаджувальний суматор НСМ. Тут чергова цифра множника, що керує додаванням часткових добутків, береться зі старшого розряду регістра множника.
Час множення за даним методом дорівнює:
. (3.3)
Рис. 3.2. Структурна схема пристрою, що реалізує множення за методом 2
Приклад 3.3.
Помножити числа А = - 0, 10100 і В = - 0, 10011, використовуючи метод 2.
Розв'язання
. Для даних чисел маємо: =1; = 0, 10100; =1; = 0, 10011. Визначаємо знак добутку: =11=0. Усі дії, що виконуються під час множення, наведені у табл. 3.3.
Відповідь
: С
= 0, 0101111100.
Метод 3.
Перетворимо (3.1) за схемою Горнера для обчислення поліномів:
=
=.
Звідси випливає, що множення зводиться до п
-кратного виконання циклу:
для початкових значень .
Таблиця 3.3 - Приклад множення за методом 2
У кожному циклі до суми часткових добутків додається або множене, якщо =1, або нуль, коли =0, після чого сума часткових добутків помножується на , тобто зсувається на один розряд управо. Після завершення п
-го циклу утворюється остаточний результат множення . Звідси випливає, що множення починається з молодших розрядiв множника
i зсувається сума часткових добутків управо
на один розряд в кожному циклi.
Для реалізації даного методу множення потрібні (рис.3.3) п
-розрядний регістр множеного РгА, п
-розрядний регістр множника РгВ з колами для зсуву вліво, п
схем І і (2п
+1)-розрядний нагромаджувальний суматор НСМ з колами для зсуву вправо. Тут множене завжди додається до п
старших розрядів суми часткових добутків. Один додатковий розряд ліворуч у НСМ необхідний для запам'ятовування цифри переповнення, що може виникнути в процесі додавання; під час наступного зсуву ця цифра піде в старший з основних розрядів нагромаджувального суматора,
так що в остаточному результаті переповнення не буде.
Рис. 3.3. Структурна схема пристрою, що реалізує множення за методом 3
Оскільки в кожному циклі в нагромаджувальному суматорі НСМ спочатку виконується додавання, а потім зсув коду, то час множення п
-розрядних кодів за даним методом дорівнює:
. (3.4)
Приклад 3.4.
Помножити числа А = 0, 11100 і В = 0, 10011, використовуючи метод 3.
Розв'язання
. Для даних чисел маємо: =0; = 0, 11100; =0; = 0, 10011. Визначаємо знак добутку: =00=0. Послідовність дій, що виконуються для одержання модулю добутку, показано в табл. 3.4.
Таблиця 3.4 - Приклад множення за методом 3
Відповідь
: С
= 0,1000010100.
Особливість даного методу множення полягає в тому, що в кожному циклі визначається одна вірогідна цифра добутку (починаючи з наймолодшого розряду), яка не змінюється в інших циклах множення. Врахування цього дозволяє зменшити кількість розрядів нагромаджувального суматора вдвічі, обчислюючи 2п
-розрядний добуток. При цьому для зберігання вірогідних цифр використовуються розряди регістра множника, що звільняються в процесі множення. Структурна схема такого пристрою для множення наведена на рис. 3.4. Тут вихід молодшого розряду нагромаджувального суматора НСМ з'єднаний з входом старшого розряду регістра множника РгВ. Цим самим утворюється спільний зсувовий регістр. Старші розряди добутку формуються в НСМ, а молодші в РгВ.
Рис. 3.4. Структурна схема модифікованого пристрою, що реалізує множення за методом 3
Приклад 3.5.
Описати множення чисел А = 0, 11100 і В = 0, 10011, що реалізується модифікованим пристроєм.
Розв'язання
. Для даних чисел маємо: =0; = 0, 11100; =0; = 0, 10011. Визначаємо знак добутку: =00=0. Послідовність дій, виконуваних у процесі множення, наведено в табл. 3.5.
Відповідь
: С
= 0,1000010100.
Метод 4.
Якщо перетворити (3.1) за схемою Горнера до вигляду:
,
то множення зведеться до п
-кратного виконання циклу:
для початкових значень .
У кожному циклі до суми часткових добутків додається або множене, якщо =1, або нуль, коли =0, після чого сума часткових добутків зсувається на один розряд вліво. Тобто множення починається зі старших розрядiв множника
i зсувається сума часткових добутків вліво
на один розряд в кожному циклi.
Таблиця 3.5 - Приклад множення з використанням модифікованого пристрою
Для реалізації даного методу множення потрібні (рис.3.5) п
-розрядний регістр множеного РгА, п
-розрядний регістр множника РгВ з колами для зсуву вліво, п
схем І і 2п
-розрядний нагромаджувальний суматор НСМ з колами для зсуву вліво. Тут множене завжди додається до п
молодших розрядів суми часткових добутків.
Враховуючи те, що в кожному циклі в нагромаджувальному суматорі НСМ спочатку виконується додавання, а потім зсув коду, маємо такий час множення п
-розрядних кодів за даним методом:
. (3.5)
Рис. 3.5. Структурна схема пристрою, що реалізує множення за методом 4
Приклад 3.6.
Помножити числа А = 0, 10100 і В = 0, 10011, використовуючи метод 4.
Розв'язання
. Для даних чисел маємо: =0; = 0, 10100; =0; = 0, 10011. Визначаємо знак добутку: =00=0. Послідовність дій, виконуваних у процесі множення, наведено у табл. 3.6.
Відповідь
: С
= 0, 0101111100.
Аналіз описаних методів множення і пристроїв, що їх реалізують показує таке.
Тривалість процесу множення за першим і другим методами менше, ніж за третім і четвертим, за рахунок суміщення у часі операцій додавання часткових добутків і зсувів множеного.
За кількістю апаратури перевагу варто віддати модифікованому пристрою, що реалізує третій метод множення.
Пристрій, що реалізує перший метод множення виявляється дуже не ощадливим за кількістю необхідної апаратури. Крім того, розряди суматора НСМ використовуються неефективно: у початкових циклах множення старші розряди зайняті увесь час "додаванням" нулів, наприкінці множення на молодші розряди надходять з регістра РгА нулі, тобто ніяких корисних операцій вони фактично не роблять.
Таблиця 3.6 - Приклад множення за методом 4
У той же час цей пристрій є вигідним з такої точки зору. До початку множення можна записати в суматор НСМ замість нуля яке-небудь інше число (скажемо, результат попереднього множення). Тоді в результаті множення можна одержати у суматорі НСМ замість добутку значення суми +. Це дозволяє легко організувати нагромадження суми парних добутків чисел . У модифікованому пристрої, що реалізує третій метод, цього зробити не можна, тому що в процесі множення початковий вміст суматора НСМ зсувається п
раз управо.
На підставі вищевикладеного можна вважати найбільш зручними для застосування в ЦОМ пристрої, які реалізують перший і третій методи множення, що і підтверджується практикою розробки обчислювальних пристроїв.
3.2.2. Метод скороченого множення
Усі розглянуті методи множення забезпечують одержання добутку розрядністю 2п
, не вносячи при цьому похибок у результат. Якщо послідовно буде виконуватись декілька операцій множення, то розрядність результатів буде значно збільшуватись. Тому після виконання операції множення, як правило, здійснюється округлення. Якщо висувається вимога, щоб похибки добутків не перевищували одиниці молодшого розряду (), то можна значно скоротити розрядність регістра множеного РгА і нагромаджувального суматора НСМ. У спеціалізованих машинах іноді реалізують метод скороченого множення, починаючи зі старших розрядів. Особливість цього методу полягає в тому, що одержуються п
точних розрядів добутку з використанням розрядів у суматорі НСМ і регістрі РгА.
Кількість додаткових розрядів визначається виходячи з таких міркувань. Нехай і . Тоді, якщо всі , то
Припустимо, що всі розряди, які розташовані праворуч від вертикальної лінії, відкидаються. Якщо додавати тільки n
розрядів, то вноситься похибка, тому що не враховуються перенесення з відкинутих розрядів у розряди, які розташовані ліворуч від лінії. Ці перенесення можуть поширитися на k
розрядів ліворуч від лінії. Якщо всі , то кожен розряд дає одиницю перенесення і загальна кількість одиниць перенесень з відкинутої частини буде дорівнювати
.
Для досить великих значень n
маємо: .
Одиниці перенесень поширяться на k
розрядів суматора, і добуток буде містити тільки точних розрядів. Отже, щоб одержати результат з точністю до n
розрядів, необхідно виділити розрядів у суматорі НСМ і регістрі РгА. Кількість додаткових розрядів k
при цьому визначається за формулою:
. (3.6)
Нижче приведені результати розрахунку за (3.6) :
| п
|
24 |
32 |
40 |
48 |
64 |
72 |
| k
|
5 |
5 |
6 |
6 |
6 |
7 |
3.2.3. Множення обернених кодів чисел
Операцію множення найпростіше виконувати в прямих кодах чисел. Разом з тим застосування обернених кодів дозволяє істотно спростити операцію алгебричного додавання. Тому числа бажано зберігати в запам'ятовувальному пристрої в оберненому коді і множити також обернені коди. Розглянемо правила множення операндів, що представлені в оберненому коді.
Нехай множене А
- будь-яке число, а множник B
> 0, тобто А
= [A
]об
і [В
]об
. Тоді
.
Згідно з теоремою про додавання обернених кодів можна стверджувати, що права частина цього співвідношення відповідає оберненому коду результату.
Розглянемо випадок, коли множене А
- будь-яке число, а множник B
< 0, тобто А
=[A
]об
і [В
]об
. Виходячи з означення оберненого коду . Отже,
.
Тоді
.
Таким чином, у загальному випадку, добуток одержується відразу зі знаком.
Виходячи з розглянутих випадків, можна зробити такі висновки.
1. Дії, що виконуються під час множення обернених кодів, залежать від знаку множника.
2. Добуток обернених кодів співмножників дорівнює оберненому коду результату тільки у випадку додатного множника.
3. Якщо множник є від'ємним числом, то обернений код добутку одержується додаванням поправок і до добутку обернених кодів співмножників.
Оскільки поправки мають різну вагу, то послідовність їх додавання залежить від того, з яких розрядів множника починається множення (табл. 3.7).
Приклад 3.7.
Помножити обернені коди чисел А
= - 0, 10100 і В
= 0, 10011, використовуючи метод 1.
Розв'язання
. Для даних чисел маємо: [А
]м
об
=11,01011; [В
]об
= 0,10011. Оскільки B
>0, то поправки не додаються. Послідовність дій, що виконуються в процесі множення, подані у вигляді табл. 3.8.
Відповідь
: [С
]м
об
=11,1010000011; С
= - 0, 0101111100.
Таблиця 3.7 - Послідовність додавання поправок для оберненого коду
| Методи множення |
Е т а п и |
||
| З молодших розрядів множника |
Додавання |
Множення за методом і додатковий зсув на один розряд після його завершення |
Додавання |
| Зі старших розрядів множника |
Додавання |
Додатковий зсув на один розряд і після нього множення за методом |
Додавання |
Таблиця 3.8 - Перший приклад множення обернених кодів
Приклад 3.8.
Помножити обернені коди чисел А
= - 0,10100 і В
= - 0, 10011, використовуючи метод 2.
Розв'язання
. Для даних чисел маємо: [А
]м
об
=11,01011; [В
]об
= 1,01100. Оскільки B
<0, то додаються поправки. Послідовність дій, що виконуються в процесі множення, подані у вигляді табл. 3.9.
Таблиця 3.9 - Другий приклад множення обернених кодів
Відповідь
: С
= 0, 0101111100.
3.2.4. Множення доповняльних кодів чисел
У випадках, коли числа в машині зберігаються в доповняльних кодах, доцільно всі операції над числами робити на суматорі доповняльного коду. Однак при цьому під час множення виникає ряд особливостей, які необхідно враховувати. Тому розглянемо правила множення операндів, що представлені в доповняльному коді.
Нехай множене А
- будь-яке число, а множник B
> 0, тобто А
= [A
]д
і [В
]д
. Тоді
.
Згідно з теоремою про додавання доповняльних кодів можна стверджувати, що права частина цього співвідношення відповідає доповняльному коду результату. Таким чином, у випадку додатного множника добуток доповняльних кодів співмножників дорівнює доповняльному коду результату.
Розглянемо випадок, коли множене А
- будь-яке число, а множник B
< 0, тобто А
=[A
]д
і [В
]д
. Виходячи з означення доповняльного коду . Отже,
.
Тоді
.
Звідси випливає, що коли множник є від'ємним числом, то доповняльний код добутку одержується додаванням поправки
до добутку доповняльних кодів співмножників.
Таким чином, у загальному випадку, в процесі множення доповняльних кодів операндів одержуємо одночасно знакову і цифрову частини добутку.
Правила множення з додаванням поправки наведені в табл. 3.10.
Приклад 3.9.
Помножити доповняльні коди чисел А
= - 0, 10100 і В
= 0, 10011, використовуючи метод 1.
Розв'язання
. Для даних чисел маємо: [А
]м
д
=11,01100; [В
]д
= 0,10011. Оскільки B
>0, то поправка не додається. Послідовність дій, що виконуються в процесі множення, подані у вигляді табл. 3.11.
Відповідь
: [С
]м
д
=11,1010000100; С
= - 0, 0101111100.
Таблиця 3.10 - Правила множення з додаванням поправки
| Методи множення |
Етапи |
|
| З молодших розрядів множника |
Множення за методом і додатковий зсув на один розряд після його завершення |
Додавання |
| Зі старших розрядів множника |
Додавання |
Додатковий зсув на один розряд і після нього множення за методом |
Таблиця 3.11 - Перший приклад множення доповняльних кодів
Приклад 3.10.
Помножити доповняльні коди чисел А
= - 0,10100 і В
= - 0, 10011, використовуючи метод 2.
Розв'язання
. Для даних чисел маємо: [А
]м
д
=11,01011; [В
]д
= 1,01100. Оскільки B
<0, то додається поправка. Послідовність дій, що виконуються в процесі множення, подані у вигляді табл. 3.12.
Таблиця 3.12 - Другий приклад множення доповняльних кодів
Відповідь
: С
= 0, 0101111100.
3.3. МЕТОДИ ПРИСКОРЕННЯ ОПЕРАЦІЇ МНОЖЕННЯ
3.3.1. Основні поняття
Прискорення операції множення дозволяє істотно підвищити продуктивність ЦОМ, оскільки приблизно 70% свого часу вони витрачають на виконання цієї операції. Аналізуючи (3.2) - (3.5), можна намітити такі шляхи скорочення часу множення: зменшення часу додавання і зсуву кодів; зменшення кількості додавань і кількості зсувів кодів.
Оскільки прості методи множення передбачають виконання в кожному циклі зсув кодів тільки на один розряд, то зменшити час зсуву неможливо тому, що кола для зсуву реалізують, як правило, з найменшою затримкою сигналів.
Зменшення часу додавання двох кодів досягається за рахунок ускладнення кіл формування розрядних сум і перенесень у суматорі. Але це ні яким чином не впливає на організацію процесу множення. Тому основні підходи щодо прискорення операції множення базуються на зменшенні кількості додавань і кількості зсувів кодів.
Відомі на цей час методи прискорення множення розподілені на дві великі групи: логічні й апаратні.
Логічними
методами прискорення множення називають такі методи, реалізація яких не вимагає змін основної структури арифметичних кіл пристрою для множення (див. рис. 3.1 - 3.5), а прискорення досягається тільки за рахунок ускладнення схеми керування цим пристроєм. Стосовно пристроїв для множення паралельних кодів ознакою того, що ми маємо справу з логічним методом прискорення множення, є незалежність кількості додаткової апаратури (у порівнянні з вихідною схемою) від кількості розрядів співмножників.
Апаратні методи,
прискорення множення вимагають для свого здійснення введення додаткової апаратури в основні арифметичні кола пристрою для множення.
Розрізняють апаратні методи першого порядку і другого порядку. Для апаратних методів першого порядку
характерна лінійна залежність кількості додаткової апаратури від кількості розрядів у співмножниках п
. Тоді як реалізація методів другого порядку
вимагає введення додаткової апаратури, кількість якої пропорційна .
3.3.2. Логічні методи прискорення операції множення в двійковій системі числення
До логічних методiв прискорення операції множення належать: метод множення з пропусканням додавань у тих випадках, коли чергова цифра множнику є нуль; метод множення з перетворенням цифр множнику шляхом групування розрядiв i метод множення з послідовним перетворенням цифр множника.
В основi двох останніх логічних методiв лежить перехід до надлишкової двійкової системи числення з алфавітом {1, 0, }, який дозволяє зменшити кількість одиниць у коді множника, але при цьому в процесi множення будуть виконуватись операції додавання та віднімання.
Метод множення з пропусканням додавань
є найпростішим з логічних методів прискорення множення. Схему керування взагалі простіше побудувати так, щоб за тактом зсуву щораз приділявся час на додавання, але додавання виконувалося б у залежності від цифри множника. Невелике ускладнення схеми керування, що дозволяє відводити час на додавання тільки тоді, коли воно дійсно необхідно, скорочує число тактів додавання в середньому вдвічі. Час множення за таким методом прискорення дорівнює:
.
Цей метод прискорення рівною мірою підходить для тих випадків, коли множення починається зі старших розрядів множника, і для випадків, коли множення починається з молодших розрядів.
Приклад 3.11.
Помножити числа А
= - 0, 10100 і В
= 0, 10011, використовуючи метод множення з пропусканням додавань.
Розв'язання
. Для даних чисел маємо: =1; = 0, 10100; =0; = 0, 10011. Визначаємо знак добутку: =10=1.
Усі дії, що виконуються в кожному циклі множення, наведені табл. 3.13.
Відповідь
: С
= - 0, 0101111100.
Таблиця 3.13 - Приклад множення за прискореним методом
Розглянемо тепер метод множення з перетворенням цифр множнику шляхом групування розрядiв
.
Кількість циклів, що необхідні для реалізації операції множення, можна скоротити, якщо в кожному циклі аналізувати не один, а два або більше розрядів множнику, виконуючи після аналізу додавання або віднімання та зсув множнику на відповідну кількість розрядів (два або більше). Для організації прискореного множення множник розбивають на групи з двох розрядів і перетворюють його таким чином, щоб кожна група містила не більш одної значущої одиниці (додатної або від'ємної).
Правила перетворення множника з молодших розрядiв у разі групування по два розряди формулюються, враховуючи таке.
Комбінації 00, 01, 10 не перетворюються, а комбінація 11 замінюється комбінацією 1.0, яка містить від'ємну одиницю в даній групі розрядів і додатну одиницю, що передається до наступної групи розрядів множника.
З урахуванням одиниці, що передається з попередньої групи розрядів, у даній групі розрядів після перетворення може зустрітися одна з таких комбінацій:
00 - якщо дана група розрядів містить цифри 00 і з попередньої групи одиниця не передається або якщо дана група розрядів містить цифри 11 і одиниця передається з попередньої групи розрядів;
01 - якщо дана група містить цифри 01 і з попередньої групи одиниця не передається, або якщо дана група розрядів містить 00 і передається одиниця з попередньої групи розрядів;
10 - якщо дана група містить 10 і нема одиниці з попередньої групи або якщо дана група містить 01 і є одиниця з попередньої групи розрядів;
0 - якщо дана група розрядів містить 11 і нема одиниці з попередньої групи або якщо дана група містить 10 і є одиниця з попередньої групи.
Із сказаного випливають правила перетворенням множнику, починаючи з молодших груп розрядів, що наведені в табл. 3.14. Тут - цифри даної групи розрядів; - цифра, що передається з попередньої групи; - перетворені цифри даної групи; - цифра, що передається в наступну групу.
Таблиця 3.14 - Правила перетворенням множнику, починаючи з молодших груп розрядів
|
|
|
|
|
|
|
|
|
| 0 0 |
0 |
0 0 |
0 |
0 0 |
1 |
0 1 |
0 |
| 0 1 |
0 |
0 1 |
0 |
0 1 |
1 |
1 0 |
0 |
| 1 0 |
0 |
1 0 |
0 |
1 0 |
1 |
0 |
1 |
| 1 1 |
0 |
0 |
1 |
1 1 |
1 |
0 0 |
1 |
Застосовуючи ці правила необхідно враховувати, що старша значуща цифра перетвореного множника може знаходитися в розряді цілих, де неперетворений множник містить завжди нуль.
Приклад 3.12.
Використовуючи групування розрядів, виконати перетворення множнику 001011111001100111, починаючи з молодших розрядів.
Розв
'
язання.
Діючи за правилами, що наведені в табл. 3.14, одержимо
| 0 0 |
1 0 |
1 1 |
1 1 |
1 0 |
0 1 |
1 0 |
0 1 |
1 1 |
| +1 |
+1 |
+1 |
+0 |
+0 |
+0 |
+0 |
+1 |
|
| 0 1 |
0 |
0 0 |
0 |
1 0 |
0 1 |
1 0 |
1 0 |
0 |
Замість 11 одиниць у вихідному представленні множника одержуємо 8 додатних і від'ємних одиниць у перетвореному.
Відповідь:
010000100110100.
Коли одразу аналізуються два розряди перетвореного множнику, то в процесі множення виконуються такі дії.
Якщо група містить комбінацію 00, то це означає, що протягом двох найближчих циклів множення не потрібно буде виконувати ні додавань, ні віднімань; при наявності комбінації 01 потрібно буде виконати одне додавання в першому з двох найближчих циклів множення, а у разі комбінації 10 - у другому. Коли група містить комбінацію 0, то буде потрібно виконати одне віднімання в першому з двох найближ
У разі одночасного аналізу двох розрядів, починаючи зі старших, у правилах перетворення груп розрядів (табл. 3.15) враховується значення сусіднього розряду, що розташований праворуч від групи, яка аналізується. При цьому аналіз розрядів множника завжди починається з пустої групи, що дописується ліворуч від найстаршого розряду.
Приклад 3.13.
Використовуючи групування розрядів, виконати перетворення множнику 001011111001100111, починаючи зі старших розрядів.
Розв
'
язання.
Діючи за правилами, що наведені в табл. 3.15, одержимо
Замість 11 одиниць у вихідному представленні множника одержуємо 7 додатних і від'ємних одиниць у перетвореному.
Відповідь:
01000000100100.
Той чи інший метод перетворення тим ефективніше, чим менше в перетвореному множнику середня кількість додатних і від'ємних одиниць, тобто чим менше в середньому потрібно додавань і віднімань. Важлива також максимальна кількість додавань і віднімань, що можуть виконуватись під час множення.
Таблиця 3.15 - Правила перетворення множнику, починаючи зі старших груп розрядів
|
|
|
|
|
|
|
| 0 0 |
0 |
0 0 |
0 0 |
1 |
0 1 |
| 0 1 |
0 |
0 1 |
0 1 |
1 |
1 0 |
| 1 0 |
0 |
0 |
1 0 |
1 |
0 |
| 1 1 |
0 |
0 |
1 1 |
1 |
0 0 |
Для оцінки ефективності описаного вище методу групування розрядів відзначимо насамперед, що для будь-якої комбінації цифр протягом двох циклів множення може бути не більш одного додавання або віднімання. Таким чином, в гіршому випадку кількість додавань-віднімань дорівнює 0,5п
.
Середня кількість додавань-віднімань дорівнює 0,375п
. З урахуванням цього середній час множення складає:
- для першого і другого методів множення
;
- для третього і четвертого методів множення
.
Метод множення з послідовним перетворенням цифр множника
передбачає послідовний аналіз цифр множника без розбиття на групи. При цьому використовується такі правила перетворення:
- якщо дана цифра неперетвореного множника не збігається із сусідньою праворуч цифрою, сусідня ліворуч цифра є 0 і попередня цифра перетвореного множника є 0, то даний розряд у перетвореному множнику є 1;
- якщо дана цифра неперетвореного множника не збігається із сусідньою праворуч цифрою, сусідня ліворуч цифра є 1 і попередня цифра перетвореного множника є 0, то даний розряд перетвореного множника повинний містити ;
- якщо дана цифра неперетвореного множника збігається із сусідньої праворуч цифрою або якщо попередня цифра перетвореного множника не є нулем, то даний розряд у перетвореному множнику є 0.
Застосовуючи ці правила необхідно враховувати, що старша значуща цифра перетвореного множника може знаходитися в розряді цілих; праворуч і ліворуч від значущих розрядів перетвореного множника завжди передбачаються нулі. Коли в приведеному правилі говориться про "попередні" цифри перетвореного множника, то стосовно до множення від молодших розрядів це відноситься до попередньої молодшої цифри перетвореного множника, а стосовно до множення від старших - до старшої попередньої цифри.
Описане послідовне перетворення розрядів множнику забезпечує під час множення в середньому 0,333п
додавань-віднімань. Це найкращий результат, що може бути отриманий для логічних методів прискорення множення.
У здійсненні метод послідовних перетворень ненабагато складніше, ніж метод групування розрядів множника, ефективність же його вище.
При цьому виникають визначеної довжини послідовності чи нулів одиниць, що приводить до необхідності одночасного аналізу декількох розрядів множника і зрушенню на довільне число розрядів.
3.3.3. Апаратні методи прискорення операції множення в двійковій системі числення
Спочатку розглянемо апаратні методі прискорення операції множення першого порядку.
1. Метод множення з перетворенням цифр множнику групування розрядiв і використанням кратних множеного
.
Практично використовують розбиття на групи з чотирьох розрядів, що рівносильне переходу до шестнадцаткової системи числення. При цьому розглядається чергова цифра (тетрада) множника і його попередня цифра (тетрада). В залежності від значень цифри множнику в попередньому розряді виконуються різні дії (табл.3.16). Для реалізації такого множення потрібно попередньо сформувати кратні множеного: А
, 2А
, 3А
і 6А
.
Аналіз чотирьох двійкових розрядів одночасно дає можливість одразу здійснити зсув на чотири розряди.
Таблиця 3.16 - Дії, що виконуються в залежності від цифр множника
| Тетрада, що аналізується |
Значення попередньої цифри |
Тетрада, що аналізується |
Значення попередньої цифри |
||
| 8 |
<8 |
8 |
<8 |
||
| 0 0 0 0 |
+А
|
0 |
1 0 0 0 |
- (6А
|
+(6А
|
| 0 0 0 1 |
+2А
|
+А
|
1 0 0 1 |
- 6А
|
- (6А
|
| 0 0 1 0 |
+3А
|
+2А
|
1 0 1 0 |
- (3А
|
- 6А
|
| 0 0 1 1 |
+(2А
|
+3А
|
1 0 1 1 |
- (2А
|
- (3А
|
| 0 1 0 0 |
+(3А
|
+(2А
|
1 1 0 0 |
- 3А
|
- (2А
|
| 0 1 0 1 |
+6А
|
+(3А
|
1 1 0 1 |
- 2А
|
- 3А
|
| 0 1 1 0 |
+(6А
|
+6А
|
1 1 1 0 |
- А
|
- 2А
|
| 0 1 1 1 |
+(6А
|
+(6А
|
1 1 1 1 |
0 |
- А
|
2. Метод множення з аналізом довільної кількості розрядiв множнику
. Ідея методу полягає у виявленні послідовностей нулів і одиниць з наступної груповою обробкою розрядів множнику. Якщо виявляється група вигляду , то виконується одразу зсув на k
-1 розрядів і додавання множеного. Якщо аналізується група вигляду , то здійснюється зсув одразу на k
-1 розрядів і віднімається множене. Коли аналізується група розрядів вигляду , то виконується її перетворення в нову групу вигляду . Код цієї групи показує, що спочатку виконується віднімання множеного, а потім зсув одразу на k
-1 розрядів.
Такий метод прискорення операції множення вимагає створення пристрою для зсуву кодів на довільну кількість розрядів.
3. Метод множення з розбиттям множника на частини
передбачає одночасне виконання множення числа А
на окремі частини числа В
з наступним додаванням отриманих результатів.
Множник В
можна розбити на будь-яку кількість частин, але найефективнішим, з точки зору комплексної оцінки апаратних і часових витрат, є розбиття на дві частини. Для цього випадку обчислення описуються такою формулою:
.
Якщо множення на частини виконується за першим і другим методами, то час множення дорівнює:
.
4. Метод множення з використанням таблиць квадратів чисел
базується на тотожності:
.
За значеннями суми і різниці співмножників з таблиці квадратів чисел зчитуються числа і , а потім остаточний добуток формується шляхом виконання операції віднімання .
Різновид цього методу множення описується тотожністю
.
Практично даний метод і його різновид дозволяють прискорити виконання операції множення чисел тільки невеликої розрядності (8 або 16 розрядів), тому що зі збільшенням розрядності чисел складність таблиці значно зростає.
4. Метод множення з запам’ятовуванням проміжних
перенесень
.
Час множення можна скоротити шляхом зменшення тривалості кожного додавання за рахунок виключення з нього часу, що витрачається на розповсюдження перенесень. Суть цього методу прискорення полягає в тому, що весь процес одержання добутку виконується додаванням без розповсюдження перенесень з одночасним їх запам'ятовуванням і однократним розповсюдженням перенесень на заключному етапі множення. При цьому в кожному циклі множення додаються порозрядно три числа: черговий частковий добуток, проміжна сума часткових добутків і проміжні перенесення, що утворені в попередньому циклі множення. При цьому перенесення, що отримані в попередньому циклі, повинні запам'ятовуватися до початку наступного циклу.
Приклад 3.14.
Помножити числа А
= 0, 10110 і В
= 0, 11011, використовуючи метод множення з запам’ятовуванням проміжних перенесень.
Розв'язання
. Для даних чисел маємо: =0; = 0, 10110; =0; = 0, 11011. Визначаємо знак добутку: =00=0.
Дії, що виконуються в процесі множення, наведені в табл. 3.17. Тут S - проміжна сума часткових добутків, P - проміжні перенесення.
Таблиця 3. 17 - Приклад множення з запам’ятовуванням перенесень
Для остаточних кодів S і P виконується додавання з розповсюдженням перенесення:
Відповідь
: С
= 0,1001010010.
До апаратних методів прискорення операції множення другого порядку відносяться матричні методи множення
.
Коли множене і множник розташовані в регістрах машини, можна утворити відразу всі часткові добутки і здійснити їх одночасне додавання, використовуючи певну кількість суматорів. Узагальнена структура пристрою, що реалізує таке множення (рис. 3.6), містить: регістри РгА і РгВ, в яких зберігаються множене і множник, відповідно; блок елементів І, що забезпечує формування всіх часткових добутків; блок суматорів, у якому здійснюється одночасне додавання всіх часткових добутків.
Матричні методи множення відрізняються саме організацією одночасного додавання.
Рис. 3.6. Узагальнена структура пристрою, що реалізує матричний метод множення
Існує ряд методів множення, що засновані на додаванні груп часткових добутків з наступним об'єднанням сум разом з перенесеннями для одержання добутку. Наприклад, часткові добутки групуються по три і додаються із запам'ятовуванням перенесень за допомогою ланцюжка суматорів На кінці ланцюжка здійснюється додавання з розповсюдженням перенесень. Така роздільна обробка проміжних сум і перенесень вимагає так називаного "дерева суматорів" (рис. 3.7).
Реалізація матричних методів виконання операції множення вимагає більшої кількості апаратури, ніж методів послідовного аналізу розрядів або груп розрядів множника, і дає більший виграш у часі. Однак у зв'язку зі значним розвитком мікроелектроніки обмеження щодо кількості апаратури стають усе менш суворими, тому матричні методи широко застосовують на практиці.
Рис. 3.7. Дерево суматорів
3.4. МНОЖЕННЯ ЧИСЕЛ З ПЛАВАЮЧОЮ КОМОЮ
Для чисел і , що представлені в формі з плаваючою комою, добуток обчислюється за формулою:
,
де , .
Звідси випливає, що процес множення складається з чотирьох етапів:
- множення мантис;
- додавання порядків;
- нормалізація й округлення мантиси добутку;
- корегування порядку добутку.
Перші два етапи можуть виконуватись одночасно, оскільки вони незалежні один від одного. При цьому множення мантис може бути здійснене будь-яким з розглянутих методів множення.
У загальному випадку результат множення мантис може бути одержаний в ненормалізованій формі. Причому порушення нормалізації можливо тільки зліва. Воно усувається шляхом зсуву коду мантиси на один розряд вліво і, відповідно, корегується порядок добутку шляхом віднімання одиниці від суми порядків. Округлення мантиси здійснюється додаванням одиниці до (п
+1)-го розряду.
Під час виконання операції множення чисел з плаваючою комою можуть мати місце такі особливі випадки.
Якщо порядок результату є найбільшим від'ємним числом, то необхідно формувати машинний нуль.
Коли виникає переповнення додатного порядку і воно не усувається після нормалізації і корегування порядку, то необхідно формувати ознаку переповнення порядку.
Ці особливі випадки можна передбачити в алгоритмі операції множення введенням корегування добутку на підставі ознак результату.
3.5. МЕТОДИ ДІЛЕННЯ ЧИСЕЛ В ЦОМ
3.5.1. Основні уявлення про ділення чисел
Одним з найдавніших вважається давньоєгипетський спосіб ділення, що заснований на використанні операцій подвоєння і порівняння. Розглянемо його реалізацію на прикладі.
Приклад 3.15.
Поділити число А
= 1075 на число В
= 25.
Розв'язання
. Складаються два стовпчики. В лівому стовпчику розташовуються степені двійки, а у правому стовпчику перше число дорівнює В
, а кожне наступне є подвоєним попереднім числом. Кожне число, що утворюється у правому стовпчику, порівнюють з діленим 1075. Як тільки буде утворено число 1600, яке більше за ділене 1075, то попереднє число лівого стовпчику, а саме, 32 помічається зірочкою. При цьому визначається різниця 1075 - 800 = 275, яка є остачею. Далі вона порівнюється з числами правого стовпчику у напряму, який вказує стрілка, до утворення чергової остачі. Результат ділення утворюється додаванням чисел лівого стовпчику, що помічені зірочками, тобто 32 + 8 + 2 + 1 = 43.
Ділення двійкових чисел багато в чому аналогічне діленню десяткових чисел. Процес ділення полягає в тому, що послідовно розряд за розрядом відшукуються цифри частки шляхом підбора з наступним множенням цієї цифри на дільник і відніманням цього добутку від діленого.
Існує багато різних методів виконання операції ділення, серед яких найвідоміші такі.
Насамперед це - "шкільний" алгоритм ділення, який полягає в тому, що дільник на кожному кроці віднімається стільки разів від діленого (починаючи зі старших розрядів), скільки це можливо для одержання найменшої додатної остачі. Тоді в черговий розряд частки записується цифра, яка дорівнює кількості дільників, що містяться в діленому на даному кроці. Таким чином, весь процес ділення зводиться до операцій віднімання і зсуву.
Інший метод виконання операції ділення полягає в множенні діленого на обернене значення дільника
.
Тут виникає нова операція - обчислення оберненого значення, що здійснюється за відомими наближеними формулами (наприклад, розкладанням у біноміальний ряд Ньютона і т.п.). У цьому випадку до складу команд машини повинна входити спеціальна операція для визначення оберненого числа.
До найбільш розповсюджених методів виконання операції ділення відноситься також метод, що полягає у використанні наближеної формули для визначення частки від ділення двох чисел. Від методу ділення шляхом множення діленого на обернене значення дільника він відрізняється тільки тим, що частка визначається за деякою формулою шляхом виконання операцій додавання, віднімання і множення.
Два останні методи, як правило, реалізуються за підпрограмами, що потребують значних витрат часу, тому вони придатні для використання тільки в спеціалізованих машинах, в програмах яких операція ділення чисел зустрічається досить рідко. В більшості сучасних ЦОМ є спеціальний операційний блок, який здійснює ділення чисел. В універсальних обчислювальних машинах, як правило, реалізується різновид "шкільного" алгоритму ділення.
3.5.2. Ділення чисел з фіксованою комою
Нехай А
- ділене, В
- дільник і С
- частка. Найпростіше ділення виконується в прямому коді. У разі представлення чисел , і у формі з фіксованою комою, воно реалізується у два етапи. На першому етапі визначається знак частки шляхом додавання за модулем два цифр знакових розрядів діленого і дільника (див. табл. 3.1). На другому етапі здійснюється ділення модулів початкових чисел і , округлення модуля частки, після чого до нього дописується знак, що визначений на першому етапі.
На відміну від множення чисел з фіксованою комою, в процесі якого принципово неможливе переповнення розрядної сітки, ділення дробових чисел може призвести до переповнення розрядної сітки і, отже, до неправильного результату. Тому для уникнення такої ситуації має виконуватись умова: .
Відомо два основних метода ділення чисел, а саме: ділення з відновленням та без відновлення остач.
Алгоритм ділення модулів чисел з відновленням остач
полягає у виконанні таких дій.
П. 1. Подвоїти модуль діленого .
П. 2. Відняти від подвоєного модуля діленого модуль дільника. Одержана різниця є першою остачею.
П. 3. Проаналізувати знак остачі R
. Якщо , то черговому розряду частки присвоїти цифру 1 і перейти до п. 5; якщо ж R
< 0, то черговому розряду частки присвоїти цифру 0.
П. 4. Відновити остачу, додавши модуль дільника .
П. 5. Подвоїти остачу.
П. 6. Визначити чергову остачу, віднявши від попередньої остачі модуль дільника. Перейти до п. 3.
П. 3 - п. 6 виконувати до одержання всіх необхідних цифр частки.
За своїм характером операція ділення відноситься до операцій, що дають не завжди точний результат, тому ознакою закінчення операції ділення може бути досягнення заданої точності. Якщо в процесі ділення одержується остача R
= 0, то операція зупиняється й у решту розрядів частки записується нуль. Звичайно формальною ознакою кінця операції ділення є одержання такої самої кількості розрядів у частці, яку мають операнди.
Подвоєння діленого та остачі практично виконується шляхом зсуву коду вліво на один розряд.
Приклад 3.16.
Поділити число А
= - 0, 10100 на число В
= 0, 11011, використовуючи метод ділення з відновленням остач.
Розв'язання
. Для даних чисел маємо: =1; = 0, 10100; =0; = 0, 11011. Визначаємо знак частки: =10=1. Віднімання будемо виконувати як додавання доповняльних кодів, тому = 1,00101.
Усі дії, що виконуються в процесі ділення, наведені в табл. 3.18.
Відповідь
: С
= - 0, 10111.
З наведеного прикладу випливає, що цифри частки є інверсними значеннями знакових розрядів чергових остач. Треба також відзначити, що результат подвоєння іноді може бути > 1. Однак таке переповнення розрядної сітки усувається на наступному кроці алгоритму, оскільки після подвоєння завжди виконується віднімання.
Основні недоліки розглянутого методу ділення такі:
- аритмічність процесу ділення, яка обумовлена нерегулярністю виконання відновлення остачі, що призводить до ускладнення блоку керування діленням;
- відносно мала швидкість ділення, оскільки в середньому для половини кроків потрібно виконувати додаткове додавання, що забезпечує відновлення остач.
Для ритмізації процесу ділення можна виконувати фіктивну дію у тих випадках, коли відновлення остачі не потрібне, що призведе до збільшення часу виконання операції. Разом з тим, операцію можна спростити, якщо відмовитись від відновлення остач.
Таблиця 3.18 - Приклад ділення з відновленням остач
Алгоритм ділення модулів чисел без відновлення остач
зводиться до виконання таких дій.
П. 1. Подвоїти модуль діленого .
П. 2. Відняти від подвоєного модуля діленого модуль дільника. Одержана різниця є першою остачею.
П. 3. Проаналізувати знак остачі R
. Якщо , то черговому розряду частки присвоїти цифру 1; якщо ж R
< 0, то черговому розряду частки присвоїти цифру 0.
П. 4. Подвоїти остачу.
П. 5. Визначити чергову остачу, віднявши від попередньої остачі модуль дільника якщо і додавши до попередньої остачі модуль дільника якщо R
< 0. Перейти до п. 3.
П. 3 - п. 5 виконувати до одержання всіх необхідних цифр частки.
Приклад 3.17.
Поділити число А
= - 0, 10100 на число В
= 0, 11011, використовуючи метод ділення без відновлення остач.
Розв'язання
. Для даних чисел маємо: =1; = 0, 10100; =0; = 0, 11011. Визначаємо знак частки: =10=1. Віднімання будемо виконувати як додавання доповняльних кодів, тому = 1,00101.
Усі дії, що виконуються в процесі ділення, наведені в табл. 3.19.
Відповідь
: С
= - 0, 10111.
В наведених алгоритмах пункт "Подвоєння остачі" можна замінити пунктом "Зменшити в два рази модуль дільника". В машині це буде відповідати зсуву дільника, а не остачі. Наявність двох варіантів зсуву для двох алгоритмів ділення приводить до чотирьох основних алгоритмів машинного ділення:
- ділення з відновленням остач і зі зсувом дільника;
- ділення з відновленням остач та з їх зсувом;
- ділення без відновлення остач і зсувом дільника;
- ділення без відновлення остач та з їх зсувом.
Алгоритми ділення з відновленням остач не знаходять практичного застосування в машинах у силу наведених вище причин, тому на рис. 3.8, а
і б
приведені тільки структурні схеми пристроїв для ділення без відновлення остач.
Для реалізації варіанта а
необхідні 2n-
розрядний регістр дільника (РгВ) з колами зсуву вправо, 2n-
розрядний нагромаджувальний суматор (НСМ), (п
+1)-розрядний регістр частки (РгС) з колами зсуву вліво, суматор за модулем два (М2), блок інвертування цифр (БІЦ) і блок керування (БК).
Таблиця 3.19 - Приклад ділення без відновлення остач
Перед початком ділення в нагромаджувальний суматор НСМ записується ділене. За допомогою М2 визначається цифра знакового розряду частки, що записується в знаковий розряд регістра РгС. Передавання модуля дільника в НСМ для додавання або віднімання забезпечується блоком керування, що аналізує цифру знакового розряду НСМ. Ця знакова цифра остачі, проходячи через блок БІЦ, інвертується і подається в молодший розряд регістра частки, де вона зсувається вже як цифра частки.
Для реалізації варіанта б
необхідні: (п
+ 1)-розрядний регістр дільника; (п
+ 1)-розрядний регістр частки з колами зсуву вліво і (n
+ 1)-розрядний суматор з колами зсуву вліво. Решта блоків така сама, як для варіанта а
.
а
)
б
)
Рис. 3.8. Варіанти пристроїв для ділення без відновлення остач:
а
- зі зсувом дільника; б
- зі зсувом остач
Аналіз обох схем показує, що апаратні витрати на реалізацію варіанта б
менше, ніж варіанта а
. Проте у варіанті б
неможливо сумістити додавання і зсув, оскільки додавання в НСМ можна тільки після закінчення зсуву коду остачі в нагромаджувальному суматорі. В варіанті а
кожну цифру дільника з відповідного розряду регістра РгВ можна одночасно передавати за двома адресами: в сусідній правий розряд цього регістра (зсув) і у відповідний розряд НСМ, тобто починати виконувати додавання модуля дільника (або його доповнення) до остачі. Виходячи з цього, час ділення за алгоритмом без відновлення остач і зі зсувом дільника дорівнює , тоді як зі зсувом остач - .
3.5.3. Ділення чисел, що представлені в доповняльному коді
Коли в пам'яті машини числа зберігаються в доповняльному коді, то виникає задача пошуку найраціональніших методів ділення в доповняльному коді. Так само як і в разі множення, тут можливі два варіанти:
- переведення операндів у прямий код, одержання частки звичайним способом і переведення його в доповняльний код перед записом у пам'ять;
- ділення операндів у доповняльному коді з одержанням частки в необхідному вигляді.
Реалізація другого варіанта так само проста, як і першого. Необхідно тільки керувати логікою утворення цифр частки. Принципово є можливість одержувати ці цифри як з виходу БІЦ, так і минаючи цей блок. При цьому буде формуватись обернений код частки, який неважко перетворити в доповняльний код. Практична реалізація такого ділення може бути організована двома шляхами:
- аналізуючи знаки операндів блок керування БК організує передавання знакових цифр остач із НСМ в регістр частки так, щоб результат завжди формувався в оберненому коді (тобто додатна частка складалась із прямих значень цифр, а від'ємне - з обернених);
- аналізуючи знаки операндів блок БК організує спочатку або віднімання модуля дільника від модуля діленого, або віднімання модуля діленого від модуля дільника, для того щоб логіка утворення частки в разі всіх можливих комбінацій знаків операндів залишалась незмінною. Разом з тим частка має обов'язково формуватись в оберненому коді.
Розглянемо чотири можливих випадки, що обумовлені комбінаціями знаків доповняльних кодів операндів.
Випадок 1. А
> 0; B
> 0; C
= A
/B
> 0.
Ділення виконується як звичайно: знак частки визначається шляхом додавання знакових цифр операндів за модулем 2 і одночасно формується доповнення модуля дільника до двох. Цифри частки одержуються шляхом інвертування знакових цифр остач в БІЦ.
Випадок 2. А
> 0; B
< 0; C
= A
/B
< 0.
Ділення починається з віднімання модуля дільника від діленого. У разі відсутності переповнення розрядної сітки знак першої остачі обов'язково буде дорівнювати 1. Отже, його потрібно без інвертування надіслати до знакового розряду РгС. Продовжується ділення звичайним шляхом, але знакові цифри остач надходять до регістра частки минаючи БІЦ. По закінченню ділення в РгС утворюється обернений код від'ємної частки. Додаванням одиниці до (п
+ 1)-го розряду частки здійснюється одночасно округлення частки і переведення оберненого коду в доповняльний.
Приклад 3.18.
Поділити число А
= 0,1010 на число В
= - 0,1101, використовуючи ділення в доповняльному коді.
Розв'язання
. Для даних чисел маємо: [А
]д
= 0,1010; [В
]д
= 1,0011.
Усі дії, що виконуються в процесі ділення, наведені в табл. 3.20. Обернений код частки має вигляд 1,00111. Додавши одиницю до наймолодшого розряду і відкидаючи його, одержимо [С
]д
= 1,0100
Відповідь
: С
= - 0,1100.
Таблиця 3.20 - Приклад ділення в доповняльному коді для випадку А
> 0 і B
< 0
Випадок 3. А
< 0; B
> 0; C
= A
/B
< 0.
Цей випадок є дзеркальним відображенням попереднього. Отже, для того щоб одержати обернений код від'ємної частки, необхідно надсилати знакові цифри остач до регістра частки через БІЦ. Наприкінці ділення, так саме як у другому випадку, необхідно додати одиницю до (п
+ 1)-го розряду частки для переведення його в доповняльний код і округлення одночасно.
Приклад 3.19.
Поділити число А
= - 0,1010 на число В
= 0,1101, використовуючи ділення в доповняльному коді.
Розв'язання
. Для даних чисел маємо: [А
]д
= 1,0110; [В
]д
= 0,1101.
Усі дії, що виконуються в процесі ділення, наведені в табл. 3.21. Обернений код частки має вигляд 1,00111. Додавши одиницю до наймолодшого розряду і відкидаючи його, одержимо [С
]д
= 1,0100
Відповідь
: С
= - 0,1100.
Таблиця 3.21 - Приклад ділення в доповняльному коді для випадку А
< 0 і B
> 0
Випадок 4. А
< 0; B
< 0; C
= A
/B
> 0.
Ділення починається з віднімання модуля діленого від модуля дільника. Для цього достатньо перетворити попередньо тільки код дільника. В процесі ділення знакові цифри остач необхідно надсилати до регістра частки без інвертування, минаючи БІЦ, оскільки частка має бути додатною, а її доповняльний код - співпадати з прямим.
3.5.4. Особливості ділення чисел з плаваючою комою
Для чисел і , що представлені в формі з плаваючою комою, частка визначається за формулою:
де , .
Звідси випливає, що процес ділення складається з чотирьох етапів:
- ділення мантис;
- віднімання порядків;
- нормалізація мантиси частки;
- корегування порядку частки.
Перші два етапи можуть виконуватись одночасно, оскільки вони незалежні один від одного. При цьому ділення мантис повністю співпадає з діленням чисел, що представлені в формі з фіксованою комою. Відміна полягає лише в тому, що мантиси операндів можуть співвідноситись одна з одною довільно. Оскільки мантиси діленого і дільника - нормалізовані числа, то можливі такі випадки: ; .
Коли мантиса діленого більше або дорівнює мантисі дільника, то на початку ділення одержується цифра частки, що дорівнює 1 і яка записується в цілу частину частки. Решта дій над мантисами аналогічні діям над числами, що представлені в формі з фіксованою комою. Одержана при цьому мантиса частки буде мати порушення нормалізації праворуч. Воно усувається шляхом зсуву коду мантиси на один розряд управо і, відповідно, корегується порядок частки шляхом додавання одиниці до різниці порядків.
Коли мантиса діленого менше мантиси дільника, то на початку ділення одержується цифра частки, що дорівнює 0 і яка записується в цілу частину частки. Далі ділення мантис продовжується за правилами ділення чисел, що представлені в формі з фіксованою комою. Одержана при цьому мантиса частки буде мати нормалізовану форму.
Під час виконання операції ділення чисел з плаваючою комою можуть мати місце такі особливі випадки.
Якщо дільник дорівнює нулю, то формується сигнал "Зупинка машини".
Оскільки в процесі ділення порядки віднімаються, то можливе переповнення розрядної сітки порядків. Коли виникає переповнення в бік від'ємних значень порядку і воно не усувається після нормалізації і корегування порядку, то мантисі результату приписується машинний нуль, а порядку - найбільше від'ємне число.
У разі переповнення додатного порядку необхідно формувати ознаку переповнення порядку.
Ці особливі випадки можна передбачити в алгоритмі операції ділення введенням аналізатора дільника на нуль і корегування частки на підставі ознак результату.