Iндивiдуальнi контрольнi завдання

Лабораторна робота 9

Тема: Виконання алгебрачної операцiї дiлення чисел у сучасних комп`ютерах iз вiдновленням та без відновлення залишкiв.

Мета роботи: опанувати на практиці наступні ключові питання, пов`язані з виконанням алгебрачної операцiї дiлення чисел у сучасних комп`ютерах: формальні основи визначення поточної цифри частки й алго-ритм реалiзацiї дiлення чисел iз вiдновленням і без вiдновлення залишкiв.

Основні знання й уміння: знати основні відомості про дiлення чисел iз вiдновленням залишкiв у комп`ютернiй арифметицi, умiти виконувати основ-ні етапи дiлення чисел iз вiдновленням залишкiв; знати основні відомості про дiлення чисел без вiдновлення залишкiв у комп`ютернiй арифметицi, умiти виконувати основні етапи дiлення чисел без вiдновлення залишкiв.

1 ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ

1.1 Виконання алгебрачної операцiї дiлення чисел у сучасних комп`ютерах iз вiдновленням залишкiв

1.1.1 Формальні основи визначення поточної цифри частки при діленні чисел iз відновленням залишків

Ділення в комп`ютерах, так само, як і множення, найпростіше виконувати в прямому коді.

Але, на відміну від множення дробових співмножників, де не може виникнути переповнення розрядної сітки, при діленні правильних дробів таке переповнення можливе у тому випадку, коли ділене більше дільника.

Ознакою переповнення є поява одиниці в знаковому розряді частки, що сильно викривляє результат.

Знак частки при діленні в прямому коді формуться в наступний спосiб: визначається як сума по модулю 2 знакових цифр діленого та дільника; приписується частці наприкінці операції ділення.

Частка визначається шляхом ділення модулів вхідних чисел.

Для того, щоб уникнути переповнення розрядної сітки, для діленого А та дільника В повинна виконуватися наступна умова: | А| < | В |.

Якщо потрібно розділити А на В iз точністю до і-го розряду, то:

Y_i = A / B = 0, y ₁ y ₂ …y_i _-1 y_i = y₁ 2^-1+ y ₂2^-2+ y_i _-12^{-(i -1)} + y_i 2^{- i}.

(1)

При будь-якому значенні i, повинна виконуватися наступна нерівність:

0 <= A – BY_i < B *2 ^-i.

(2)

Перетворимо (2) до виду

0 <= (A – BY_i)*2 ⁱ < B

(3)

Позначивши (A – BY_i)*2 ⁱ через R_i, одержимо:

0 <= R_i < B

(4)

Частки визначаються послідовно, починаючи зі старшого розряду.

Припустимо, що в результаті виконання i циклів отримані старші i розрядів частки, тобто наближене значення частки Y_i, що задовольняє нерівності (4).

У наступному, (i + 1)-ому циклі, буде отримане значення (i + 1)-го розряду частки.

Вхідними даними для даного циклу є Y_i і R_i.

Цифра y_i ₊₁ може мати одне з двох значень: 0 або 1.

У першому випадку (y_i ₊₁ = 0), будемо мати наступне:

Y_i ₊₁ = Y_i + y_i ₊₁2^{-(i +1)} = Y_i*;	(5)
R_i ₊₁ = (A – BY_i ₊₁)2 ⁱ ⁺¹ = 2 R_i*,	(6)

тобто у частці записується нуль за умови

0 <= R_i ₊₁ = 2 R_i < B.

(7)

У другому випадку (якщо y_i ₊₁ = 1):

Y_i ₊₁ = Y_i + 2^-(i+1),	(8)
R_i ₊₁ = 2 R_i – B,	(9)

Тобто цифра частки дорівнює одиницi, якщо виконується умова

B <= 2 R_i < 2 B.

(10)

Оскільки завжди виконується лише одна з умов (або (7), або (10)), то, для визначення поточної цифри частки, досить перевірити тiльки одну з них.

1.1.2 Алгоритм реалiзацiї дiлення чисел iз вiдновленням залишкiв

У пiдсумку вище сказаного, алгоритм (правило) ділення з відновленням залишків формулюється в наведений нижче спосiб.

Етап 1. Дільник віднімається з діленого та визначається знак нульового (по порядку) залишку.

Етап 2. Залежно вiд знаку залишку, отриманого на попередньому етапi, виконуються наступнi дії:

- якщо залишок є додатним (| A | > | В |), то в псевдознаковому розряді частки проставляється одиниця, з появою якої формується ознака переповнення розрядної сітки й операція припиняється;

- якщо залишок є від’ємним, то в псевдознаковому розряді частки записується нуль, а потім здiйснюється відновлення діленого шляхом додавання до залишку дільника.

Етап 3. Виконується зсув відновленого діленого на один розряд ліворуч і повторне вирахування дільника.

Етап 4. Знак одержаного на попередньому етапi залишку визначає першу значущу цифру частки: якщо залишок є додатним, то в першому розряді частки записується 1; якщо залишок є від’ємним, то в першому розряді частки записується 0.

Етап 5. Знак залишку також визначає наведенi нижче дії.

Якщо залишок є додатним, то: залишок зсувається ліворуч на один роз-ряд; iз залишку віднімається дільник для визначення наступної цифри частки.

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

Таким чином, цифри частки виходять як інверснi значення знакових розрядів поточного залишку, що приймають значення 00 чи 11. Але, при зсуві залишку ліворуч, у знакових розрядах може виникнути сполучення 01.

У деяких випадках, для того, щоб цифри частки формувалися як пряме значення знакового розряду поточного залишку, ділення виконують iз інверсними знаками. У даних випадках: ділене передається до суматору не прямим, а інверсним кодом; на нульовому кроці виконується операція «+ B» замість операції «-В ».

Розглянемо приклад. Нехай задано числа A = 0,101 та B = 0,110. Потрiбно знайти Y = A/B. Необхiднi обчислення представлено нижче.

[- B ]_дм = 11,010. Визначення знаку частки: Sg(Y) = 0 Å 0 = 0

A 00 + B _д^м 11 101 СМ 010 Рг B Рг Y

+| B | 00 111 СМ

+ B _д^м 11 101 СМ відновлений залишок 010 СМ зсув

+ B _д^м 11 100 СМ 000 СМ зсув 010 СМ

+ B _д^м 11 010 СМ 100 СМ зсув

+| B | 00

+ B _д^м 11 100 СМ відновлений залишок 000 СМ зсув 010 СМ Округлення +1

1.2 Виконання алгебрачної операцiї дiлення чисел у сучасних комп`ютерах без вiдновлення залишкiв

