автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Алгоритмы и устройства "фибоначчиевой" арифметики целых чисел большого диапазона

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

1 І ГГЦ 'ЛГіГі

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

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

Спеціальність 05. 13. 05 - елементи та пристрої обчислювальної техніки та

систем керування

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

Вінниця -1999

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

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

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

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

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

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

доктор технічних наук, професор Тарасенко Володимир Петрович Національний технічний університет України «Київський політехнічі інститут»

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

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

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

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

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

Захист відбудеться «ЗО» 0$ 1999 р. о і2 годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому державному технічно університеті за адресою: 286021, м. Вінниця, Хмельницьке шосе, 95, ГУК.

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

Автореферат розісланий « О (і 1999 р.

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

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

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

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

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

При чисельному розв'язанні математичних задач на ЕОМ виникає проблема, ов'язана з наявністю великих класів погано обумовлених задач, для яких точне о’.в'язання гранично чутливо до „малих” збурень даних. Ефект похибок кругленпя для таких задач може бути катастрофічним. Тому важливо осліджуватп скінченні системи машинних чисел, що дозволяють проводити Г>‘іи;лення без похибок 0КруГЛЄННЯ.

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

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

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

• ■ ■ ґ' і ■ "іІ28 ■ •.гиіч, проміжних і вихідних даних часто буває великим (від 2 до І і

льпГ), го виникає необхідність у великій кількості розрядів машинного

бражспня цілих чисел. Як скінченні системи машинних чисел досліджені

іелові системи лишків за одним і за багатьма модулями, а також

пнченнорозрядна система р-адичних чисел. Розроблено і досліджені відповідні

іифметики в цих системах для цілих і раціональних чисел. Однак кожній з цих

іслових систем притаманні свої недоліки, що обмежують області їх

застосування. .. . .

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

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

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

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

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

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

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

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

-розробити принципи побудови пристроїв „фібоначчієвоГ’ цілочисельні

арифметики.

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

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

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

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

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

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

з

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

Практичне значення одержаних результатів. Практична цінність роботи

!ЛЯ! ,ЧГ І! ТОМУ, ЩО'

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

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

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

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

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

- Міжнародній науково-технічній конференції, «Приборостроение -97» ядіНица-Симеиз, 1997)

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

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

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

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

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

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

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

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

При розв'язанні задач, для яких даними є не раціональні числа, а поліном більш ефективна скінченнорозрядна /7-адична арифметика. Вона еквіваленті одномодульній арифметиці лишків, коли модуль є цілим числом виду т рг, де

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

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

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

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

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

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

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

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

Раціональні числа ^, шо належать до скінченної підмаожини Рц множини

відображаю і ься у множину Пт = {0,1,2,...,то-1} цілих чисел, де т - просте, вкопуються арифметичні операції в цілочисельній системі (її™а потім лочисельні результати відображаються у відповідні раціональні числа.

Підмножина ¥ц, що задається таким чином:

є <2: (а,Ь)=1,0 5 \с\ <, И, 0 < \Ь\ <; N }, (1)

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

іінопідію до умови ІИ1 + 1 < т.

Цілі числа а і />, що вводяться з клавіатури, зображаються у Фібоначчі-счікоаому коді кір^ш, а вся обробка даних виконується над/7-кодами Фібоначчі ,, гому розробляються алгоритми перетворення коду * в код кр

коду £4,_10 цілого числа 2 відповідає зображення вигляду:

л =]£§*• 10і Ь* +(5'10,к +{з-1(У)^ +(2-Ку)(/і +1(У%], (2)

І=0

де '/;і -{(), і}- цифри розрядів коду.

Цей вираз можна трактувати як зображення цілого числа Z у системі счіснші ї вагами розрядів

... 800 500 300 200 100 80 50 ЗО 20 10 8 5 3 2 1 лфавітом {0; І}.

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

розрядів •

{и’у,Ц8-10'';5-10';3-10';2-10';10' }, і = 0,-1

і Іри виведенні інформації розв’язується обернена задача, що полягає в ретворенні коду кр в код к^10. Запропоновано алгоритм перетворення

V»), який зводиться до визначення коефіцієнтів у розкладанні (2).

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

і ,| > її, ккгцо /)_і+го>6;

П=]П-1+П)\.: сі=сі-і+с0+ у: У =1 , / = 1.2,-,

° [0, якщо г/_і+го<^.

де со - частка від ділення т на 6;

П) - додатна остача від ділення т на Ь\ с0- частка від ділення а на 6;

/•о - додатна остача від ділення а на Ь.

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

Для оберненого відображення Пт яке полягає в тому, що ціло:

