Машинні алгоритми операції ділення

Прискорені алгоритми множення. Алгоритм Бута

Цей алгоритм передбачає аналіз наявності підряд слідкуючих одиниць множника з тим, щоб замінити множення на N одиниць на 2ⁿ-1. Для цього аналізуються два розряди другого множника. При найбільш сприятливому поєднанні цифр множника кількість складань рівна n/2, де n - число розрядів множника.

Наведемо ще один приклад множення за покращеним алгоритмом Бута, в якому використовуються ті ж самі множники, що і у попередніх прикладах за класичними схемами. При цьому другий множник зсувається одразу на два розряди праворуч.

Початковий стан

Перший крок

Другий крок

Третій крок

Четвертий крок

Як бачимо, результат такий самий, як і у попередніх прикладах.

Машинні алгоритми операції ділення

Машинне ділення організовано за тією ж схемою, як й звичайне десяткове ділення. Тобто, починаючи зі старших розрядів діленого, віднімається дільник і формує чепнрві цифри результату, починаючи зі старшої. Якщо результат віднімання додатній, то чергова цифра результату ділення, починаючи із старшої цифри, дорівнює 1, інакше 0 і повторювати ці дії, зсуваючи праворуч на один розряд дільник, доки кількість розрядів діленого операнду, не буде менше за кількість цифр дільника.. Якщо при черговому відніманні дільника результат буде від’ємний, то треба відновити від’ємний залишок. Від’ємний залишок можна і не відновлювати, якщо на наступному кроці віднімання замінити на додавання. Припустимо, що і-му кроці маємо від’ємний результат. Тобто, ми віднімали 2^і*D, де D – це дільник. При відновленні від’ємного залишку виконується +2^і*D та чергове віднімання -2^(і-1)*D, тобто фактично виконується додавання +2^(і-1)*D. Звідси існує два алгоритми множення: з відновленням від’ємного залишку та без його відновлення.

При діленні із відновленням від’ємного залишку алгоритм складається із таких кроків: 1) до старшої частини числа, що ділиться, додається додатковий код дільника, якщо результат додатній, чергова цифра результату ділення буде 1. 2) Від’ємний залишок відновлюється за допомогою прямого коду дільника. Вказані дії повторюються циклічно. Кількість кроків в циклі обмежується останньою двійковою цифрою діленого.

В разі ділення без відновлення від’ємного залишку маємо два коди дільника – прямий та додатковий. Цей алгоритм заснований на тому, що замість відновлення від’ємного залишку виконується додавання прямого коду дільника до від’ємного залишку.

Алгоритм машинного ділення у відповідних машинних командах реалізований як мікропрограма (низка мікрокоманд).

Приклад машинного ділення за алгоритмом з відновлюванням від’ємного залишку. Для прикладу візьмемо результат попереднього множення та один з множників. В результаті ділення отримаємо другий множник.

-11001010

1011100111000110 від’ємний залишок

[phone] відновлення

-11001010

0001111011000110 чергова цифра результату - 1

-11001010

1110110001000110 від’ємний залишок

[phone] відновлення

0001111011000110 чергова цифра результату - 0

-11001010

0000010110000110 чергова цифра результату - 1

-11001010

[phone] відновлення

0000010110000110 чергова цифра результату – 0

-11001010

[phone] відновлення

0000010110000110 чергова цифра результату – 0

-11001010

0000001001011110 чергова цифра результату - 1

-11001010

0000000011001010 чергова цифра результату - 1

-11001010 чергова цифра результату - 1

Як бачимо, в результаті ділення тримали значення другого множника з попереднього прикладу.

Дата добавления: 2015-11-14