Алгоритми та пристрої "фібоначчієвої" арифметики цілих чисел великого діапазону

Размещено на http://www.allbest.ru/

Вінницький державний технічний університет

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

АЛГОРИТМИ ТА ПРИСТРОЇ ,,ФІБОНАЧЧІЄВОЇ'' АРИФМЕТИКИ ЦІЛИХ ЧИСЕЛ ВЕЛИКОГО ДІАПАЗОНУ

АЛЬ-МАЙТА МОХАММАД АБДЕЛЬКАРІМ

УДК 681.325.5

Спеціальність 05. 13. 05

елементи та пристрої обчислювальної техніки та систем керування

Вінниця - 1999

Дисертацією є рукопис

Робота виконана у Вінницькому державному технічному університеті Міністерства освіти України

Науковий керівник: кандидат технічних наук, доцент

Лужецький Володимир Андрійович

Вінницький державний технічний університет,

доцент кафедри обчислювальної техніки

Офіційні опоненти:

доктор технічних наук, професор Тарасенко Володимир Петрович

Національний технічний університет України “Київський політехнічний інститут”

завідувач кафедри спеціалізованих комп'ютерних систем

кандидат технічних наук, доцент Корченко Олександр Григорович

Київський міжнародний університет цивільної авіації,

доцент кафедри основ обчислювальної техніки та бортових обчислювальних пристроїв

Провідна установа:

Інститут кібернетики імені В.М. Глушкова НАН України, відділ мікропроцесорної техніки, м. Київ

Захист відбудеться “ 30 ” 09 1999 р. о 12-00 годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому державному технічному університеті за адресою: 286021, м. Вінниця, Хмельницьке шосе, 95, ГУК.

З дисертацією можна ознайомитись у бібліотеці Вінницького державного технічного університету.

Автореферат розісланий “ 27 ” 08 1999 р.

Вчений секретар спеціалізованої вченої ради Лисогор В.М.

фібоначчі алгоритм арифметичний

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Чисельні алгоритми мають дві характеристики, по котрим часто судять про їхню якість. Перша - складність (час, що витрачається на обчислення), друга - чисельна стійкість (мала чутливість до похибок округлення).

Існують три основні причини виникнення похибки при чисельному розв'язанні вихідної математичної задачі. Насамперед, вхідні дані завжди задаються з деякою похибкою. Далі, при заміні вихідної задачі дискретною задачею виникає похибка методу. Нарешті, скінченна розрядність чисел, що зображаються в ЕОМ, призводить до похибок округлення, які можуть накопичуватися в процесі обчислень.

При чисельному розв'язанні математичних задач на ЕОМ виникає проблема, пов'язана з наявністю великих класів погано обумовлених задач, для яких точне розв'язання гранично чутливо до ,,малих” збурень даних. Ефект похибок округлення для таких задач може бути катастрофічним. Тому важливо досліджувати скінченні системи машинних чисел, що дозволяють проводити обчислення без похибок округлення.

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

Вже більш трьох десятиліть в обчислювальній математиці існує розділ, названий "безпохибковими обчисленнями". Теорія безпохибкових обчислень має справу з задачами, для яких вхідна інформація є набором цілих чисел, а розв'язання є раціональною функцією від цих чисел. При дискретизації вихідної задачі, вхідні дані, що є дійсними числами, апроксимуються раціональними числами, які, у свою чергу, відображаються в цілі числа. Оскільки діапазон вхідних, проміжних і вихідних даних часто буває великим (від 2-128 до 2128 і більш), то виникає необхідність у великій кількості розрядів машинного зображення цілих чисел. Як скінченні системи машинних чисел досліджені числові системи лишків за одним і за багатьма модулями, а також скінченнорозрядна система p-адичних чисел. Розроблено і досліджені відповідні арифметики в цих системах для цілих і раціональних чисел. Однак кожній з цих числових систем притаманні свої недоліки, що обмежують області їх застосування.

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалось згідно з планом наукових досліджень Вінницького державного технічного університету, за держбюджетною темою: 52-Г-158, “Розробка нових інформаційних і алгоритмічних основ перспективних ЕОМ, орієнтованих на розв'язання задач обчислювальної математики”, номер держ. реєстр. № 0196U007366; та темою “Створення нових інформаційних, алгоритмічних та схемотехнічних основ спеціалізованих високонадійних обчислювальних пристроїв”.

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

