Множник В можна розбити на будь-яку кількість частин, але найефективнішим, з точки зору комплексної оцінки апаратних і часових витрат, є розбиття на дві частини. Для цього випадку обчислення описуються такою формулою:
.
Якщо множення на частини виконується за першим і другим методами, то час множення дорівнює:
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.
Страницы: 1, 2, 3, 4, 5, 6