Будем рассматривать двоичное деление целых чисел как основу для деления произвольных чисел, включая дроби. В выражении A / B = C делимым будем называть A, делителем - B, частным - C.

Рассмотрим вначале традиционный алгоритм деления:

- делитель сдвигается влево к старшему разряду делимого;

- на каждом шаге из делимого вычитается делитель, помноженный на цифру частного (данная цифра подбирается так, чтобы при вычитании получилось наименьшее неотрицательное число);

- остаток от вычитания принимается за делимое.

В случае двоичной системы счисления, очередная цифра частного получается из сравнения делимого и делителя, которое производится путем вычитания из делимого регистра делителя.

Если делимое больше делителя (их разность больше нуля), то: цифра частного принимается равной 0; делимое после сравнения восстанавливают, прибавляя к нему регистр делителя. Если делимое меньше делителя (их разность меньше нуля), то цифра частного принимается равной единице.

Далее делитель сдвигается вправо на один разряд, и операция продолжается еще n раз. Всего операция сравнения производится (n+1) раз.

Машинный алгоритм данного метода деления в применении к двоичным числам представлен ниже.

Исходные данные алгоритма деления с восстановлением остатка и сдвигом делителя вправо: делимое находится в регистре делимого; делитель находится в регистре делителя; ноль находится в регистре частного.

Этап 1. Сдвигаем делитель влево, пока он не станет больше делимого или пока не совпадут их старшие цифры, обозначив число сдвигов через n.

Этап 2. Сравниваем делимое и делитель. Операция сравнения призво-дится с помощью вычитания, а результат заносится в регистр делимого.

Если при вычитании из делимого делителя не было заема (делимое больше делителя), то заносим в регистр частного 1 и переходим к пункту 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. Достаточно на следующем шаге вместо операции вычитания при сравнении применить сложение.

Данный алгоритм получил название алгоритма деления без восстановления остатков.

Кроме того, вместо сдвига делителя вправо можно производить сдвиг делимого влево.

При этом, если выдвигемая старшая (знаковая) цифра равна 1, то в регистр частного вдвигается 0, и наоборот.

Ниже приведен широко распространенный алгоритм деления чисел без восстановления остатков на примере беззнаковых целых чисел (дроби приводят к правильному виду и отдельно рассматривается деление мантисс дробей как беззнаковых целых чисел).

Исходное состояние алгоритма: делимое находится в регистре суматора; делитель находится в регистре делителя; 0 находится в регистре частного.

