ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6856
Скачиваний: 22
227
які можуть бути рівні 0,1 або +1, -1. У першому випадку говорять про ітераційний процес із знакопостійними приростами, в другому - із знакозмінними. На другому етапі, на підставі знайдених на першому етапі значень, визначається величина елементарної функції шляхом додавання або множення констант. Одночасне виконання двох описаних етапів методу "цифра за цифрою" називають методом Волдера, а послідовне - методом Меджіта. Відміна методів Волдера і Меджіта, що полягає у величинах ітераційних кроків, значеннях констант і послідовності виконання етапів, істотним чином впливає на точність, швидкодію і структуру операційного пристрою. Детальний аналіз показав, що метод Меджіта має вищу точність, ніж метод Волдера, проте швидкодія його реалізації нижча.
З урахуванням отриманих Вальтером результатів по уніфікації методу і шляхом об'єднання одержаних для різних функцій алгоритмів, єдиний обчислювальний алгоритм "цифра за цифрою" в двійковій позиційній системі числення можна представити в наступному вигляді:
Тут ]h[ - ціла частина від h; [p] - модуль р; fi- двійкові оператори, що приймають значення +1 або -1 залежно від знаку Yiабо Zi, і - номер ітерації, причому, ітерації 3, 12,... к, ..., 3(к-1),... повторюються двічі. Параметр р визначає тип обчислюваних функцій: р = 0 - лінійні, р = 1 - тригонометричні, р= -1 - гіперболічні; R - параметр, що визначає від чого залежить значення fi: якщо R = 0, то f = sign Zi., якщо R= 1, то fi = signYi; C. - константи. В табл. 6.10 представлені функціональні можливості розглянутого алгоритму при різних значеннях параметрів р, R і різних початкових умовах Х0, Y0, Z0. Тут Кт і Кг - коефіцієнти деформації відповідно тригонометричного і гіперболічного векторів, рівні: Кт= (П (1+2-2(і+1)))1/2 ; Кг = (П (1-2 -2(і-1)!))1/2, де знаком П позначено добуток чисел, взятих в дужки, при і = 0, 1, 2 .., n-1.
Таблиця 6.10
228
Алгоритми обчислення окремих елементарних функцій методом "цифра за цифрою" мають меншу обчислювальну складність порівняно з уніфікованим алгоритмом, тому часто їх використання є доцільнішим.
6.5.3. Табличний метод обчислення елементарних функцій
Ідея цього методу доволі проста: формується таблиця з наперед обчисленими значеннями функції для всіх значень аргументу. Тоді, коли виникає необхідність обчислення якоїсь функції, відбувається звертання до таблиці і зчитування з неї результату. Таблиця може мати, наприклад, наступний вигляд (табл. 6.11):
Таблиця 6.11
|
Аргумент |
Значення |
|
0000 0001 |
1001 0111 |
|
0000 0010 |
0011 0100 |
|
|
|
|
1111 1111 |
0011 1011 |
Часто застосовують комбінований підхід, коли деякі функції обчислюються таблично, а інші - за допомогою розкладу в ряд чи ітераційних формул уже з використанням функцій, що обчислюються таблично.
6.5.4. Таблично-алгоритмічний метод обчислення елементарних функцій
Застосування табличного методу вимагає великої за розміром таблиці при обробці аргументів з великою розрядністю, що ускладнює зберігання значень функції та їх пошук в таблиці. Тому бажано стиснути інформацію, а потім відновити її з мінімальними втратами точності. Вирішення цієї задачі можливе шляхом застосування таблично-алгоритмічного методу обчислення елементарних функцій. Для таблично-алгоритмічного методу характерна наявність арифметичних операцій, необхідних для обчислення поправки, яка додається до знайденого по таблиці значення, що залежить від старшої частини аргументу. Чим вищі вимоги до точності, тим більше арифметичних операцій необхідно виконати. При обчисленні поправки використовуються як загальний, так і частковий підходи. Загальний підхід застосовується для широкого класу функцій, а принципи використання часткового підходу ґрунтуються на застосуванні відомих тотожностей для кожної конкретної елементарної функції. При загальному підході використовується співвідношення:
f(X) = f(Xs + Xn-s) = f(Xs) + Ф( Xn-s, Xs),
де Xs - число, утворене s старшими розрядами аргументу X, Xn-s - число, утворене (n-s) молодшими розрядами аргументу X, Ф(Xn-s, Xs) - поправка.
Як видно, при загальному підході поправка залежить як від молодшої, так і від старшої частини аргументу. При частковому підході поправка в основному залежить тільки від молодшої частини аргументу. Обидва підходи передбачають використання таблич-но-апроксимаційного і таблично-ітераційного методів обчислень.
Це, зокрема, метод, що ґрунтується на представленні функції у виді суперпозиції двох підфункцій, де поправка задається у вигляді усередненого значення шуканої функції на кінцях підінтервалів, на які розбивається область визначення функції. Однак застосуван-
229
ня цього методу доцільне лише в комп'ютерах, де вимоги до точності невисокі. Можливості варіювання обчислювальною складністю та об'ємом таблиць надають методи ку-сочно-лінійної і кусочно-поліноміальної апроксимації, а також методи, що ґрунтуються на розбивці аргументу X на складові X і X , утворені відповідно його старшими та молодшими розрядами, і розкладанні функції в ряд Тейлора та використанні схеми Горнера.
6.6. Операції перетворення даних
6.6.1. Перетворення даних із формату з фіксованою у формат з рухомою комою та навпаки
Для перетворення даних із формату з фіксованою у формат з рухомою комою та навпаки спочатку мають бути визначені параметри форматів представлення даних, наприклад, це перетворення даних із формату з одинарною точністю за стандартом ІЕЕЕ-754 до 32-розрядного формату з фіксованою комою.
При перетворенні даних із формату з фіксованою у формат з рухомою комою потрібно привести мантису до прийнятого в форматі з рухомою комою діапазону (за стандартом ІЕЕЕ-754 зробити її нормалізованою), та забезпечити обчислення порядку з тим, щоб не змінилося значення числа. Потрібно відзначити, що будь-яке число в форматі з фіксованою комою може бути представлено в форматі з рухомою комою. При цьому, якщо розрядність цього числа менша або рівна розрядності мантиси, воно буде представлено точно, якщо ж більша - наближено, оскільки частина молодших розрядів буде втрачена.
При перетворенні даних із формату з рухомою у формат з фіксованою комою потрібно привести мантису до прийнятого в форматі з фіксованою комою діапазону при зведенні порядку до нульового значення з тим, щоб не змінилося значення числа.
Розглянемо кілька прикладів.
Нехай потрібно перетворити ціле число X = 7910 = 10011112, яке представлене в двійковій формі в доповняльному 16-розрядному коді, як показано на рис. 6.24, у формат з рухомою комою розрядністю п=16 = m+k, де к=6 - розрядність порядку, а m=10 - розрядність мантиси.
Значення порядку числа визначається з виразу Еx= Px+D, (D = 2k-1 = 32). Тут Рx=n-1 - початкове значення порядку, рівне розрядності числа з фіксованою комою без врахування знакового розряду, D - зміщення порядку. Тобто початкове значення експоненти рівне Е = 32+15 = 1011112 . Послідовність перетворення даних із формату з фіксованою у формат з рухомою комою показана в табл. 6.12.
Таблиця 6.12
|
Номер такту |
Мантиса |
Експонента |
|
0 |
0,000000001001111 |
101111 |
|
1 |
0,000000010011110 |
101110 |
230
|
2 |
0,000000100111100 |
101101 |
|
3 |
0,000001001111000 |
101100 |
|
4 |
0,000010011110000 |
101011 |
|
5 |
0,000100111100000 |
101010 |
|
6 |
0,001001111000000 |
101001 |
|
7 |
0,010011110000000 |
101000 |
|
8 |
0,100111100000000 |
100111 |
Таким чином, елементи числа з рухомою комою визначені. Його значення в заданих межах представлено на рис. 6.25.
Для перевірки правильності
результату перетворимо показане на
рис. 6.25 число в десяткове:
Нехай потрібно перетворити число Х=-3276810 = -10000000000000002 в формат з рухомою комою в тій самій розрядній сітці n= 16 = m+k, де к=6 - розрядність порядку, а m=10 - розрядність мантиси.
Двійковий еквівалент перетворюваного числа в 16-розрядній сітці з фіксованою комою в доповняльному коді має вигляд, показаний на рис. 6.26.
Значення порядку числа визначається з виразу Ех = Рх+D (D = 2k-1 = 32). Тобто початкове значення експоненти рівне Е = 32+15 = 1011112 . Як видно з рис. 6.26, тут достатньо зсунути перетворюване число на один розряд праворуч, і, тим самим, отримати нормалізовану мантису, залишивши на місці знаковий розряд, та додати до початкового значення порядку одиницю. Тобто при від'ємному значенні мантиса зсувається праворуч, а до порядку добавляється одиниця. Таким чином, елементи числа з рухомою комою визначені. Його значення в заданих межах представлено на рис. 6.27.
Для перевірки вірності
результату перетворимо показане на
рис. 6.27 число в десят
кове: v
X = -0,1.248-32 = - 1000000000 000000,0 (2) = - 32768 (10).
231
6.6.2. Перетворення даних з двійково-десяткового коду в двійковий та навпаки
Як ми вже бачили в попередньому розділі, двійково-десяткова система числення - це система, у якій кожну десяткову цифру від 0 до 9 подають 4-розрядним (або більшої роз-рядності) двійковим еквівалентом. Для виконання перетворення можуть бути використані відповідні таблиці. Розглянемо приклади.
Нехай потрібно перетворити десяткове число 3691 в двійково-десятковий код.
При перетворенні кожну цифру десяткового числа перетворюють на його двійковий 4-розрядний еквівалент.
|
Десяткове число |
3 |
6 |
9 |
1 |
|
Двійково-десяткове число |
0011 |
0110 |
1001 |
0001 |
Отже, 369110 = 0011 0110 1001 00012- 10.
Нехай потрібно перетворити двійково-десяткове число 10000000011100102-10 на десятковий еквівалент.
Кожна тетрада двійково-десяткового числа перетворюється на десятковий еквівалент:
|
Двійково-десяткове число |
1000 |
0000 |
0111 |
0010 |
|
Десяткове число |
8 |
0 |
7 |
2 |
Отже, 1000 0000 0111 00102_10 = 807210.
Аналогічним чином здійснюється перетворення й інших кодів.
6.7. Операції реорганізації масивів і визначення їх параметрів
Масив - це впорядкований скінчений набір даних одного типу, які зберігаються в послідовно розташованих комірках оперативної пам'яті і мають спільну назву. Масив складається з елементів. Кожний елемент має ім'я та індекси, за якими його можна знайти в масиві. Кількість індексів елемента визначає розмір масиву. У математиці поняттю масив відповідають поняття вектора та матриці.
Характеристикою масиву є його розмір - загальна кількість елементів у масиві. Інша характеристика масиву - його розмірність, оскільки масиви можуть бути як одновимір-ні, так і багатовимірні, а також розміри в кожному з вимірів.
Над масивами можуть виконуватись наступні операції: сортування, пошук максимуму або мінімуму, вибір заданого масиву, зсув елементів масиву, стиск масиву, визначення параметрів масиву.
Алгоритм сортування - це алгоритм для впорядкування елементів масиву. До алгоритмів сортування належать такі: сортування за методом бульбашки, сортування методом вставок, сортування злиттям, цифрове сортування, порозрядне сортування, двійкове дерево сортування, блокове сортування, сортування методом вибору, сортування методом Шелла та інші.
232
Розглянемо основні принципи виконання декількох вищеназваних алгоритмів сортування. Завдання сортування полягає в здійсненні перестановки елементів масиву таким чином, щоб впорядкувати їх по зростанню чи спаданню їх значень.
При виконанні сортування за методом бульбашки максимальні елементи ніби бульбашки спливають до початку масиву.
При сортуванні вставкою впорядкування елементів масиву здійснюється шляхом порівняння елемента масиву з усіма іншими та його розміщення відповідно до його значення.
При сортуванні за методом вибору впорядкований масив будується шляхом багаторазового застосування вибору мінімального елемента з масиву, його вилученням з масиву і додаванням в кінці нового масиву, який спочатку має бути порожнім.
Сортування за методом бульбашки, вставкою та за методом вибору виконується за пропорційну квадрату розміру масиву чисел кількість порівнянь.
Завдання пошуку максимуму або мінімуму вирішується шляхом розбиття масиву на підмасиви, аж до масиву із двох елементів, та рекурсивного вибору з них більшого або меншого. На рис. 6.28 приведено приклад послідовності дій при знаходженні максимуму або мінімуму для масиву із 8 чисел.
Задачі зсуву елементів масиву по заданій координаті, транспонування масиву та визначення параметрів масиву, а також операція стиску (розширення) масиву по заданій координаті, вирішуються шляхом роботи з адресами його елементів у пам'яті.
6.8. Операції обробки символів та рядків символів
Є два типи операцій над символами - аналіз, тобто визначення значення символу, і перетворення, тобто зміна значення кодів символів. До основних операцій над символами належать наступні:
• Ідентифікація. Ця операція дозволяє визначити відповідність (невідповідність) значення коду аналізованого символу X коду заданого символу С. Ідентифікація символу X виконується шляхом перевірки збігу коду символу X з кодом символу С, розміщених в основній пам'яті або регістрах, і вказаних відповідними адресами. Результатом операції