Основні задачі, що визначаються поставленою метою:

- розробити і проаналізувати алгоритми відображення раціональних чисел у цілі й обернено;

- розробити алгоритми зображення цілих чисел великого діапазону;

- розробити і проаналізувати алгоритми виконання арифметичних операцій над цілими числами великого діапазону;

- розробити принципи побудови перетворювачів кодів і чисел;

- розробити принципи побудови пристроїв ,,фібоначчієвої” цілочисельної арифметики.

Наукова новизна одержаних результатів. У дисертації вперше розроблено ефективні алгоритми та пристрої арифметики цілих чисел великого діапазону, заснованої на р-числах Фібоначчі, що забезпечують точні обчислення при розв'язанні погано обумовлених задач і підвищують продуктивність спеціалізованих процесорів, призначених для реалізації таких задач.

До основних нових наукових результатів, що складають наукову новизну, відносяться:

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

- алгоритми відображення раціональних чисел у цілі й обернено, що за певних умов простіше, ніж узагальнені алгоритми Евкліда;

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

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

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

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

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

Результати дисертаційної роботи впроваджено на ВАТ “Науково-дослідний інститут відеотермінальної техніки” та використовуються в навчальному процесі на кафедрі обчислювальної техніки Вінницького державного технічного університету

Особистий внесок здобувача. У роботах, що написані в співавторстві, автору належать: [1] - ідея способу кодування символьної інформації; [2] - алгоритми відображення раціональних чисел у цілі і навпаки; [3] - алгоритми зображення цілих чисел великого діапазону й оцінки діапазону для різних форм зображення цілих чисел у ЦОМ; [4,6] - алгоритми виконання арифметичних операцій і оцінки складності алгоритмів; [5] - структури арифметичних пристроїв для обробки цілих чисел великого діпазону; [7] - структури перетворювачів кодів.

Апробація результатів дисертації. Основні положення дисертації і результати досліджень доповідалися і обговорювалися на:

Міжнародній науково-технічній конференції, “Приборостроение -97” (Винница-Симеиз, 1997)

- VI-науково-технічній конференції “Вимірювальна та обчислювальна техніка в технологічних процесах” (Хмельницький 1999);

- Щорічних науково-технічних конференціях професорсько-викладацького складу Вінницького державного технічного університету. (Вінниця, 1996-98).

Публікації. Результати дисертації опубліковані в 5 статтях у наукових журналах, 2 збірниках наукових праць.

Структура та обсяг дисертації. Робота складається зі вступу, п'яти розділів, п'яти додатків, загальний обсяг дисертації 215 сторінок з яких основний зміст викладений на 142 сторінках друкованого тексту, 53 рисунків, 11 таблиць. Список використаних джерел складається з 70 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

При розв'язанні задач, для яких даними є не раціональні числа, а поліноми, більш ефективна скінченнорозрядна р-адична арифметика. Вона еквівалентна одномодульній арифметиці лишків, коли модуль є цілим числом виду m=pr, де p - просте, а r - ціле додатне. У силу цього, при розв'язанні інших класів задач p-адична арифметика має ті ж недоліки, що й одномодульна арифметика.

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

Відомі "фібоначчієві" системи числення мають ті ж недоліки, що одномодульна система. Проте властивості р-чисел Фібоначчі дозволяють створювати інші способи зображення цілих чисел.

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

В другому розділі розглядаються питання зображення даних на різних рівнях: на рівні символів, що вводяться за допомогою клавіатури, на рівні чисел, що вводяться у ЦОМ і виводяться із неї, на рівні машинних форм зображення чисел і на рівні машинних кодів. Кожному з цих рівнів відповідає своя форма зображення і свої коди. Тому виникає необхідність перетворення одних форм зображення в інші. Виходячи з цього, розробляються і досліджуються алгоритми прямих і обернених перетворень.

Запропоновано спосіб кодування алфавітно-цифрової і символьної інформації на основі М-форми 12-ти розрядного 1-коду Фібоначчі, що названа "дюжиною". Збільшення кількості можливих кодів символів із 256 (для байта) до 377 (для дюжини) дозволяє ввести додатково до відомих символів символи грецького алфавіту і деякі математичні символи. Крім того, забезпечується контроль формування, зберігання і передавання кодів символів. Для дюжини коефіцієнт знаходження помилок дорівнює 0,908, тоді як для байта з контролем на парність він є 0,5.

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