Состояние устройства управления делением (УУД): n = 0 - в счетчике сдвигов; 1 - в разряде состояния.

Этап 1. Сдвигаем делитель влево до тех пор, пока старший после знакового разряд не станет равным 1.

Подсчитываем количество сдвигов в счетчике.

Если произошло переполнение счетчика, то имеет место деление на 0.

Этап 2. Если состояние равняется единице, то заполняем регистр делителя дополнением делителя, иначе - самим делителем.

Прибавляем делитель к делимому.

Этап 3. Сдвигаем делимое, инвертируем выдвинутую цифру устрой-ством обращения цифр (УОЦ) и вдвигаем эту цифру в регистр частного.

Состояние равняется вдвигаемой цифре.

Этап 4. Если выполнено (n+1) шагов, то переходим к шагу 5, иначе – переходим к шагу 2.

Этап 5. Сдвигаем сумматор вправо на 1 разряд.

Этап 6. Если состояние равняется нулю, то остаток необходимо восстановить, присуммировав делитель к делимому.

Этап 7. Сдвигаем остаток на n разрядов вправо, уменьшая счетчик.

Рассмотрим пример применения алгоритма деления без восстановления остатков для чисел 11010₂ (делимое) и 101₂ (делитель), результатом действия которого является частное 101 и остаток 1:

№ п/п Шаг алгоритма Регистр делимого Регистр велителя Регистр частного

Инициализация исходных данных

Cдвиг делителя до совпадения старших цифр

Cравнение

Cдвиг делителя

Cравнение

Cдвиг делителя

Cравнение путем сложения

2 КОНТРОЛЬНІ ПИТАННЯ

1. Назвати особливостi виконання операції ділення.

2. Пояснити, як визначається знак частки.

3. Назвати ознаку переповнення розрядної сітки при виконанні операції ділення.

4. Сформулювати алгоритм виконання операції ділення.

5. Навести та прокоментувати приклад виконання операції ділення.

6. Назовите исходные данные алгоритмов деления без восстановления и с восстановлением остатка.

7. Сформулируйте алгоритм деления с восстановлением остатка.

8. Охарактеризуйте алгоритм деления без восстановления остатка как результат оптимизации алгоритма с восстановлением остатка.

IНДИВIДУАЛЬНI КОНТРОЛЬНI ЗАВДАННЯ

ЗАВДАННЯ 1. Скласти схему алгоритму та виконати операцiю дiлення з відновленням залишків для чисел A i B, заданих у таблицi 1 (номер варіанту в таблицi 1 спiвпадає з порядковим номером студента за списком у журналі).

ЗАВДАННЯ 2. Скласти схему алгоритму та виконати операцiю дiлення без відновлення залишків для чисел A i B, заданих у таблицi 1 (номер варіанту в таблицi 1 спiвпадає з порядковим номером студента за списком у журналі).

Таблиця 1 – Iндивiдуальнi варiанти завдань

Номер варiанту	Значення числа A (дiлене)	Значення числа B (дiльник)
	0.010	0.110
	0.001	0.110
	-0.111	-0.010
	-0.100	0.101
	-0.101	0.111
	0.110	0.111
	-0.010	0.101
	-0.001	0.010
	-0.001	-0.011
	-0.011	-0.101
	0.101	0.110
	-0.001	-0.110
	-0.011	-0.100
	-0.010	0.110
	0.001	-0.011
	0.010	-0.110
	-0.010	0.101
	-0.101	0.110
	0.010	0.101
	-0.110	0.111
	-0.100	-0.101
	0.011	-0.101
	0.010	-0.011
	-0.011	-0.101
	-0.100	-0.101
	-0.011	0.101
	0.001	0.011
	-0.100	0.101
	-0.010	0.110
	-0.011	-0.101

Додаток А

Вимоги до оформлення, захисту та оцінювання

лабораторних робіт

Під час захисту лабораторної роботи, студент повинен здійснити:

− коротке викладення теоретичних основ і змісту визначальних етапів виконання роботи;

− демонстрацію результатів роботи;

− відповіді на питання викладача;

− подання підсумкового звіту про виконання роботи.

Звіт з лабораторної роботи повинен містити такі складові частини:

− титульний аркуш (зразок оформлення знаходиться далі, в Додатку Б);

− формулювання теми та мети лабораторної роботи;

− постановка індивідуального контрольного завдання на лабораторну роботу;

− покроковий опис ходу виконання роботи;

− опис результатів, отриманих у процесі виконання роботи;

− висновки;

− перелік використаної літератури.

