РЕФЕРАТ
натему:”ВИКОНАННЯ ОПЕРАЦІЙ МНОЖЕННЯ І ДІЛЕННЯ В ДВІЙКОВІЙ СИСТЕМІ ЧИСЛЕННЯ ”
ВИКОНАННЯОПЕРАЦІЙ МНОЖЕННЯ І ДІЛЕННЯ В ДВІЙКОВІЙ СИСТЕМІ ЧИСЛЕННЯ
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. Визначаємо знакдобутку: />=1/>0=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. Визначаємо знакдобутку: />=1/>1=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. Визначаємо знакдобутку: />=0/>0=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. Визначаємо знакдобутку: />=0/>0=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. Визначаємо знакдобутку: />=0/>0=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 А=[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
Таблиця 3.9 — Другий приклад множення обернених кодів
/>/>/>/>/>/>/>
Відповідь: С= 0, 0101111100.
3.2.4.Множення доповняльних кодів чисел
У випадках, количисла в машині зберігаються в доповняльних кодах, доцільно всі операції надчислами робити на суматорі доповняльного коду. Однак при цьому під час множеннявиникає ряд особливостей, які необхідно враховувати. Тому розглянемо правиламноження операндів, що представлені в доповняльному коді.
Нехай множене А — будь-яке число, а множникB > 0, тобто А = [A]ді [В]д/>. Тоді
/>.
Згідно з теоремоюпро додавання доповняльних кодів можна стверджувати, що права частина цього співвідношеннявідповідає доповняльному коду результату. Таким чином, у випадку додатногомножника добуток доповняльних кодів співмножників дорівнює доповняльному кодурезультату.
Розглянемовипадок, коли множене А — будь-яке число, а множник B А=[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
Таблиця 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. Визначаємо знакдобутку: />=1/>0=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 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1
0 /> 1 1 1
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 додатних і від'ємних одиниць у перетвореному.
Відповідь: 010/>000/>100110100/>.
Коли одразуаналізуються два розряди перетвореного множнику, то в процесі множеннявиконуються такі дії.
Якщо групамістить комбінацію 00, то це означає, що протягом двох найближчих циклівмноження не потрібно буде виконувати ні додавань, ні віднімань; при наявностікомбінації 01 потрібно буде виконати одне додавання в першому з двох найближчихциклів множення, а у разі комбінації 10 — у другому. Коли група міститькомбінацію 0/>, то буде потрібно виконати одневіднімання в першому з двох найближчих циклів множення.
У разіодночасного аналізу двох розрядів, починаючи зі старших, у правилахперетворення груп розрядів (табл. 3.15) враховується значення сусідньогорозряду, що розташований праворуч від групи, яка аналізується. При цьому аналізрозрядів множника завжди починається з пустої групи, що дописується ліворуч віднайстаршого розряду.
Приклад 3.13. Використовуючи групуваннярозрядів, виконати перетворення множнику 001011111001100111, починаючи зістарших розрядів.
Розв'язання. Діючи за правилами, що наведені втабл. 3.15, одержимо
/>/>/>/>/>/>
Замість 11одиниць у вихідному представленні множника одержуємо 7 додатних і від'ємних одиниць у перетвореному.
Відповідь: 010/>0000/>010/>0100/>.
Той чи іншийметод перетворення тим ефективніше, чим менше в перетвореному множнику середнякількість додатних і від'ємних одиниць, тобто чим менше в середньому потрібнододавань і віднімань. Важлива також максимальна кількість додавань і віднімань,що можуть виконуватись під час множення.
Таблиця 3.15 — Правила перетворення множнику, починаючи зі старших груп розрядів
/>
/>
/>
/>
/>
/> 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0
/> 0 1 0 1
0 /> 1 1
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 +А 1 0 0 0
— (6А+А)
+(6А+2А) 0 0 0 1
+2А
+А 1 0 0 1
— 6А
— (6А+А) 0 0 1 0
+3А
+2А 1 0 1 0
— (3А+2А)
— 6А 0 0 1 1
+(2А+2А)
+3А 1 0 1 1
— (2А+2А)
— (3А+2А) 0 1 0 0
+(3А+2А)
+(2А+2А) 1 1 0 0
— 3А
— (2А+2А) 0 1 0 1
+6А
+(3А+2А) 1 1 0 1
— 2А
— 3А 0 1 1 0
+(6А+А)
+6А 1 1 1 0
— А
— 2А 0 1 1 1
+(6А+2А)
+(6А+А) 1 1 1 1
— А
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. Визначаємо знакдобутку: />=0/>0=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
П. 4. Відновитиостачу, додавши модуль дільника />.
П. 5. Подвоїтиостачу.
П. 6. Визначитичергову остачу, віднявши від попередньої остачі модуль дільника. Перейти до п.3.
П. 3 — п. 6виконувати до одержання всіх необхідних цифр частки.
За своїмхарактером операція ділення відноситься до операцій, що дають не завжди точнийрезультат, тому ознакою закінчення операції ділення може бути досягненнязаданої точності. Якщо в процесі ділення одержується остача R = 0, то операція зупиняється й урешту розрядів частки записується нуль. Звичайно формальною ознакою кінцяоперації ділення є одержання такої самої кількості розрядів у частці, яку маютьоперанди.
Подвоєнняділеного та остачі практично виконується шляхом зсуву коду вліво на одинрозряд.
Приклад 3.16. Поділити число А = — 0, 10100 на число В = 0, 11011, використовуючи метод ділення звідновленням остач.
Розв'язання. Для даних чисел маємо: />=1; /> = 0, 10100; />=0; /> = 0, 11011. Визначаємо знакчастки: />=1/>0=1. Віднімання будемовиконувати як додавання доповняльних кодів, тому />= 1,00101.
Усі дії, що виконуютьсяв процесі ділення, наведені в табл. 3.18.
Відповідь: С= — 0, 10111.
З наведеногоприкладу випливає, що цифри частки є інверсними значеннями знакових розрядівчергових остач. Треба також відзначити, що результат подвоєння іноді може бути> 1. Однак таке переповнення розрядної сітки усувається на наступному кроціалгоритму, оскільки після подвоєння завжди виконується віднімання.
Основні недолікирозглянутого методу ділення такі:
- аритмічністьпроцесу ділення, яка обумовлена нерегулярністю виконання відновлення остачі, щопризводить до ускладнення блоку керування діленням;
- відносномала швидкість ділення, оскільки в середньому для половини кроків потрібновиконувати додаткове додавання, що забезпечує відновлення остач.
Для ритмізаціїпроцесу ділення можна виконувати фіктивну дію у тих випадках, коли відновленняостачі не потрібне, що призведе до збільшення часу виконання операції. Разом зтим, операцію можна спростити, якщо відмовитись від відновлення остач.
Таблиця 3.18 — Приклад ділення з відновленням остач
/>/>/>/>/>/>/>/>/>/>/>/>/>
Алгоритмділення модулів чисел без відновлення остач зводиться до виконання таких дій.
П. 1. Подвоїтимодуль діленого />.
П. 2. Відняти відподвоєного модуля діленого модуль дільника. Одержана різниця /> є першою остачею.
П. 3.Проаналізувати знак остачі R. Якщо />, то черговому розряду часткиприсвоїти цифру 1; якщо ж R
П. 4. Подвоїтиостачу.
П. 5. Визначитичергову остачу, віднявши від попередньої остачі модуль дільника якщо /> і додавши до попередньоїостачі модуль дільника якщо R
П. 3 — п. 5виконувати до одержання всіх необхідних цифр частки.
Приклад 3.17. Поділити число А = — 0, 10100 на число В = 0, 11011, використовуючи метод ділення безвідновлення остач.
Розв'язання. Для даних чисел маємо: />=1; /> = 0, 10100; />=0; /> = 0, 11011. Визначаємо знакчастки: />=1/>0=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 C = A/B
Діленняпочинається з віднімання модуля дільника від діленого. У разі відсутностіпереповнення розрядної сітки знак першої остачі обов'язково буде дорівнювати 1.Отже, його потрібно без інвертування надіслати до знакового розряду РгС.Продовжується ділення звичайним шляхом, але знакові цифри остач надходять дорегістра частки минаючи БІЦ. По закінченню ділення в РгС утворюється оберненийкод від'ємної частки. Додаваннямодиниці до (п + 1)-го розряду частки здійснюється одночасно округленнячастки і переведення оберненого коду в доповняльний.
Приклад 3.18. Поділити число А =0,1010 на число В = — 0,1101, використовуючи ділення в доповняльномукоді.
Розв'язання. Для даних чисел маємо: [А]д = 0,1010; [В]д = 1,0011.
Усі дії, щовиконуються в процесі ділення, наведені в табл. 3.20. Обернений код частки маєвигляд 1,00111. Додавши одиницю до наймолодшого розряду і відкидаючи його,одержимо [С]д= 1,0100
Відповідь: С= — 0,1100.
Таблиця 3.20 — Приклад ділення в доповняльному коді для випадку А > 0 і B
/>/>/>/>/>/>/>
Випадок3.А B > 0; C = A/B
Цей випадок єдзеркальним відображенням попереднього. Отже, для того щоб одержати оберненийкод від'ємної частки, необхіднонадсилати знакові цифри остач до регістра частки через БІЦ. Наприкінці ділення,так саме як у другому випадку, необхідно додати одиницю до (п + 1)-горозряду частки для переведення його в доповняльний код і округлення одночасно.
Приклад 3.19. Поділити число А = — 0,1010 на число В = 0,1101, використовуючи ділення в доповняльному коді.
Розв'язання. Для даних чисел маємо: [А]д = 1,0110; [В]д = 0,1101.
Усі дії, щовиконуються в процесі ділення, наведені в табл. 3.21. Обернений код частки маєвигляд 1,00111. Додавши одиницю до наймолодшого розряду і відкидаючи його,одержимо [С]д= 1,0100
Відповідь: С= — 0,1100.
Таблиця 3.21 — Приклад ділення в доповняльному коді для випадку А B > 0
/>/>/>
Випадок4.А B C = A/B > 0.
Діленняпочинається з віднімання модуля діленого від модуля дільника. Для цьогодостатньо перетворити попередньо тільки код дільника. В процесі ділення знаковіцифри остач необхідно надсилати до регістра частки без інвертування, минаючиБІЦ, оскільки частка має бути додатною, а її доповняльний код — співпадати зпрямим.
3.5.4.Особливості ділення чисел з плаваючою комою
Для чисел /> і />, що представлені в формі зплаваючою комою, частка визначається за формулою:
/>
де />, />.
Звідси випливає,що процес ділення складається з чотирьох етапів:
- діленнямантис;
- відніманняпорядків;
- нормалізаціямантиси частки;
- корегуванняпорядку частки.
Перші два етапиможуть виконуватись одночасно, оскільки вони незалежні один від одного. Прицьому ділення мантис повністю співпадає з діленням чисел, що представлені вформі з фіксованою комою. Відміна полягає лише в тому, що мантиси операндівможуть співвідноситись одна з одною довільно. Оскільки мантиси діленого ідільника — нормалізовані числа, то можливі такі випадки: />; />.
Коли мантисаділеного більше або дорівнює мантисі дільника, то на початку діленняодержується цифра частки, що дорівнює 1 і яка записується в цілу частинучастки. Решта дій над мантисами аналогічні діям над числами, що представлені вформі з фіксованою комою. Одержана при цьому мантиса частки буде мати порушеннянормалізації праворуч. Воно усувається шляхом зсуву коду мантиси на один розрядуправо і, відповідно, корегується порядок частки шляхом додавання одиниці дорізниці порядків.
Коли мантисаділеного менше мантиси дільника, то на початку ділення одержується цифрачастки, що дорівнює 0 і яка записується в цілу частину частки. Далі діленнямантис продовжується за правилами ділення чисел, що представлені в формі зфіксованою комою. Одержана при цьому мантиса частки буде мати нормалізовануформу.
Під час виконанняоперації ділення чисел з плаваючою комою можуть мати місце такі особливівипадки.
Якщо дільникдорівнює нулю, то формується сигнал «Зупинка машини».
Оскільки в процесіділення порядки віднімаються, то можливе переповнення розрядної сітки порядків.Коли виникає переповнення в бік від'ємних значень порядку і воно не усувається після нормалізації ікорегування порядку, то мантисі результату приписується машинний нуль, апорядку — найбільше від'ємне число.
У разіпереповнення додатного порядку необхідно формувати ознаку переповнення порядку.
Ці особливівипадки можна передбачити в алгоритмі операції ділення введенням аналізаторадільника на нуль і корегування частки на підставі ознак результату.