Виконання операцій множення і ділення у двійковій системі числення (стр. 7 из 9)

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

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

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 виконувати до одержання всіх необхідних цифр частки.