числу з Пт ставиться у відповідність дріб Фарея порядку Лґ, розроблен алгоритм, що реалізує такі обчислення:

-якщо а$ +с~г$ <с, то Ь* =ЬД1+і>о + 1 і а* = а*_і+с-го;

-ЯКЩО ад +с-/}) >с, то Ь* =йДі +*о ’ ^ =а^-1~г0!

-ЯКЩО І а^і-го І <с, то = Ь^\ +Ь$ і щ -а/1] -гц;

-якщо |а,Пі-/$ |>с,то і,- =£>/1|+іо~1 ' в/~ ~аТ-і+с_/0>

де г0 - остача від ділення /я на с; бо - частка від ділення т на с;

а0 = *0 = а0 = *0 = 0 •

На кожному кроці алгоритму додатний а//Ь* та від’ємний а~ /6' дрої перевіряються на належність до множини Рдг згідно з (І). Якщо ні один із дро£ не є дробом Фарея порядку Ы, то збільшується і.

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

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

Ціле число 2 є у'-м елементом послідовності цілих чисел {V.'р і}, и породжується рекурентним співвідношенням

*’р,і=н’р,і-і+'і’р,і-р-і’ 0і/>0

при певних значеннях початкових елементів ч/р0,ч>р1,...,уур р, і обчислюється : формулою:

р+і

'=1 ... - -де е^,(&) - Аг-е /7-число Фібоначчі

Гам-.м чином, задача зображення цілого числа 7 полягає у визначенні

а.ючисельних значень початкових елементів послідовності {'♦' /} і номера

шеменга, то дорівнює 7.

! кібір називається ^-зображенням числа 7.

(/-зображення цілого числа, що має властивість {тіпі<у, |; / = 1, 2, • • •, р +1}

і,; пк'.аггьея мінімальним зображенням (М- зображенням).

Для спільного зображення в ЦОМ р+1 кодів </; і коду / використовуються форма з коловим покажчиком плаваючих меж між » частинами ІаЛСільшс число, що можна зобразити, використавши цю форму, дорівнює:

^шах = <Рр {<РР [(Р + *Х« -!) + т ]}.

де п - розрядність коду Ц) \ т - розрядність коду у.

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

У третьому розділі розглядаються питання виконання операцій ілочисе.іьної арифметики (/-зображень. При цьому використовується таке ряліувиїшя (/-зображення. Ціле число г розкладається за базисом срр, елементами кого г /з-числа Фібоначчі <рг(1), і мас координата (/,. Оскільки існує множина ц-оеражеш. числа то с і множина базисів срГ. Як характеристика базису фр і<м>ри<:говупгься число}, що називається індексом.

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

/?1-1 /> + !

"і = 2 <7/ {:іУррІ)і+і-р\ :г = Т.Яі {-г}РрЬг+‘-р)-І=І І = 1

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

Яр+1 = 4Р+і +ЧР',Я Г =ЧР+ьЧі=ЯиЧг =4г,—',й'р-яр-і, (3)

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

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

ЧР ~:ІР¥і ~ЧьЯР+і = <?і;<Уі =</2'1І2 /і-і = Яр (‘0

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

На першому етапі визначається різниця А/ = /, - /2 ■ Якщо А/ = 0, те

здійснюється перехід до другого етапу. Якщо Д/ > 0, то виконуєтьс перетворення (3) Д/ разів для координат числа г,, а якщо А/ < 0, то )А/'| разів дл координат числа г2.

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

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

На четвертому етапі збільшується індекс суми у2 ПРИ АІ > 0, і /\ прі Д/ < 0 на кількість виконаних перетворень (4).

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

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

На першому кроці визначається різниця Д/ = у, —у2 - Якщо Д/ > 0, то ні другому кроці для кожного фіксованого значення Л визначаються частков добутки = д,(г,)ди(г2), а у випадку А/<0- часткові добутки = ц,(г2)(/,,(г,)

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

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

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

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

На першому кроці виконується множення ^-зображення числа г2 на число (рр У і + і — р) шляхом додавання ^-зображень - 2р -1 разів за формулою:

<рРШ^)=<рР(і - -р-Шъ). (5)

починаючи з <рр{р + .

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

й* =9/Оі)й = 'Еаі?р{ФІ-

к=1

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

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

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

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

'з = —= 2>Р(*Д

~2 і _______________________ - - -

>жнз записати

/і+і />-*• і

2>, (~і Урр Ь\ + >-р)=)£</Дг2 Уррі/2+і-р\

/=І І і=\