В роботі розглядається такий підхід до зображення множини раціональних чисел Q у ЦОМ.

Раціональні числа , що належать до скінченної підмножини FN множини Q відображаються у множину ={0,1,2,…,m-1} цілих чисел, де m - просте. Виконуються арифметичні операції в цілочисельній системі , а потім цілочисельні результати відображаються у відповідні раціональні числа.

Якщо ці ваги розрядів, зобразити в р-коді Фібоначчі і додати ті з них, при котрих qji=1, то одержимо р-код Фібоначчі числа Z. Тобто процедура перетворення в полягає в накопиченні визначених кодових еквівалентів ваг розрядів

При виведенні інформації розв'язується обернена задача, що полягає в перетворенні коду в код . Запропоновано алгоритм перетворення , який зводиться до визначення коефіцієнтів qji у розкладанні (2).

Для прямого відображення запропонований алгоритм, що реалізує такі обчислення:

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

Для оберненого відображення , яке полягає в тому, що цілому числу з ставиться у відповідність дріб Фарея порядку N, розроблений алгоритм, що реалізує такі обчислення:

На кожному кроці алгоритму додатний /та від'ємний /дроби перевіряються на належність до множини згідно з (1). Якщо ні один із дробів не є дробом Фарея порядку N, то збільшується і.

Результати моделювання запропонованих алгоритмів прямого й оберненого перетворень і відомих узагальнених алгоритмів Евкліда показали таке. Для розрядності операндів n=16 запропонований алгоритм потребує меншої кількості операцій у порівнянні з узагальненим алгоритмом Евкліда у випадку дробів Фарея порядку N<200, а для розрядності n=32 - у випадку N<500. Для обернених перетворень теж спостерігається при n=16, N<300 і при n=32, N<700.

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

Ціле число Z є j-м елементом послідовності цілих чисел {}, що породжується рекурентним співвідношенням при певних значеннях початкових елементів ,,...,, і обчислюється за формулою:

де p(k) - k-е p-число Фібоначчі.

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

Набір називається q-зображенням числа Z.

Для спільного зображення в ЦОМ p+1 кодів q1 і коду j використовується машинна форма з кодовим покажчиком плаваючих меж між її частинами. Найбільше число, що можна зобразити, використавши цю форму, дорівнює:

,

де n - розрядність коду q1;

m - розрядність коду j.

Якщо використовується звичайна форма зображення цілих чисел, то при однаковій розрядності найбільше число буде

У третьому розділі розглядаються питання виконання операцій цілочисельної арифметики q-зображень. При цьому використовується таке трактування q-зображення. Ціле число z розкладається за базисом p, елементами якого є p-числа Фібоначчі p(l), і має координати qi. Оскільки існує множина q-зображень числа z, то є і множина базисів p. Як характеристика базису p використовується число j, що називається індексом.

При розробці алгоритмів додавання, віднімання, множення та ділення вважається, що числа z1 і z2 зображені у вигляді:

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

(3)

де нове значення координати.

Перетворення координат, що збільшує індекс на одиницю, зводиться до виконання таких дій:

 (4)

Додавання (віднімання) q-зображень двох цілих чисел виконується в чотири етапи.

На першому етапі визначається різниця . Якщо , те здійснюється перехід до другого етапу. Якщо то виконується перетворення (3) разів для координат числа z1, а якщо то разів для координат числа z2.

На другому етапі здійснюється звичайне додавання (віднімання) кодів однойменних координат.

Оскільки початкові числа z1 і z2 мають М-зображення, то і сума повинна мати таке ж зображення. Тому на третьому етапі здійснюється мінімізація q-зображення шляхом виконання перетворення (4).

На четвертому етапі збільшується індекс суми при і при на кількість виконаних перетворень (4).

Розроблено модифікацію цього алгоритму, що забезпечує обчислення за модулем m.

Для реалізації операції множення цілих чисел z1 і z2 запропоновано два алгоритми. Перший алгоритм передбачає виконання таких дій.

На першому кроці визначається різниця . Якщо , то на другому кроці для кожного фіксованого значення h визначаються часткові добутки а у випадку - часткові добутки

