МНОЖЕННЯ ЧИСЕЛ, ЩО ПРЕДСТАВЛЕНІ В ФОРМІ З ФІКСОВАНОЮ КОМОЮ
Метод скороченого множення
Дії, що виконуються під час множення обернених кодів, залежать від знаку множника
МЕТОДИ ПРИСКОРЕННЯ ОПЕРАЦІЇ МНОЖЕННЯ
Апаратні методи прискорення операції множення в двійковій системі числення
Метод множення з запам’ятовуванням проміжних перенесень
МЕТОДИ ДІЛЕННЯ ЧИСЕЛ В ЦОМ
Ділення чисел, що представлені в доповняльному коді
Навигация
МЕТОДИ ДІЛЕННЯ ЧИСЕЛ В ЦОМ
Виконання операцій множення і ділення у двійковій системі числення
52201
знак
8
таблиц
30
изображений
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. Визначаємо знак частки: 
=1
0=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. Варіанти пристроїв для ділення без відновлення остач:
а - зі зсувом дільника; б - зі зсувом остач
Аналіз обох схем показує, що апаратні витрати на реалізацію варіанта б менше, ніж варіанта а. Проте у варіанті б неможливо сумістити додавання і зсув, оскільки додавання в НСМ можна тільки після закінчення зсуву коду остачі в нагромаджувальному суматорі. В варіанті а кожну цифру дільника з відповідного розряду регістра РгВ можна одночасно передавати за двома адресами: в сусідній правий розряд цього регістра (зсув) і у відповідний розряд НСМ, тобто починати виконувати додавання модуля дільника (або його доповнення) до остачі. Виходячи з цього, час ділення за алгоритмом без відновлення остач і зі зсувом дільника дорівнює 
, тоді як зі зсувом остач - 
.
Похожие работы
... автомата повинна містити певну кількість логічний елементів, що утворюють функціонально повну систему для синтезу необхідної комбінаційної схеми. 1.5 Контроль виконання арифметичних операцій Арифметичні операції виконуються на суматорах прямого, оберненого і доповняльного коду. Припустимо, що зображення чисел зберігаються в машині в деякому коді, тобто операція перетворення в заданий код або ...
... в іншу (найчастіше для переведення із двійкової, вісімкової та шістнадцяткової систем числення у десяткову, і навпаки). 6. Програмна реалізація Програма розроблена для перетворення чисел з однієї системи числення в іншу.Реалізована в середовищі програмування Borland C++Builder. Лістінг програми: #include <vcl.h> #pragma hdrstop #include "Unit1.h" #include <math.h> #include < ...
... льш прості операції які називаються мікроопераціями тобто кожна операція – це визначена послідовність мікрооперацій. Існують два основні типи керуючих автоматів 1. Керуючий автомат з жорсткою чи схемною логікою. Для кожної операції будується набір комбінаційних схем які в потрібних тактах збуджують відповідні керуючі сигнали. Іншими словами ...
... тову складність операцій у полі, то можна оцінити результуючу бітову складність операцій з многочленами. Щоб відрізняти арифметичну складність від бітової в оцінках ми використовуватимемо символи і . Обчислення значень многочленів. Нехай – довільне кільце. Розглянемо добре відомий алгоритм Руфіні - Горнера для обчислення значень многочлена над кільцем у точці. Останнє число ,і буде шуканим ...
0 комментариев