Чгідси випливає, що набір <рр(к/) може бути отриманий шляхом слідовного розкладання ^-зображень числа 2\ і залишків /7:

~ 1 = <Рр (к1 )-2 + 'і ’ 'і = <Рр (к2 )=1 + гг і Г2 = <Рр (*3 )-2 + 'V. - ■,

0 < п <(рр{к,-р):2.

Для визначення числа (Л„ (^'і) виконується порішшшя <2(г,) з РріїУЖ-і)* і формупься за формулою (5). Решта чисел <рр(к[) визначається шляхом рівняння «-/-зображень залишків г/ з )> Щ° обчислються за формулою:

^ (/ХХ-2 )=-?;,(./+/? + і)СХ-2 ) ■- <Рр 0 + />)б("2 ). (6)

де ./ = *, -р-ї, к, -р-2,---

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

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

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

__ • * * *

При введенні дійсного числа виду хпхп_1...х] ,х1л,2...^. воно перетворюється

'С X X X X X о

національне число :к~=— кожна десяткова цифра якого

10і Ь *

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

'ібоначчі-десятковим кодом кгр_,0. Число 6 = 10* зображається неявно у виді

1>К‘'СТ1 к цифр після коми.

І!;>.чодячи з цього, формування чисельника а зводиться до перетворення

іоггачпі-дссяткового коду вр-код Фібоначчі крі а формування 6 полягає

..'ре;в(>ренні коду числа к у/ькод Фібоначчі числа 10*.

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

Рис. 1. Схема пристрою для перетворення дійсного числа в раціональне.

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

о-їкр, перетворювач кодів

10* -» кр і блок керування.

Перетворювач 10а є

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

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

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

... Ъ00Ь 200* 100Ь 80Ь 50Ь З0Ь 2ОЬ 106 8Ь 5Ь ЗЬ 2Ь Ь і алфавітом {0; 1}.

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

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

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

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

іапіональпі. Для здійснення оберненого відображення П„, -> І*д; також розроблені два варіанти перетворювачів, що відрізняються складністю і

ішидкодією. - ...... — -------- ------

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

і Іеред початком роботи іристрою в регістри Ргі н- Рг</Н !) іііцисуюіься коди чисел

и 1 ' - Чі:» “з ^Ч2’—,»Р+1=Ч'Р,

цо отримуються шляхом зсуву коду аа відповідну кількість розрядів

іраворуч. Максимальний час іеретворення дорівнює:

Т.

пер

:(©Дт + і) +

пі он

+ 1,

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

■ час запису в регістр.

Час перетворення можна

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

■Пя

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

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

Рис.3. Схема перетворювача Рл-(варіант 2).

■ ІЬ

Рис 4 Схема пристрою для перетворення />- колу Фібоначчі в М-зображення

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

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

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

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

Рис. 5. Схема перетворювача координат ПК' Рис.6. Схема перетворювача координат ГОТ

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

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

Чр+1 ~~Чі ~~Чі * ’ “■ Чр-1 > Чр

Добуток крфрії) обчислюється шляхом виконання і разів перетворення

(3). При цьому результат множення формується на виході <у*+1.

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

Оскільки вирівнювання індексів і мінімізація (/-зображення потребують ігиб.г.і іно однакового часу, то даний пристрій організований у виді дворівневого сонвеєра. До першого рівня конвеєра належать регістри Рг І Рг 3, Рг 1. і : Рг І.

і3; 2 І ~ Рг 2. /7+1, віднімач ВДН, усі комутатори і ПК', а до другого рівня -ї.М.'М-ИДН.ІІК'іЛіч.

Рис 7 Схема пристрою для додавання-віднімання.

/Ь;; значного скорочення апаратурних витрат запропоновано нлтриеі’овувагії шинну організацію пристрою з одним суматором-віднімачем.

таргану пристрою, у порівнянні з першим варіантом, містить також удвічі :іі!'/є реисірів. Час додавання (віднімання) у цьому пристрої більш ніж у два ви перевищує час додавання (віднімання) у першому варіанті пристрою.

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

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

імпульсів у р-коді Фібоначчі.

Рис.8. Схема пристрою для множення

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

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

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

Рис.9. Схема пристрою для ділення

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

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

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

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

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

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

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

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

іані її збільшенням і зменшенням індексу у. Ці перетворення, а так само всі шн дії, що здійснюються при виконанні арифметичних операцій, зводяться до галізації додавання і віднімання /і-коді в Фібоначчі. Показано, що при виконанні пераціГі додавання, віднімання і множення за модулем простою числа доцільно іонрзп! це число з послідовності /7-ЧИСЄЛ Фібоначчі. Крім того, при множенні ■ін'іьііо кожний проміжний результат обчислювати за модулем. Такий підхід ■пяоттггг спростити обчислення.

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

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

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

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

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

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

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

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

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

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

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

АНОТАЦІЇ

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

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

Дисертація присвячена розробці спеціалізованих арифметичних пристроїв,

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

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

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

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

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

Tlie dissertation is devoted to development of the specialized arithmetic devices ividing for the solution of poorly grounded problems. Forms of data representation, ;ed on Fibonacci /^-numbers are used in the given work. In order to obtain these ms real numbers are represented by integer numbers of one-modular representation ng simple Fibonacci /7-numbers. In its turn, the integers are represented in index form representation), which does not have analogues among the known forms of numbers icsentation in digital computer. It is shown that the suggested form provides the resentation of greater range of numbers. Algorithms and devices for numbers and les transformation at data input and output have been designed.