На третьому кроці виконується перетворення (3) разів при і разів при над наборами часткових добутків.

На четвертому і п'ятому кроках виконуються такі ж дії, як на третьому і четвертому етапах алгоритму додавання.

Недоліком даного алгоритму множення є те, що він не завжди забезпечує одержання М-зображення добутку.

Другий алгоритм полягає у виконанні таких дій.

На першому кроці виконується множення q-зображення числа z2 на число шляхом додавання q-зображень разів за формулою:

, (5)

починаючи з .

На другому кроці обчислення здійснюються за формулою:

При цьому добуток визначається як (5).

Третій крок полягає у накопиченні q-зображень часткових добутків

Таким чином, множення q-зображень зводиться тільки до додавань q-зобра-жень. Якщо додавання q-зображень виконується за модулем , то даний алгоритм описує множення q-зображень за модулем .

Зобразивши результат ділення z1 на z2 у вигляді

Звідси випливає, що набір може бути отриманий шляхом послідовного розкладання q-зображень числа z1 і залишків rl:

...,

Для визначення числа виконується порівняння з , що формується за формулою (5). Решта чисел визначається шляхом порівняння q-зображень залишків rl з , що обчислються за формулою:

(6)

При визначенні чергового числа його q-зображення підсумовується з q-зображенням суми раніше визначених чисел.

Отримані порівняльні оцінки складності запропонованих алгоритмів і відомих алгоритмів арифметики багатократної точності (АБТ). Ці оцінки показують, що алгоритм додавання q-зображень складніше за алгоритм додавання АБТ, а алгоритми множення і ділення q-зображень значно простіше. Так при р=1, n=16 і m=8 алгоритм додавання q-зображень складніше в 53 рази, а алгоритми множення і ділення q-зображень простіше більш ніж у 105 і 104 разів.

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

При введенні дійсного числа виду воно перетворюється в раціональне число , кожна десяткова цифра якого зображається 5-ти розрядним 1-кодом Фібоначчі, а вся сукупність цифр (число а) - Фібоначчі-десятковим кодом . Число зображається неявно у виді кількості k цифр після коми.

Виходячи з цього, формування чисельника а зводиться до перетворення Фібоначчі-десяткового коду в р-код Фібоначчі , а формування b полягає в перетворенні коду числа k у р-код Фібоначчі числа .

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

Пристрій містить такі функціональні блоки: пам'ять Пм, лічильник Сч, перетворювач кодів , перетворювач кодів і блок керування.

Перетворювач є логічною схемою, що реалізує таблицю відповідності двійкового коду числа k р-коду Фібоначчі числа .

Перетворення Фібоначчі-десяткового коду k-10 в р-код Фібоначчі здійснюється відповідно до формули (2) і полягає в накопиченні визначених кодових еквівалентів ( р-кодів Фібоначчі чисел послідовності {810i; 510i; 310i; 210i; 10i}, де i = 0, 1, 2, ... , n+k ). Виходячи з цього, розроблені перетворювачі, основним функціональним блоком яких є генератор кодових еквівалентів (ГКЕ). Запропоновано два варіанти реалізації цього генератора: табличний (на основі ПЗП) і обчислювальний (на основі суматора). Показано, що перетворювач, реалізований на основі ПЗП кодових еквівалентів, має в 3,5 рази менше час перетворення, ніж перетворювач на основі обчислювального ГКЕ. Проте він потребує більше апаратурних витрат.

Показано так само, що обчислювальний ГКЕ може бути використаний для перетворення раціональних чисел у дійсні. Це перетворення, що полягає в діленні a на b, зводиться до перетворення р-коду числа a у Фібоначчі-десятковий код із вагами розрядів, помноженими на b, тобто

... 300b 200b 100b 80b 50b 30b 20b 10b 8b 5b 3b 2b b

і алфавітом {0; 1}.

При введенні даних після одержання р-кодів Фібоначчі чисел a і b, що є чисельником і знаменником дробу Фарея, здійснюється перетворення цього дробу в ціле число. Для реалізації алгоритму прямого відображення розроблено два варіанти пристроїв: із жорсткими зв'язками між функціональними вузлами і з загальною шиною. Схема перетворювача з жорсткими зв'язками наведена на рис.2

