LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Управління процесом символьних перетворень при розв'язанні задач комп'ютерної алгебри

фізичні адреси об'єктів, або через спеціальні процедури. Система іменування А-2000 забезпечує динамічний доступ до об'єктів, які можуть спеціально формуватися у процесі звернення до них. Це, зокрема, відбувається в процесі підстановки на задане число кроків значень змінних іменуючих виразів, або це можуть бути структурні частини бездужкового запису, задані своїми координатами.

У внутрішньому поданні програма мови АНАЛІТИК подана у вигляді дескрипторної таблиці “Програма”, яка містить послідовність фізичних адрес бездужкових записів операторів, що можуть розташовуватися в будь-яких місцях пам'яті.

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

Система реалізації містить бібліотеку функцій і операторів, доступ до яких здійснюється так само за допомогою дескрипторних таблиць. Написані користувачем процедури-функції за допомогою оператора ВКЛЮЧИТИ також включаються у відповідну дескрипторну таблицю.

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

На вхід АО подаються вирази, які іменують багаторівневу ієрархічну структуру. Значення змінних утворюють складні суперпозиції, де для виконання однієї функції необхідно викликати інші функції. Алгоритми таких обчислень виконуються по “гілках” багаторівневої ієрархічної структури без попередньої підстановки значень змінних. В АО послідовно виконуються функції і операції, які утворюють таку суперпозицію. Вони виконуються в міру готовності їх операндів. Фізична адреса отриманого значення по закінченні виконання АО заноситься в рядок дескрипторної таблиці “Каталог”, що відповідає імені результату.

Особливе значення у процесі рішення задач КА має процедура зведення подібних. Ефективність процедури зведення подібних визначається частотою перевірки еквівалентності членів ряду. При цьому процес попарного порівняння надзвичайно складний і неефективний. Примусове впорядкування виразу тільки відсуває рішення проблеми, тому що всеодно вимагає впорядкування результатів.

У реалізації А-2000 при зведенні подібних над об'єктом, де порівнюються вирази з множини U, задається деяка функція f(uі), що легко обчислюється, і тільки якщо над uі й uj виконується складна процедура точного порівняння з урахуванням комутативності й асоціативності. Час зведення подібних можна оцінити


,


де t1 - час обчислення f(uі);

t2 - середній час точного порівняння uі й uj ;

- число збігів ;

n - число операндів багатомісної операції, що виконується.

Такий підхід практично виправдується тим, що , , де p(n)- імовірність і, якщо uі й uj еквівалентні, то , і при достатній складності виразів множини подібні зустрічаються рідко й імовірність мала та зменшується з ростом n. Звідси для багатомісних операцій така перевірка негативних гіпотез приводить до того, що час зведення подібних асимптотично наближається до лінійної залежності від n.

Подібним чином відбувається зведення подібних при виконанні таких багатомісних операцій, як “+”, “*”,“&”, “”. При цьому як f(uі) в А-2000 використовується сума двійкових кодів запису uі .

Процедура ділення цілих чисел має особливе значення для реалізації операцій над раціональними дробами, тому що забезпечує автоматичне скорочення чисельника й знаменника в раціональному дробі. Реалізація операцій над раціональними дробами в системі А-2000 відрізняється тим, що при такому скороченні не виконується окремо ділення чисельника й знаменника на найбільший спільний дільник. Замість цього, паралельно із процедурою алгоритму Евкліда, чисельник і знаменник обчислюються за рекурентними формулами відповідно


;


;


,


де Dі - результат i-го кроку алгоритму Евкліда після видалення множників виду ,

u - чисельник,

v - знаменник,

- число нульових розрядів наприкінці результату кроку алгоритму Евкліда.

Ознакою закінчення процедури є . Результат ділення.

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

Розглянемо як приклад диференціювання виразу


. (1)


Таблиця 3

Об'єм результатів диференціювання (без звичайних спрощень)

Порядок похідної (k)

1

2

4

8

10

Об'єм (у Kб)

36

80

666

170 732

4 570 000


З таблиці видно, що об'єм похідної росте експоненціально з ростом порядку похідної.

Основні (найважче обчислювальні) фрагменти в результатах диференціювання виразу (1) будуть повторюватися.


Таблиця 4

Кількість фрагментів у результатах диференціювання

Порядок похідної

Фрагмент

1

2

4

8

10

cos(x)

1

3

25

6531

45 347

sin(x)

1

2

19

5242

11 082

1

2

14

3238

20 574


Для оцінки ефективності описаної оптимізації позначимо через T час обчислень без оптимізації та через Toп - час з оптимізацією. Тоді


;


,

де m - число різних фрагментів об'єкта,

ti - час обчислень і-го фрагмента,

ni - число повторень цього фрагмента.

У такий спосіб оцінка ефективності описаної оптимізації


.


Для 10-ої похідної (1) при ефективність оптимізації швидко зростає з точністю обчислень. Фактично на результат експерименту дуже впливають особливості реалізації.

Таблиця 5

Ефективність оптимізації

Розрядність

25

50

100

1000

h

5

11

23

2900


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

В цьому розділі описані особливості функціонування системи, яка реалізує мову А-2000. Описані основні процедури, що забезпечують виконання програми і засоби проблемної