Звіт про виконання лабораторної роботи може бути оформлений у наступній формі:

− письмовий (рукописний, друкований, електронний тощо);

− усний (доповідь, прокоментований показ на комп’ютері, озвучений слайдовий показ тощо);

− письмово-усний.

Електронний, усний і письмово-усний варіанти звіту припускаються тільки за дозволом викладача в тому разі, якщо студент вільно володіє темою та здатен доповісти її лаконічно, дохідливо та наочно в усній формі.

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

− за національною шкалою, тобто за чотирибальною системою („відмінно/5”, „добре/4”, „задовільно/3”, „незадовільно/2”);

− за європейською шкалою ECTS, тобто за семибальною системою (“відмінно/A”, “добре/B,C”, “задовільно/D,E”, “незадовільно/FX,F”);

− за стобальною шкалою ХНТУ.

Основними критеріями оцінювання лабораторної роботи є:

− повнота та правильність виконання завдань;

− здатність студента до творчого застосування набутих ним знань, умінь і навичок (диференціації, інтеграції та уніфікації знань; застосування правил, методів, принципів і законів у конкретних ситуаціях; інтерпретації схем, графіків, діаграм; встановлювання різниці між причинами та наслідками; аналізу та оцінювання фактів і подій, прогнозування очікуваних результатів від прийнятих рішень тощо);

− здатність студента викладати матеріал на папері логічно, послідовно, з дотриманням вимог ЄСКД та ЄСТД.

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

− „відмінно” виставляють у тому разі, якщо студент виявив: всебічні, систематизовані, глибокі знання програмного матеріалу; вміння вільно виконувати завдання; засвоєння основної та додаткової літератури, що передбачена програмою, на рівні творчого використання;

− „добре” виставляють у тому разі, якщо студент виявив: повне знання програмного матеріалу; вміння виконання завдань; засвоєння основної літератури, що передбачена програмою, на рівні аналогічного відтворення;

− „задовільно” виставляють у тому разі, якщо студент виявив: повне знання основного програмного матеріалу в обсязі, що є необхідним для подальшого навчання та роботи; здатність упоратися з виконанням завдань, які передбачено програмою, на рівні репродуктивного відтворення.

Виконання лабораторної роботи на найвищий бал (оцінку “Відмінно/5/A”) передбачає обов`язкову наявність у звіті з лабораторної роботи елементів творчої роботи над матеріалом (порівняльного огляду, аналізу, формулювання та обгрунтування раціональних пропозицій, створення презентаційних матеріалів тощо), наведення прикладів практичного використання технологій комп'ютерної арифметики.

Рекомендовано наступні види завдань творчої та практичної спрямованості:

− проаналізувати приклади ефективного використання технологій комп'ютерної арифметики в комп'ютерній підтримці підприємств (організацій, установ) на основі відомостей із фундаментальної та періодичної літератури, власного досвіду;

− проаналізувати поточний стан і розробити пропозиції щодо підвищення ефективності використання технологій комп'ютерної арифметики в комп'ютерній підтримці конкретного підприємства (організації, установи) за місцем проходження практики (місцем проживання, роботи тощо).

Виконання лабораторної роботи на оцінку “Добре/4/B,C”) передбачає розкриття поставленого завдання з наведенням прикладів практичного використання операційної системи.

Виконання лабораторної роботи на оцінку “Задовільно/3/D,E”) передбачає достатність розкриття поставленого завдання на основі репродуктивного відтворення матеріалів із запропонованого переліку літератури.

Таблиця А.1

Правила переведення балів внутрішньої 100-бальної шкали ХНТУ

в національну та європейську шкали

№ з/п	Оцінка за шкалою МОН України	Оцінка за національною шкалою	Оцінка за шкалою ECTS	Пояснення оцінки за шкалою ECTS

	90-100	Відмінно (5)	А	excellent	відмінно – відмінне вико- нання лише з незначною кількістю помилок
	75-89	82-89	Добре (4)	В	very good	дуже добре – вище середнього рівня з кількома помилками
	75-81	С	good	добре – в загальному вірне виконання з певною кіль- кістю суттєвих помилок
	60-74	67-74	Задовільно (3)	D	satisfactory	задовільно – непогано, але зі значною кількістю недоліків
	60-66
E	sufficient	достатньо – виконане за- вдання задовольняє міні-мальним критеріям
	1-59	35-59	Незадовільно (2)	FX	fail (із правом перескладання)	незадовільно з можли-вістю повторного складан-ня
	1-34
F	fail (повторний курс)	незадовільно з обов’язко-вим повторним курсом

Додаток Б