До його складу входять два блоки для ділення р-кодів Фібоначчі БДКФ1 і БДКФ2, суматор-віднімач СМ-ВДН, сумматор СМ, регістри Рг1 Рг5 і блок керування.

Схема перетворювача з загальною шиною приведена на рис.3. Наявність загальної шини дозволяє використовувати тільки один суматор-віднімач для реалізації всіх обчислень. Проте це призводить до збільшення часу перетворення.

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

Після відображення раціонального числа в ціле, здійснюється перетворення р-коду Фібоначчі цілого числа z у набір р-кодів Фібоначчі М-зображення. Це перетворення реалізує пристрий, схема якого наведена на рис.4.

Перед початком роботи пристрою в регістри Рг1 Рг(р+1) записуються коди чисел , що отримуються шляхом зсуву коду на відповідну кількість розрядів праворуч. Максимальний час перетворення дорівнює:

,

- час віднімання;

- час запису в регістр. Рис.2. Схема перетворювача (варіант 1).

Час перетворення можна зменшити, якщо врахувати таке. Виходячи з р+1 початкових елементів послідовності можна формувати не один наступний елемент, а р елементів одночасно.

Для реалізації такого перетворення запропоновано пристрій, що у порівнянні з першим варіантом, має в р разів менше час перетворення, але це досягнуто за рахунок введення додатково р-1 віднімачів.

Розроблено три варіанти перетворювачів М-зображення цілих чисел у р-код Фібоначчі, що відрізняються апаратурними витратами і швидкодією.

У п'ятому розділі розглядаються питання побудови пристроїв цілочисельної арифметики q-зображень. В основі цієї арифметики лежать операції перетворення координат qi із зменшенням і збільшенням індексу j і множення на послідовність р-чисел Фібоначчі. Блоки, що реалізують ці перетворення, є базовими і входять до складу арифметичних пристроїв.

Зменшення індексу j на одиницю відбувається при перетворенні координат відповідно до (3). Для реалізації даного перетворення потрібно р+1 регістрів і суматор. Схема такого перетворювача координат приведена на рис.5.

Перетворення координат, що збільшує індекс j на одиницю, зводиться до виконання дій відповідно до (4) і реалізується перетворювачем, що містить р+1 регістрів і віднімач (див. рис.6).

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

Множення р-коду Фібоначчі на послідовність р-чисел Фібоначчі реалізує перетворювач координат ПК

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

У розділі. 3 показано, що додавання (віднімання) q-зображень цілих чисел z1 і z2 виконується в чотири етапи. З метою забезпечення високої швидкодії при побудові пристрою додавання-віднімання пропонується використовувати окрему апаратуру для реалізації кожного з етапів. Схема такого пристрою додавання-віднімання приведена на рис.7.

Оскільки вирівнювання індексів і мінімізація q-зображення потребують приблизно однакового часу, то даний пристрій організований у виді дворівневого конвеєра. До першого рівня конвеєра належать регістри Рг 1 Рг 3, Рг 1.1 Рг 1. р+1, Рг 2.1 Рг 2. р+1, віднімач ВДН, усі комутатори і ПК+, а до другого рівня - Бл СМ-ВДН, ПК- і Ліч.

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

Для реалізації додаткових дій, що виконуються при додаванні (відніманні) за модулем , в пристрій (рис.7) необхідно ввести додатково р+1 регістрів координат {qh} числа і змінити деякі зв'язки між блоками.

Розроблено два варіанти пристрою множення, що функціонують відповідно до алгоритму 1. Перший варіант (див. рис.8) реалізований у виді трирівневого конвеєра з різноманітною організацією рівнів, а другий - у виді структури з загальною шиною. У цих пристроях множення кодів координат реалізується будь-яким із відомих пристроїв для множення р-кодів Фібоначчі. Згортка часткових добутків реалізується перетворювачем координат ПК+, а мінімізація q-зображення - перетворювачем ПК-. Збільшення індексу добутку на одиницю на кожному кроці мінімізації здійснюється за допомогою відомих лічильників імпульсів у р-коді Фібоначчі.

Отримані оцінки часу множення й апаратурних витрат показують, що конвеєрний пристрій множення має швидкодію в 4 рази вище, ніж пристрій із загальною шиною, але містить у 5 разів більше суматорів і в 1,5 рази більше регістрів.

