Програмне моделювання машинних алгоритмів ділення чисел з фіксованою крапкою

Лабораторна робота № 4

Мета роботи: Розглянути машинні алгоритми виконання операції ділення над числами у форматі з фіксованою крапкою

Теоретичні відомості: Машинне ділення організовано за тією ж схемою, як й звичайне десяткове ділення.

Алгоритм полягає в тому, що дільник спочатку зсувається вліво до старшого розряду діленого, а далі на кожнім кроці з діленого віднімається дільник, помножений на цифру частки. При цьому цифра частки підбирається так, щоб при вирахуванні вийшло найменше ненегативне число. Далі залишок від вирахування приймається за ділене. У випадку двійкової системи числення чергова цифра частки виходить з порівняння діленого і дільника. Порівняння це виробляється шляхом вирахування дільника з діленого. Якщо дільник менше (різниця менше нуля), то цифра частки приймається рівної 1, інакше - 0. В другому випадку ділене після порівняння необхідно відновити, додавши до нього регістр дільника. Далі дільник зсувається вправо на 1 розряд і операція продовжується ще n раз. Усього ж операція порівняння проводиться (n+1) раз.

Машинний алгоритм цього методу ділення в застосуванні до двійкових чисел представлений нижче:

Ділення з відновленням залишку. Вихідні дані: ділене в регістрі діленого, дільник у регістрі дільника і нуль у регістрі частки.

1. Зрушуємо дільник уліво доти, поки він не стане більше діленого (або поки не збіжаться їхні старші цифри), позначимо число таких зрушень n;

2. Порівнюємо дільник і ділене. Операція порівняння проводиться за допомогою вирахування, результат заноситься в регістр діленого. Якщо при вирахуванні дільника з діленого отримали заєм (тобто ділене менше дільника), то всуваємо в регістр частки праворуч цифру нуль. Інакше заносимо одиницю і йдемо до пункту 4;

3. Відновлюємо негативний залишок у регістрі діленого до стану перед порівнянням у пункті (2). Для цього додаємо значення дільника до регістра діленого (на кроці (2) при порівнянні ми віднімали);

4. Зрушуємо дільник вправо на один розряд. Якщо не виконана (n+1) ітерація, то перейти до пункту 2.

Розглянемо приклад:

Приклад ділення з відновленням залишку

Поділимо двійкове число 11010₂ на двійкове число 101₂

Частка дорівнює 101, залишок 1.

У такий спосіб у регістрі частки сформується значення частки, а в регістрі діленого - значення залишку. Такий алгоритм ділення називається діленням з відновленням залишку і зрушенням дільника вправо. Існують і інші схеми ділення чисел з фіксованою крапкою.

Спробуємо оптимізувати алгоритм. Нехай A_i - залишок на i-тім кроці (після i-того порівняння), B - вихідний дільник. Розглянемо випадок відновлення залишку:

A_i+1 = A_i + B*2^n-i - B*2^n-i-1

де додавання відповідає відновленню залишку, вирахування - i+1-му порівнянню. Очевидно, що відновлення робити необов'язково:

A_i+1 = A_i + B*2^n-i-1

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

Розглянемо приклад:

Приклад ділення без відновлення залишку

Поділимо двійкове число 11010₂ на двійкове число 101₂

Частка дорівнює 101, залишок 1.

У випадку представлення операндів операції ділення у прямому коді знакові і числові розряди обробляються окремо, при цьому знак частки визначається шляхом додавання по модулю 2 знакових розрядів ділимого і дільника.

При виконанні ділення над операндами представленими у додатковому коді можливі наступні випадки комбінацій знаків дільника та ділимого:

1. X> 0, Y> 0, Z=X/Y> 0 (X – ділене, Y – дільник, Z – частка). В даному випадку виконання операції ділення нічим не відрізняється від ділення додаткових чисел в прямому коді.

2. X< 0, Y> 0, Z=X/Y< 0. Для отримання додаткового коду результату необхідно додати одиницю в n+1 розряд.

3. X> 0, Y< 0, Z=X/Y< 0. Для отримання додаткового коду результату необхідно додати одиницю в n+1 розряд.

4. X< 0, Y< 0, Z=X/Y> 0. На першому кроці алгоритму необхідно для формування вірного знаку частки необхідно із від’ємного діленого віднімати додатній дільник. Далі цей випадок зводиться до випадку №3. Всі цифри частки рівні знакам залишків.

Конец формы

Завдання на виконання лабораторної роботи.

1) Обрати свій номер варіанта згідно з останньою цифрою у номері залікової книжки (цифра „0” відповідає десятому варіантові).

2) Створити блок-схему алгоритму ділення множення чисел з фіксованою крапкою згідно варіанту.

3) Проаналізувати текст паскаль-програми у файлі lab4_var_”N”.pas (де „N” – номер варіанту) і визначити її призначення.

4) Скомпілювати програму та запустити на виконання.

5) Підставити власні вхідні значення та проаналізувати результати роботи програми.

6) Оформити звіт та подати його викладачу разом з результатами виконання роботи.