Algorithms and devices to carry out arithmetic operations over (/-representations of ., gers of greater range have been designed. It has been shown that the arithmetics of

(/-representations provides far less complexity of calculations than the arithmetics < repeated accuracy.

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

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

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

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

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

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

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

отображаются во множество целых чисел Пт={0,1,2,...,/и-1}, где т — простс число, выбираемое из последовательности p-чисел Фибоначчи. Выполняютс

отображаются целочисленные результаты в соответствующие рациональны

числа. Для прямого Рд, —>11^ и обратного Пт -> Рл, отображений разработан

алгоритмы, которые при определенных условиях реализуются быстрее, че

известные обобщенные алгоритмы Евклида.

Разработан алгоритм представления целых чисел большого диапазона,

. Р+1 , основе которого лежит изображение целого числа в виде: Х/ЛР/Д/ +' " I

у-1

где д,- целые числа; у = 0, 1, 2, ... Набор д, называется ^-представлением числа :

арифметические операции в целочисленной системе

а зате

Существует множество (/-представлений, но в качестве исходного при обработке ^пользуется М-представление, которому соответствует максимальное значение [ндекса /. Для совместного представления в ЦВМ р+1 кодов коэффициентов </, и ода числа / используются структуры машинных форм с фиксированными и лакающими границами, которым нет аналогов среди известных форм редстаплсния чисел в ЦВМ. Показано, что данные формы обеспечивают начителъно больший диапазон представления целых чисел по сравнению с звгетными формами.

Разработаны алгоритмы сложения, умножения и деления (/-представлений V*,1ы\ чисел большого диапазона. В основе этих операций лежат преобразования оординат (/,, связанные с увеличением и с уменьшением индекса / Эти |)с«>брачования, а также все другие действия, осуществляемые при выполнении рифмстичсских операций, сводятся к реализации только операций сложения и ычитания /7-кодов Фибоначчи. Характерным для всех алгоритмов является аличие процедуры минимизации ^-представления результата выполнения эифметической операции. Однако исходные операнды могут иметь не только

1-представление, но и произвольное (/-представление. Поэтому при выполнении оследовательности операций можно исключить минимизацию промежуточных гзультатов и реализовать ее только один раз для окончательного результата. Это ззг.ол.тст в два и более раз уменьшить количество вычислений. Получены }авиигелы1ме оценки сложности предложенных алгоритмов и алгоритмов жфметики многократной точности (АМТ). Эти оценки показывают, что п-орт м сложения (/-представлений сложнее алгоритма сложения АМТ, а

■ три гмы умножения и деления (/-представлений на несколько порядков ( в и’йсимоети ог значения р и разрядности операндов) проще. Поскольку лчожение также часто выполняется при решении многих задач, то арифметика представлений обеспечивает значительно меньшую сложность вычислений,

АМТ.

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

> п большими аппаратурными за фатами по сравнению с преобразователями,

■ шрые имеют структуру с общей шиной.

Разработаны арифметические устройства для сложения, вычитания,

I но-,кения и деления (/-представлений. Базовыми блоками этих устройств Л5ПОТСЯ преобразователи координат </, с увеличением и с уменьшением индекса Приводится раздельная и совмещенная реализация этих блоков. При зработке устройств использованы два принципа организации структуры:

конвейерный и с общей шиной. Такое построение арифметических устройс предоставляет возможность выбора устройства с технически» характеристиками, удовлетворяющими конкретное применение.

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

Підписано до друку 18.08.1999 р. Формат 29,7x42 1/4 Тир. 100 прим. Друк КІВЦ ВДТУ Зам. № 99-063 м. Вінниця, вул. Хмельницьке шосе, 95. Тел. 44-01-59