Розроблено структуру пристрою множення, що реалізує алгоритм 2. Якщо при побудові даного пристрою використовувати звичайні суматори q-зображень, то буде отриманий пристрій множення q-зображень, який для будь-яких співмножників забезпечує формування М-зображення добутку, що не завжди можливо в пристроях, що реалізують алгоритм 1. Застосування сумматорів q-зображень за модулем при побудові даного пристрою дозволяє здійснювати множення q-зображень за модулем.

Для реалізації алгоритму ділення q-зображень цілих чисел розроблений пристрій, схема якого приведена на рис.9. Обчислення добутків за формулами (5) і (6) здійснює сполучений перетворювач координат СПК*, а їх порівняння з і виконується за допомогою віднімача q-зображень ВДНq та блоку Бл ВЗЧ, що визначає знак різниці. Накопичення q-зображень визначених р-чисел Фібоначчі забезпечує суматор НСМ.

Даний пристрій є достатньо складним, тому запропонований інший варіант пристрою для ділення, заснований на шинній організації структури. Наприклад, при р=1 цей варіант пристрою містить у 2,7 рази менше регістрів, а суматорів - у 6 разів. Але таке значне скорочення апаратурних витрат призводить до збільшення часу ділення у р+1 разів.

У додатку наведено лістинги програм моделювання алгоритмів та документи про використання результатів роботи.

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

У роботі досліджена цілочисельна арифметична система, що утворена на р-числах Фібоначчі, і розроблені алгоритми та пристрої, які забезпечують швидкі безпохибкові (точні) обчислення при розв'язанні погано обумовлених задач. При цьому отримані такі результати.

Розроблено спосіб зображення числової і символьної інформації на основі р-чисел Фібоначчі. Показано, що 12-розрядний 1-код Фібоначчі (дюжина) забезпечує зображення тих же символів, що і байт двійкового коду, і додатково символи грецького алфавіту, а, крім того, контроль формування, передавання і зберігання символів.

2. Розроблені алгоритми й пристрої перетворень чисел і кодів, що виконуються при введенні та виведенні даних. При цьому дійсні числа відображаються в цілі числа одномодульного зображення, що використовує прості р-числа Фібоначчі. У свою чергу, цілі числа зображаються в індексній формі (q-зображення), котрій немає аналогів серед відомих форм зображення чисел у ЦОМ. Показано, що дана форма забезпечує зображення великого діапазону чисел.

3. Розроблені алгоритми виконання арифметичних операцій над q-зображеннями цілих чисел великого діапазону. Показано, що в основі операцій додавання, віднімання, множення і ділення лежать перетворення координат qi, пов'язані зі збільшенням і зменшенням індексу j. Ці перетворення, а так само всі інші дії, що здійснюються при виконанні арифметичних операцій, зводяться до реалізації додавання і віднімання р-кодів Фібоначчі. Показано, що при виконанні операцій додавання, віднімання і множення за модулем простого числа доцільно вибирати це число з послідовності р-чисел Фібоначчі. Крім того, при множенні доцільно кожний проміжний результат обчислювати за модулем. Такий підхід дозволяє спростити обчислення.

4. Отримані оцінки складності запропонованих алгоритмів. Показано, що складність алгоритму додавання-віднімання q-зображень більше, ніж складність алгоритму додавання-віднімання арифметики багатократної точності. Тоді як складність алгоритмів множення і ділення q-зображень значно (на декілька порядків у залежності від значення р і розрядності операндів) менше, ніж в арифметиці багатократної точності. Оскільки множення так само часто виконується при розв'язанні багатьох задач, як і додавання, то арифметика q-зображень забезпечує значно меншу складність обчислень, ніж арифметика багатократної точності.

5. Розроблені пристрої додавання, віднімання, множення і ділення q-зображень. Показано, що базовими блоками цих пристроїв є перетворювачі координат qi із збільшенням і зменшенням індексу j. Ці блоки можуть бути реалізовані як роздільними, так і сполученими. При побудові пристроїв використані два принципи організації структури: конвеєрний і з загальною шиною. Така побудова арифметичних пристроїв надає можливість вибору пристрою з технічними характеристиками, що задовольняють конкретне застосування.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ:

1. Мохаммад Аль-Майта, Лужецький В.А. Про один спосіб кодування алфавітно-цифрової та символьної інформації // Вісник ВПІ. - 1997. - №2. - С. 23 - 27.

2. Лужецький В.А., Мохаммад Аль-Майта. Про один спосіб зображення дійсних чисел в ЦОМ // Вісник ВПІ. - 1997. - № 4. - С. 43-47.

3. Лужецький В.А., Мохаммад Аль-Майта. Спосіб зображення цілих чисел великого діапазону // Вимірювальна та обчислювальна техніка в технологічних процесах. - 1998. - №1. - С. 156-162.

4. Лужецький В.А., Мохаммад Аль-Майта. Арифметика цілих чисел великого діапазону // Вимірювальна та обчислювальна техніка в технологічних процесах. - 1998. - №2. - С. 130-135.

5. Мохаммад Аль-Майта. Арифметические устройства для обработки целых чисел большого диапазона // Вимірювальна та обчислювальна техніка в технологічних процесах. - 1998. - №1. - С. 156-162.

В.А. Лужецький, Мохаммад Аль-Майта. Арифметика целых чисел большой розрядности // Сборник трудов международной научно-технической конференции “Приборостроение - 97” . - Винница - Симеиз. - 1997. - С. 80-83.

7. Мохаммад Аль-Майта, В.А.Лужецький. Пристрої для отримання машинної форми зображення цілих чисел великого діапазону // Збірник наукових праць Вимірювальна та обчислювальна техніка в технологічних процесах. - Хмельницький: ТУП, 1999. - С. 108 - 112.

АНОТАЦІЇ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05. - елементи та пристрої обчислювальної техніки та систем керування. - Вінницький державний технічний університет, Вінниця, 1999.

Дисертація присвячена розробці спеціалізованих арифметичних пристроїв, що забезпечують безпохибкові (точні) обчислення при розв'язанні погано обумовлених задач. В роботі використовуються форми зображення даних, що базуються на р-числах Фібоначчі. Для отримання цих форм дійсні числа відображаються у цілі числа одномодульного зображення, яке використовує прості р-числа Фібоначчі. У свою чергу, цілі числа зображаються в індексній формі (q-зображення), яка не має аналогів серед відомих форм зображення цілих чисел у ЦОМ. Показано, що дана форма забезпечує зображення великого діапазону чисел. Розроблені алгоритми та пристрої перетворення чисел і кодів при введенні та виведенні даних.

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

Ключові слова: форма зображення чисел, р-числа Фібоначчі, р-коди Фібоначчі, алгоритми цілочисельної арифметики, арифметичні пристрої.

Al-Maita Mohammad Abdelkarim. Algorithms and devices of "Fibonacci" arithmetics of integers of great range. - Manuscript.

The dissertation for the degree of Candidate of Science (Engineering) in speciality 05. 13. 05. - Elements and devices of computing engineering and control systems. - Vinnitsa state technical university, Vinnitsa, 1999.

The dissertation is devoted to development of the specialized arithmetic devices providing for the solution of poorly grounded problems. Forms of data representation, based on Fibonacci p-numbers are used in the given work. In order to obtain these forms real numbers are represented by integer numbers of one-modular representation using simple Fibonacci p-numbers. In its turn, the integers are represented in index form (q-representation), which does not have analogues among the known forms of numbers representation in digital computer. It is shown that the suggested form provides the representation of greater range of numbers. Algorithms and devices for numbers and codes transformation at data input and output have been designed.

Algorithms and devices to carry out arithmetic operations over q-representations of integers of greater range have been designed. It has been shown that the arithmetics of q-representations provides far less complexity of calculations than the arithmetics of repeated accuracy.

Key words: the form of numbers representation, p-number Fibonacci, p-codes Fibonacci, algorithms of integer arithmetics, arithmetic devices.

Аль-Майта Мохаммад Абделькарим. Алгоритмы и устройства ,,фибоначчиевой'' арифметики целых чисел большого диапазона. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05. 13. 05. - элементы и устройства вычислительной техники и систем управления. - Винницкий государственный технический университет, Винница, 1999.

Диссертация посвящена разработке специализированных арифметических устройств, обеспечивающих безошибочные (точные) вычисления при решении плохо обусловленных задач.

В работе рассматриваются вопросы представления данных на различных уровнях: на уровне символов, вводимых с помощью клавиатуры, на уровне чисел, вводимых в ЦВМ и выводимых из нее, на уровне машинных форм представления чисел и на уровне машинных кодов.

Предложен способ кодирования алфавитно-цифровой и символьной информации на основе М-формы 1-кода Фибоначчи, который позволяет увеличить количество кодируемых символов и обеспечивает контроль формирования, хранения и передачи кодов символов. При этом для кодирования символов используется 12-ти разрядный код, который назван "дюжиной".

Поскольку дискретность представления информации и конечная разрядность данных, характерные для ЦВМ, порождают конечное множество чисел, то, практически, есть возможность представлять действительные числа только в виде конечного ряда, т.е. аппроксимировать их рациональными числами. В работе рассматривается следующий подход к представлению рациональных чисел. Рациональные числа из множества дробей Фарея FN отображаются во множество целых чисел ={0,1,2,…,m-1}, где m - простое число, выбираемое из последовательности р-чисел Фибоначчи. Выполняются арифметические операции в целочисленной системе , а затем отображаются целочисленные результаты в соответствующие рациональные числа. Для прямого и обратного отображений разработаны алгоритмы, которые при определенных условиях реализуются быстрее, чем известные обобщенные алгоритмы Евклида.

Разработан алгоритм представления целых чисел большого диапазона, в основе которого лежит изображение целого числа в виде: где qi целые числа; j = 0, 1, 2, ... Набор qi называется q-представлением числа z. Существует множество q-представлений, но в качестве исходного при обработке используется M-представление, которому соответствует максимальное значение индекса j. Для совместного представления в ЦВМ p+1 кодов коэффициентов qi и кода числа j используются структуры машинных форм с фиксированными и плавающими границами, которым нет аналогов среди известных форм представления чисел в ЦВМ. Показано, что данные формы обеспечивают значительно больший диапазон представления целых чисел по сравнению с известными формами.

Разработаны алгоритмы сложения, умножения и деления q-представлений целых чисел большого диапазона. В основе этих операций лежат преобразования координат qi, связанные с увеличением и с уменьшением индекса j. Эти преобразования, а также все другие действия, осуществляемые при выполнении арифметических операций, сводятся к реализации только операций сложения и вычитания р-кодов Фибоначчи. Характерным для всех алгоритмов является наличие процедуры минимизации q-представления результата выполнения арифметической операции. Однако исходные операнды могут иметь не только М-представление, но и произвольное q-представление. Поэтому при выполнении последовательности операций можно исключить минимизацию промежуточных результатов и реализовать ее только один раз для окончательного результата. Это позволяет в два и более раз уменьшить количество вычислений. Получены сравнительные оценки сложности предложенных алгоритмов и алгоритмов арифметики многократной точности (АМТ). Эти оценки показывают, что алгоритм сложения q-представлений сложнее алгоритма сложения АМТ, а алгоритмы умножения и деления q-представлений на несколько порядков ( в зависимости от значения р и разрядности операндов) проще. Поскольку умножение также часто выполняется при решении многих задач, то арифметика q-представлений обеспечивает значительно меньшую сложность вычислений, чем АМТ.

Разработаны различные варианты преобразователей рациональных чисел в целые и обратно, р-кодов Фибоначчи целых чисел в М-представление и обратно, отличающиеся аппаратурными затратами и быстродействием. Показано, что при реализации преобразователей могут быть использованы два принципа организации структуры: с жесткими связями и с общей шиной. Преобразователи, имеющие структуры с жесткими связями обладают большим быстродействием, но и большими аппаратурными затратами по сравнению с преобразователями, которые имеют структуру с общей шиной.

Разработаны арифметические устройства для сложения, вычитания, умножения и деления q-представлений. Базовыми блоками этих устройств являются преобразователи координат qi с увеличением и с уменьшением индекса j. Приводится раздельная и совмещенная реализация этих блоков. При разработке устройств использованы два принципа организации структуры: конвейерный и с общей шиной. Такое построение арифметических устройств предоставляет возможность выбора устройства с техническими характеристиками, удовлетворяющими конкретное применение.

Ключевые слова: форма представления чисел, р-числа Фибоначчи, р-коды Фибоначчи, алгоритмы целочисленной арифметики, арифметические устройства.

Размещено на Allbest.ru

...