Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов

Представлены новый метод и алгоритмы деления модулярных чисел, основанные на процедуре использования относительных величин делимого и делителя к полному диапазону системы остаточных классов. В основе алгоритма модулярного деления используются элементарные операции регистрового сдвига и сложения, что...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
Hauptverfasser:	Червяков, Н.И., Бабенко, М.Г., Ляхов, П.А., Лавриненко И.Н.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Новые средства кибернетики, информатики, вычислительной техники и системного анализа
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/124740
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов / Н.И. Червяков, М.Г. Бабенко, П.А. Ляхов, И.Н. Лавриненко // Кибернетика и системный анализ. — 2014. — Т. 50, № 6. — С. 176-186. — Бібліогр.: 30 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-124740
record_format	dspace
spelling	irk-123456789-1247402017-10-04T03:03:08Z Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов Червяков, Н.И. Бабенко, М.Г. Ляхов, П.А. Лавриненко И.Н. Новые средства кибернетики, информатики, вычислительной техники и системного анализа Представлены новый метод и алгоритмы деления модулярных чисел, основанные на процедуре использования относительных величин делимого и делителя к полному диапазону системы остаточных классов. В основе алгоритма модулярного деления используются элементарные операции регистрового сдвига и сложения, что делает его простым и быстродействующим. В настоящее время такой алгоритм считается наиболее быстрым. Запропоновано новий метод та алгоритми ділення модулярних чисел, що базуються на процедурі використання відносних величин діленого і дільника до повного діапазону системи залишкових класів. За основу алгоритму модулярного ділення взято елементарні операції регістрового зсуву та додавання, що робить алгоритм простим і швидкодіючим. На даний час такий алгоритм вважається найшвидшим. The paper presents a new method and algorithms for division of modular numbers, which are based on the use of relative values of the dividend and the divisor to the full range of the residue number system. The algorithm of modular division uses the elementary operations of register shift and addition, which makes the algorithm very simple and the fastest to date. 2014 Article Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов / Н.И. Червяков, М.Г. Бабенко, П.А. Ляхов, И.Н. Лавриненко // Кибернетика и системный анализ. — 2014. — Т. 50, № 6. — С. 176-186. — Бібліогр.: 30 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124740 681.3 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа
spellingShingle	Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа Червяков, Н.И. Бабенко, М.Г. Ляхов, П.А. Лавриненко И.Н. Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов Кибернетика и системный анализ
description	Представлены новый метод и алгоритмы деления модулярных чисел, основанные на процедуре использования относительных величин делимого и делителя к полному диапазону системы остаточных классов. В основе алгоритма модулярного деления используются элементарные операции регистрового сдвига и сложения, что делает его простым и быстродействующим. В настоящее время такой алгоритм считается наиболее быстрым.
format	Article
author	Червяков, Н.И. Бабенко, М.Г. Ляхов, П.А. Лавриненко И.Н.
author_facet	Червяков, Н.И. Бабенко, М.Г. Ляхов, П.А. Лавриненко И.Н.
author_sort	Червяков, Н.И.
title	Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов
title_short	Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов
title_full	Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов
title_fullStr	Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов
title_full_unstemmed	Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов
title_sort	приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2014
topic_facet	Новые средства кибернетики, информатики, вычислительной техники и системного анализа
url	http://dspace.nbuv.gov.ua/handle/123456789/124740
citation_txt	Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов / Н.И. Червяков, М.Г. Бабенко, П.А. Ляхов, И.Н. Лавриненко // Кибернетика и системный анализ. — 2014. — Т. 50, № 6. — С. 176-186. — Бібліогр.: 30 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT červâkovni približennyjmetodsravneniâmodulârnyhčiseliegoprimeneniedlâdeleniâčiselvsistemeostatočnyhklassov AT babenkomg približennyjmetodsravneniâmodulârnyhčiseliegoprimeneniedlâdeleniâčiselvsistemeostatočnyhklassov AT lâhovpa približennyjmetodsravneniâmodulârnyhčiseliegoprimeneniedlâdeleniâčiselvsistemeostatočnyhklassov AT lavrinenkoin približennyjmetodsravneniâmodulârnyhčiseliegoprimeneniedlâdeleniâčiselvsistemeostatočnyhklassov
first_indexed	2025-07-09T01:57:39Z
last_indexed	2025-07-09T01:57:39Z
_version_	1837132688607150080
fulltext	ÓÄÊ 681.3 Í.È. ×ÅÐÂßÊÎÂ, Ì.Ã. ÁÀÁÅÍÊÎ, Ï.À. ËßÕÎÂ, È.Í. ËÀÂÐÈÍÅÍÊÎ ÏÐÈÁËÈÆÅÍÍÛÉ ÌÅÒÎÄ ÑÐÀÂÍÅÍÈß ÌÎÄÓËßÐÍÛÕ ×ÈÑÅË È ÅÃÎ ÏÐÈÌÅÍÅÍÈÅ ÄËß ÄÅËÅÍÈß ×ÈÑÅË Â ÑÈÑÒÅÌÅ ÎÑÒÀÒÎ×ÍÛÕ ÊËÀÑÑÎÂ1 Àííîòàöèÿ. Ïðåäñòàâëåíû íîâûé ìåòîä è àëãîðèòìû äåëåíèÿ ìîäóëÿðíûõ ÷èñåë, îñíî- âàííûå íà ïðîöåäóðå èñïîëüçîâàíèÿ îòíîñèòåëüíûõ âåëè÷èí äåëèìîãî è äåëèòåëÿ ê ïîëíîìó äèàïàçîíó ñèñòåìû îñòàòî÷íûõ êëàññîâ. Â îñíîâå àëãîðèòìà ìîäóëÿðíîãî äåëåíèÿ èñïîëüçó- þòñÿ ýëåìåíòàðíûå îïåðàöèè ðåãèñòðîâîãî ñäâèãà è ñëîæåíèÿ, ÷òî äåëàåò åãî ïðîñòûì è áûñòðîäåéñòâóþùèì. Â íàñòîÿùåå âðåìÿ òàêîé àëãîðèòì ñ÷èòàåòñÿ íàèáîëåå áûñòðûì. Êëþ÷åâûå ñëîâà: àëãîðèòì, ñèñòåìà îñòàòî÷íûõ êëàññîâ, ìîäóëÿðíàÿ àðèôìåòèêà, äåëåíèå. ÂÂÅÄÅÍÈÅ Ñèñòåìó îñòàòî÷íûõ êëàññîâ (ÑÎÊ, RNS — Residue Number System) ìíîãèå èññëåäîâàòåëè èñïîëüçóþò â êà÷åñòâå îñíîâû äëÿ âû÷èñëèòåëüíîé òåõíèêè. Â ïîñëåäíåå äåñÿòèëåòèå èíòåðåñ ê íåé ðåçêî âîçðîñ, ÷òî ïîäòâåðæäàåòñÿ áîëüøèì ÷èñëîì ïóáëèêàöèé, ïîñâÿùåííûõ ïðàêòè÷åñêîìó ïðèìåíåíèþ ÑÎÊ â öèôðîâîé îáðàáîòêå ñèãíàëîâ, ñèñòåìàõ îáðàáîòêè èçîáðàæåíèé, ïîìåõîóñ- òîé÷èâîì êîäèðîâàíèè, êðèïòîãðàôè÷åñêèõ ñèñòåìàõ, êâàíòîâûõ àâòîìàòàõ, íåéðîêîìïüþòåðàõ, ñèñòåìàõ ñ ìàññîâûì ïàðàëëåëèçìîì îïåðàöèé, îáëà÷íûõ âû÷èñëåíèÿõ è äð. [1–13]. Â ðàáîòàõ [14–16] èññëåäîâàíû ìîäåëè îòäåëüíûõ âû÷èñëèòåëüíûõ óçëîâ ñïåöèàëèçèðîâàííûõ ïðîöåññîðîâ, âêëþ÷àþùèõ òàêèå ýëåìåíòû ÑÎÊ, êàê: âõîäíûå è âûõîäíûå ïðåîáðàçîâàòåëè, ìîäóëüíûå ñóììà- òîðû, ñõåìû îïðåäåëåíèÿ çíàêà è ïåðåïîëíåíèÿ, äåëåíèÿ è ìàñøòàáèðîâàíèÿ, ðàñøèðåíèÿ áàçû ÑÎÊ, ñõåìû îêðóãëåíèÿ, ëîêàëèçàöèè è èñïðàâëåíèÿ îøè- áîê è äðóãèå, êîòîðûå ìîãóò áûòü ðåàëèçîâàíû íà êëàññè÷åñêîé, íåéðîñåòåâîé èëè êâàíòîâîé âû÷èñëèòåëüíîé áàçå. Àðèôìåòèêî-ëîãè÷åñêîå óñòðîéñòâî (ÀËÓ) â ÑÎÊ äëÿ ðåøåíèÿ çàäà÷ ñ î÷åíü áîëüøèìè ÷èñëàìè, èñïîëüçóåìûõ ïðè øèôðîâàíèè è äåøèôðîâàíèè, ïðåäñòàâëåíî â [17]. ÑÎÊ äàåò ïðåèìóùåñòâà áûñòðîãî ñëîæåíèÿ è óìíîæåíèÿ ïî ñðàâíåíèþ ñ îñòàëüíûìè ñèñòåìàìè ñ÷èñëåíèÿ, ÷òî îáóñëîâëèâàåò áîëüøîé èíòåðåñ ê ýòîé ñèñòåìå â òåõ îáëàñòÿõ, ãäå òðåáóþòñÿ áîëüøèå îáúåìû âû÷èñëåíèé. Îäíàêî íå- êîòîðûå îïåðàöèè, òàêèå êàê ñðàâíåíèå è äåëåíèå ÷èñåë, âåñüìà ñëîæíû â ÑÎÊ. Ðàçðàáîòêà áîëåå ýôôåêòèâíûõ àëãîðèòìîâ äåëåíèÿ ïîçâîëèò íàéòè íîâûå ïåð- ñïåêòèâíûå îáëàñòè ïðèìåíåíèÿ äàííîé ñèñòåìû. Èçâåñòíûå àëãîðèòìû äåëåíèÿ â ÑÎÊ ìîæíî ðàçäåëèòü íà äâå êàòåãîðèè: ñ èñïîëüçîâàíèåì óìíîæåíèÿ è ñ èñïîëüçîâàíèåì âû÷èòàíèÿ. Áîëüøèíñòâî àëãî- ðèòìîâ íà îñíîâå óìíîæåíèÿ ïðåäâàðèòåëüíî âû÷èñëÿþò îáðàòíóþ âåëè÷èíó äå- ëèòåëÿ, ïîñëå ÷åãî ýòà âåëè÷èíà óìíîæàåòñÿ íà äåëèìîå. Àëãîðèòìû íà îñíîâå âû÷èòàíèÿ èñïîëüçóþò âû÷èòàíèå êðàòíûõ äåëèòåëÿ èç äåëèìîãî, äî òåõ ïîð, ïîêà ïîëó÷åííûé ðåçóëüòàò íå áóäåò ìåíüøå äåëèòåëÿ. Íåêîòîðûå èçâåñòíûå àë- ãîðèòìû äåëåíèÿ â ÑÎÊ íà îñíîâå óìíîæåíèÿ è ôóíêöèè ÿäðà ÑÎÊ èçëîæåíû â [18–20]. Ýòè àëãîðèòìû èñïîëüçóþò ïðåîáðàçîâàíèå â îáîáùåííóþ ïîçèöèîí- íóþ ñèñòåìó ñ÷èñëåíèÿ (ÎÏÑÑ, MRC — Mixed Radix Conversion) äëÿ íàõîæäå- íèÿ îáðàòíîé âåëè÷èíû äåëèòåëÿ è ñðàâíåíèÿ ÷èñåë. Àëãîðèòìû, îñíîâàííûå íà ÎÏÑÑ, ìåäëåííûå è òðåáóþò âûïîëíåíèÿ áîëüøîãî êîëè÷åñòâà àðèôìåòè÷åñêèõ 176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 1 Ðàáîòà âûïîëíåíà ïðè ôèíàíñîâîé ïîääåðæêå Ðîññèéñêîãî Ôîíäà Ôóíäàìåíòàëüíûõ Èññëåäîâàíèé, ãðàíòû 13-07-00478-à è 14-07-31004-ìîë-à. � Í.È. ×åðâÿêîâ, Ì.Ã. Áàáåíêî, Ï.À. Ëÿõîâ, È.Í. Ëàâðèíåíêî, 2014 îïåðàöèé. Èçâåñòåí àëãîðèòì äåëåíèÿ â ôîðìàòå ÑÎÊ [21], êîòîðûé íå èñïîëüçó- åò äâîè÷íîé ñèñòåìû ñ÷èñëåíèÿ èëè ÎÏÑÑ âî âðåìÿ äåëåíèÿ. Îí òðåáóåò äîïîë- íèòåëüíîãî íàáîðà ìîäóëåé ÑÎÊ, ÷òî âåäåò ê áîëüøîé èçáûòî÷íîñòè. Áîëüøè- íñòâó ñóùåñòâóþùèõ àëãîðèòìîâ ïðèñóùè ðàçëè÷íûå íåäîñòàòêè, ÷òî äåëàåò èõ ìåíåå ïðèãîäíûìè äëÿ ðåøåíèÿ çàäà÷è äåëåíèÿ â ÑÎÊ. Â äàííîé ñòàòüå ïðåäëàãàåòñÿ ýôôåêòèâíûé àëãîðèòì äåëåíèÿ â îáùåì ñëó- ÷àå â ÑÎÊ ñ èñïîëüçîâàíèåì òîëüêî ðåãèñòðîâûõ ñäâèãîâ è ñóììèðîâàíèé. Óëó÷øåííûé àëãîðèòì õàðàêòåðèçóåòñÿ ñëåäóþùèìè ñâîéñòâàìè: î÷åíü áûñòð ïî ñðàâíåíèþ ñ èçâåñòíûìè àëãîðèòìàìè, íå èìååò îãðàíè÷åíèé íà äåëèìîå è äåëèòåëü (êðîìå ðàâåíñòâà íóëþ äåëèòåëÿ), íå èñïîëüçóåò ïðåäâàðèòåëüíîé îöåíêè ÷àñòíîãî, îáðàòíîé âåëè÷èíû äëÿ äåëèòåëÿ è îïåðàöèè ðàñøèðåíèÿ áàçû. Èçâåñòíûå àëãîðèòìû äåëåíèÿ ÷èñåë, ïðåäñòàâëåííûõ â ÑÎÊ, áàçèðóþòñÿ íà àáñîëþòíûõ çíà÷åíèÿõ äåëèìîãî è äåëèòåëÿ. Â ðàáîòå èñïîëüçóþòñÿ íå àáñîëþò- íûå çíà÷åíèÿ, à èõ îòíîñèòåëüíûå âåëè÷èíû, ÷òî ïîçâîëÿåò óìåíüøèòü âû÷èñëèòåëüíóþ ñëîæíîñòü àëãîðèòìîâ äåëåíèÿ. ÌÎÄÈÔÈÊÀÖÈß ÀËÃÎÐÈÒÌÀ ÄÅËÅÍÈß Â ÑÈÑÒÅÌÅ ÎÑÒÀÒÎ×ÍÛÕ ÊËÀÑÑÎÂ ÍÀ ÎÑÍÎÂÅ ÏÐÈÁËÈÆÅÍÍÎÃÎ ÌÅÒÎÄÀ Ðàññìîòðèì ìîäèôèêàöèþ àëãîðèòìà îñíîâíîãî äåëåíèÿ ÷èñåë, ïðåäñòàâëåííûõ â ÑÎÊ â ñëó÷àå, êîãäà è äåëèìîå è äåëèòåëü — ïðîèçâîëüíûå öåëûå ÷èñëà è äå- ëèòåëü íå ïðèâîäèòñÿ ê ñëó÷àþ ïîïàðíî ïðîñòîãî ñ ìîäóëÿìè ÑÎÊ [22]. Ìîäè- ôèêàöèÿ îñíîâàíà íà èñïîëüçîâàíèè äåëèìîãî è äåëèòåëÿ, ïðåäñòàâëåííûõ â îò- íîñèòåëüíûõ âåëè÷èíàõ. Â ïîñëåäíåå âðåìÿ ïðîÿâëÿåòñÿ çíà÷èòåëüíûé èíòåðåñ ê ÑÎÊ, õàðàêòåðèçó- þùåéñÿ âûñîêèì óðîâíåì åñòåñòâåííîãî ïàðàëëåëèçìà ïðè âûïîëíåíèè àðèôìå- òè÷åñêèõ îïåðàöèé, âûñîêîé òî÷íîñòüþ, íàäåæíîñòüþ è ñòîéêîñòüþ. Ñïåöèàëèçèðîâàííûå ïðîöåññîðû íà îñíîâå àðèôìåòèêè ÑÎÊ èìåþò áîëü- øîå çíà÷åíèå â âûñîêîñêîðîñòíûõ ñèñòåìàõ îáðàáîòêè äàííûõ â ðåæèìå ðåàëü- íîãî âðåìåíè. Îïåðàöèè ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿ, íàçûâàåìûå ìî- äóëüíûìè îïåðàöèÿìè, ìîæíî ðåàëèçîâàòü î÷åíü áûñòðî, áåç ðàñïðîñòðàíåíèÿ ìåæðàçðÿäíûõ ïåðåíîñîâ. Íåìîäóëüíûå îïåðàöèè äåëåíèÿ, ñðàâíåíèÿ ÷èñåë, îïðåäåëåíèÿ çíàêà è ïåðåïîëíåíèÿ äèàïàçîíà îñòàþòñÿ ñðàâíèòåëüíî ìåäëåííû- ìè. Ëþáîå óëó÷øåíèå ñêîðîñòè ýòèõ ìåäëåííûõ àëãîðèòìîâ çíà÷èòåëüíî óëó÷- øàåò ïðîèçâîäèòåëüíîñòü ìíîãîìîäóëüíûõ ÀËÓ. Îáû÷íî ïðè ðàññìîòðåíèè äå- ëåíèÿ â ÑÎÊ âûäåëÿþò òðè êàòåãîðèè: äåëåíèå ñ íóëåâûì îñòàòêîì, ìàñøòàáè- ðîâàíèå è äåëåíèå â îáùåì ñëó÷àå. Ïðîáëåìà äåëåíèÿ â îáùåì âèäå â ÑÎÊ ïðèâëåêàåò âíèìàíèå ìíîãèõ èññëåäîâàòåëåé äëÿ ðàçðàáîòêè âûñîêîïðîèçâîäè- òåëüíûõ ìíîãîìîäóëüíûõ ÀËÓ. Èçâåñòíûå àëãîðèòìû äåëåíèÿ â ÑÎÊ, îñíîâàí- íûå íà èñïîëüçîâàíèè ïðåîáðàçîâàíèÿ â ÎÏÑÑ, ìàñøòàáèðîâàíèè, îêðóãëåíèè, ðàñøèðåíèè è äðóãèõ îïåðàöèÿõ, ÿâëÿþòñÿ ìåäëåííûìè è òðåáóþò âûïîëíåíèÿ áîëüøîãî êîëè÷åñòâà àðèôìåòè÷åñêèõ äåéñòâèé. Áîëüøèíñòâî èçâåñòíûõ àëãî- ðèòìîâ îñíîâàíû íà ñðàâíåíèè äåëèìîãî ñ äåëèòåëåì èëè åãî óäâîåííûì çíà÷å- íèåì, ÷òî ïðåäñòàâëÿåò îïðåäåëåííóþ ñëîæíîñòü [22]. Â ñâÿçè ñ ýòèì âîçíèêàåò íåîáõîäèìîñòü óïðîñòèòü ñòðóêòóðó âû÷èñëåíèé ïðè ñðàâíåíèè ìîäóëÿðíûõ ÷è- ñåë. Îäíèì èç íàïðàâëåíèé óïðîùåíèÿ îïåðàöèè ñðàâíåíèÿ ìîäóëÿðíûõ ÷èñåë ÿâëÿåòñÿ ïîäõîä ñ èñïîëüçîâàíèåì ïðèáëèæåííîãî ìåòîäà âû÷èñëåíèÿ ïîçèöè- îííîé õàðàêòåðèñòèêè ìîäóëÿðíîãî ÷èñëà, ïîçâîëÿþùèé àáñîëþòíî ïðàâèëüíî ðåàëèçîâàòü îñíîâíûå êëàññû ïðîöåäóð ïðèíÿòèÿ ðåøåíèé: ïðîâåðêó ðàâåíñòâà (íåðàâåíñòâà) äâóõ çíà÷åíèé, ñðàâíåíèå äâóõ çíà÷åíèé (áîëüøå, ìåíüøå) è äðó- ãèå, êîòîðûå îáåñïå÷èâàþò ðåøåíèå çàäà÷, âîçíèêàþùèõ ïðè àïïàðàòíîé èëè ïðî- ãðàììíîé ðåàëèçàöèè âû÷èñëåíèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ. Èäåÿ ïðèáëèæåííîãî ìåòîäà âû÷èñëåíèÿ ïîçèöèîííîé õàðàêòåðèñòèêè ìî- äóëÿðíîãî ÷èñëà è åãî ïðèìåíåíèÿ äëÿ äåëåíèÿ ìîäóëÿðíûõ ÷èñåë îñíîâàíà íà ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 177 èñïîëüçîâàíèè îòíîñèòåëüíûõ âåëè÷èí àíàëèçèðóåìûõ ÷èñåë ê ïîëíîìó äèàïà- çîíó, îïðåäåëÿåìîìó êèòàéñêîé òåîðåìîé îá îñòàòêàõ, ñâÿçûâàþùåé ïîçèöèîí- íîå ÷èñëî a ñ åãî ïðåäñòàâëåíèåì â îñòàòêàõ ( , , , )� � �1 2 � n , ãäå � i — íàèìåíü- øèå íåîòðèöàòåëüíûå âû÷åòû ÷èñëà, îòíîñèòåëüíî ìîäóëåé ñèñòåìû îñòàòî÷íûõ êëàññîâ p p pn1 2, , ,� âûðàæåíèåì a P p P i i p i i n P i � � � � � � �� \| \|1 1 � . (1) Çäåñü P pi i n � � � 1 , pi — ìîäóëè ÑÎÊ, \| \|Pi �1 — ìóëüòèïëèêàòèâíàÿ èíâåðñèÿ Pi îòíîñèòåëüíî pi , P P p p p p p pi i i i n� � � �1 2 1 1... ... . Â ÑÎÊ èñïîëüçóþòñÿ ðàçëè÷íûå íàáîðû ìîäóëåé äëÿ êîíêðåòíûõ ïðèëîæå- íèé. Âûáîð ñîîòâåòñòâóþùåãî íàáîðà ÿâëÿåòñÿ îäíîé èç íàèáîëåå âàæíûõ ïðî- áëåì â ÑÎÊ. Íàáîð ìîäóëåé èìååò áîëüøîå çíà÷åíèå äëÿ ïðîèçâîäèòåëüíîñòè ñèñòåìû, à òàêæå îêàçûâàåò âëèÿíèå íà äðóãèå åå ÷àñòè. Êàæäûé íàáîð èìååò ñâîè ïðåèìóùåñòâà è íåäîñòàòêè, ÷òî îáóñëîâëèâàåò èññëåäîâàíèÿ ïî èõ ñðàâíå- íèþ â çàäàííîì äèíàìè÷åñêîì äèàïàçîíå P p p pn� 1 2 � , ãäå pi — ìîäóëè ÑÎÊ. Ýòî ïîçâîëÿåò âûáðàòü íàèáîëåå ýôôåêòèâíûå íàáîðû ìîäóëåé äëÿ êàæäîãî äè- íàìè÷åñêîãî äèàïàçîíà. Íåêîòîðûå èç íèõ ïðèâîäÿò ê áîëåå ýôôåêòèâíîìó ïðåîáðàçîâàíèþ èç ïîçèöèîííîé ñèñòåìû ñ÷èñëåíèÿ â ÑÎÊ, äðóãèå ýôôåêòèâíåå ïðè àðèôìåòè÷åñêîé îáðàáîòêå äàííûõ. Îñíîâíûìè õàðàêòåðèñòèêàìè êàæäîãî íàáîðà ìîäóëåé ÿâëÿþòñÿ èõ êîëè- ÷åñòâî è òèï. Ïðåæäå âñåãî íåîáõîäèìî îáåñïå÷èòü ïîêðûòèå äèíàìè÷åñêîãî äè- àïàçîíà âû÷èñëåíèé. Ýòî ìîæíî âûïîëíèèòü ëèáî ñ áîëüøèì ÷èñëîì ìîäóëåé íåáîëüøîãî ðàçìåðà, ëèáî ñ ìåíüøèì ÷èñëîì ìîäóëåé áîëüøîãî ðàçìåðà. Â ïåð- âîì ñëó÷àå óâåëè÷èâàåòñÿ ïàðàëëåëèçì àðèôìåòè÷åñêèõ îïåðàöèé, âî âòîðîì — ñíèæàåòñÿ ñëîæíîñòü îáðàòíîãî ïðåîáðàçîâàíèÿ èç ÑÎÊ. Íåîáõîäèìî íàéòè êîìïðîìèññ ìåæäó ýòèìè äâóìÿ ñâîéñòâàìè. Êðîìå òîãî, êîíêðåòíîå ïðèëîæåíèå äëÿ ïðèìåíåíèÿ ÑÎÊ òàêæå îêàçûâàåò ñèëüíîå âëèÿíèå íà âûáîð ìîäóëåé. Äðóãèìè ñëîâàìè, íåâîçìîæíî ïîäîáðàòü åäè- íûé íàáîð ìîäóëåé, íàèëó÷øèé äëÿ âñåõ ïðèëîæåíèé. Âîïðîñû âàæíîñòè ó÷åòà êîíêðåòíîãî ïðèëîæåíèÿ ïðè âûáîðå ìîäóëåé ÑÎÊ ðàññìîòðåíû â [23–28]. Îòìå- òèì, ÷òî âûáîð ìîäóëåé ÑÎÊ ïðåäñòàâëÿåò ñîáîé ñàìîñòîÿòåëüíîå èññëåäîâàíèå, ïîýòîìó â äàííîé ðàáîòå îí ïðîâåäåí òîëüêî â ðàìêàõ ïîêðûòèÿ äèíàìè÷åñêîãî äè- àïàçîíà âû÷èñëåíèé, îïðåäåëåííîãî çíà÷åíèÿìè äåëèìîãî è äåëèòåëÿ. Ðàññìîòðèì ìåòîä âû÷èñëåíèÿ îòíîñèòåëüíûõ çíà÷åíèé â ÑÎÊ. Åñëè ðàçäå- ëèòü ëåâóþ è ïðàâóþ ÷àñòè âûðàæåíèÿ (1) íà êîíñòàíòó P, ñîîòâåòñòâóþùóþ äè- àïàçîíó ÷èñåë, òî ïîëó÷èì ïðèáëèæåííîå îòíîñèòåëüíîå çíà÷åíèå a P P p k i p i i i n i i i n i 1 1 1 1 1 1 � � � � � � \| \| � � , (2) ãäå k P p i i p i i� �\| \|1 — êîíñòàíòû âûáðàííîé ñèñòåìû, à � i — ðàçðÿäû ÷èñëà, ïðåäñòàâëåííîãî â ÑÎÊ ïî ìîäóëÿì pi , ãäå i n�1 2, , ,� , ïðè ýòîì çíà÷åíèå ñóììû (2) íàõîäèòñÿ â èíòåðâàëå [ , )0 1 . Êîíå÷íûé ðåçóëüòàò ñóììû îïðåäåëÿ- åòñÿ ïîñëå ñóììèðîâàíèÿ è îòáðàñûâàíèÿ öåëîé ÷àñòè ÷èñëà ñ ñîõðàíåíèåì äðîáíîé ÷àñòè ñóììû. Äðîáíàÿ âåëè÷èíà F a a P ( ) [ , )� 1 0 1 ñîäåðæèò êàê èíôîð- ìàöèþ î âåëè÷èíå ÷èñëà, òàê è î åãî çíàêå. Åñëè a P 1 0 1 2 � � � � �, , òî ÷èñëî a ïîëî- 178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 æèòåëüíîå è F a( ) ðàâíà âåëè÷èíå ÷èñëà a, ðàçäåëåííîé íà P. Â ïðîòèâíîì ñëó÷àå a — îòðèöàòåëüíîå ÷èñëî è 1� F a( ) ïîêàçûâàåò îòíîñèòåëüíóþ âåëè÷èíó ÷èñëà a. Îêðóãëåíèå âåëè÷èíû F a( ) äî 2� t áèòà îáîçíà÷èì êàê [ ( )]F a t2� . Òî÷íîå çíà÷åíèå âåëè÷èíû F a( ) îïðåäåëÿåòñÿ íåðàâåíñòâàìè [ ( )] ( ) [ ( )]F a F a F at t t 2 2 2� �� . Öå- ëàÿ ÷àñòü ÷èñëà, ïîëó÷åííàÿ â ðåçóëüòàòå ñóììèðîâàíèÿ êîíñòàíò k i , ïðåä- ñòàâëÿåò ñîáîé ðàíã ÷èñëà, ò.å. òàêóþ íåïîçèöèîííóþ õàðàêòåðèñòèêó, êîòîðàÿ ïîêàçûâàåò, ñêîëüêî ðàç äèàïàçîí ñèñòåìû P áûë ïðåâûøåí ïðè ïåðåõîäå îò ïðåäñòàâëåíèÿ ÷èñåë â ÑÎÊ ê åãî ïîçèöèîííîìó ïðåäñòàâëåíèþ. Ïðè íåîáõîäè- ìîñòè îïðåäåëåíèå ðàíãà ìîæåò ïðîèçâîäèòüñÿ íåïîñðåäñòâåííî â ïðîöåññå âû- ïîëíåíèÿ îïåðàöèè ñóììèðîâàíèÿ êîíñòàíò k i . Äðîáíóþ ÷àñòü ìîæíî çàïèñàòü òàêæå êàê A mod 1, òàê êàê A A A� � � � mod1. Êîëè÷åñòâî ðàçðÿäîâ äðîáíîé ÷àñòè ÷èñëà îïðåäåëÿåòñÿ ìàêñèìàëüíî âîçìîæíîé ðàçíîñòüþ ìåæäó ñîñåäíèìè ÷èñëàìè. Ïðè òî÷íîì ñðàâíåíèè, øèðîêî èñïîëüçóåìîì ïðè äåëåíèè ÷èñåë, íå- îáõîäèìî âû÷èñëèòü çíà÷åíèå, êîòîðîå ÿâëÿåòñÿ ýêâèâàëåíòîì ïðåîáðàçîâàíèÿ èç ÑÎÊ â ïîçèöèîííóþ ñèñòåìó ñ÷èñëåíèÿ. Îêðóãëåíèå âåëè÷èíû F a( ) íåèçáåæíî âëå÷åò âîçíèêíîâåíèå ïîãðåøíîñòè. Îáîçíà÷èì � � � � � �n pi i n 1 . Â ðàáîòàõ [29, 30] ïîêàçàíî, ÷òî íåîáõîäèìî èñïîëü- çîâàòü N P� � �log 2 ( )� áèò ïîñëå çàïÿòîé ïðè îêðóãëåíèè âåëè÷èíû F a( ), ÷òîáû âîçíèêàþùàÿ ïîãðåøíîñòü íå îêàçûâàëà âëèÿíèÿ íà òî÷íîñòü âû÷èñëåíèé. Äðó- ãèìè ñëîâàìè, óñòàíàâëèâàåòñÿ âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ìíî- æåñòâîì ÷èñåë, ïðåäñòàâëåííûõ â ÑÎÊ, è ìíîæåñòâîì âåëè÷èí [ ( )]F a N2� . Ïåðåéäåì ê ðàññìîòðåíèþ óëó÷øåííîé âåðñèè àëãîðèòìà äåëåíèÿ â ÑÎÊ, ïðèâåäåííîãî â [22]. Àëãîðèòì äåëåíèÿ öåëûõ ÷èñåë a b ìîæíî îïèñàòü èòåðàòèâ- íîé ñõåìîé, êîòîðàÿ âûïîëíÿåòñÿ â äâà ýòàïà. Íà ïåðâîì ýòàïå îñóùåñòâëÿåòñÿ ïîèñê ñòàðøåé ñòåïåíè 2 i ïðè àïïðîêñèìàöèè ÷àñòíîãî äâîè÷íûì ðÿäîì, íà âòî- ðîì — óòî÷íåíèå àïïðîêñèìèðóþùåãî ðÿäà. ×òîáû ïîëó÷èòü äèàïàçîí, áîëü- øèé, ÷åì P, ìîæíî âûáðàòü çíà÷åíèå � � �P Ppn 1, ò.å. ïîòðåáóåòñÿ ðàñøèðèòü áàçó ÑÎÊ, äîáàâèâ äîïîëíèòåëüíûé ìîäóëü. ×òîáû èçáåæàòü ðàñøèðåíèÿ áàçû — âû÷èñëèòåëüíî ñëîæíîé îïåðàöèè, íåîáõîäèìî ñðàâíèâàòü íå äåëèìîå ñ ïðîìåæóòî÷íûìè äåëèòåëÿìè, à òåêóùèå ðåçóëüòàòû èòåðàöèè ( )i ñ ïðåäûäó- ùèìè çíà÷åíèÿìè èòåðàöèé ( )i �1 . Ïðîöåññ óäâàèâàíèÿ äåëèòåëÿ ïîâòîðÿåì äî òåõ ïîð, ïîêà çíà÷åíèå ïðîìåæóòî÷íîãî äåëèòåëÿ ïðè i-é èòåðàöèè áóäåò ìåíüøå, ÷åì ïðè i �1-é èòåðàöèè. Ýòî ïîçâîëèò âûïîëíèòü óñëîâèå 0 1� � �b P . Àëãîðèòì äåëåíèÿ ìîæíî îïèñàòü ñëåäóþùèìè ïðàâèëàìè. Êîíñòðóèðóåòñÿ íåêîòîðîå ïðàâèëî �, êîòîðîå êàæäîé ïàðå öåëûõ ïîëîæè- òåëüíûõ ÷èñåë a è b ñòàâèò â ñîîòâåòñòâèå íåêîòîðîå ïîëîæèòåëüíîå ÷èñëî qi , ãäå i — íîìåð èòåðàöèè, òàêîå, ÷òî a bq ri i� � � 0, ò.å. a bqi� . Òîãäà äåëåíèå a íà b îñóùåñòâëÿåòñÿ ïî ñëåäóþùåìó ïðàâèëó: ñîãëàñíî îïåðàöèè � ïàðå ÷èñåë a è b ñòàâèòñÿ â ñîîòâåòñòâèå ÷èñëî q q1 0� òàêîå, ÷òî a bq r� � �1 1 0, ò.å. a bq� 1. Â êà÷åñòâå qi ïðèìåì çíà÷åíèÿ 2 i , êîòîðûå ïîìåñòèì â ïàìÿòü â âèäå êîíñòàíò c p p pi i i i n� ( , , , )2 2 21 2mod mod mod� . Ïðè ýòîì i �1-ÿ îïåðàöèÿ íå çàâèñèò îò i-é îïåðàöèè, ÷òî ïîçâîëÿåò èòåðàöèè âûïîëíÿòü ïàðàëëåëüíî. Êðîìå òîãî, â êàæ- äîé èòåðàöèè âûïîëíÿþòñÿ òîëüêî äâå îïåðàöèè: óìíîæåíèå äåëèòåëÿ íà êîí- ñòàíòó 2 i è ñðàâíåíèå ïîëó÷åííîãî çíà÷åíèÿ ñ äåëèìûì. Åñëè r b1 1� , òî äåëåíèå çàêîí÷åíî, åñëè r b1 1� , òî ñîãëàñíî ïðàâèëó � ïàðå ÷èñåë ( , )r b1 ñòàâèòñÿ â ñîîòâåòñòâèå q2 òàêîå, ÷òî a bq r� � �2 2 0, ò.å. a bq� 2 . Åñëè r b2 � , òî äåëåíèå çàâåðøàåòñÿ, åñëè r b2 � , òî ñîãëàñíî ïðàâèëó � ïàðå ÷è- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 179 ñåë ( , )r b2 ñòàâèòñÿ â ñîîòâåòñòâèå q3 òàêîå, ÷òî a bq r� � �3 3 0, è ò.ä. Òàê êàê ïî- ñëåäîâàòåëüíîå ïðèìåíåíèå îïåðàöèè � ïðèâîäèò ê óáûâàþùåé ïîñëåäîâàòåëü- íîñòè öåëûõ ÷èñåë a r r� � � �1 2 0� , àëãîðèòì ðåàëèçóåòñÿ çà êîíå÷íîå ÷èñëî øàãîâ. Ïóñòü íà m-ì øàãå çàôèêñèðîâàí ñëó÷àé 0� bqm , ÷òî îçíà÷àåò îêîí÷àíèå îïåðàöèè äåëåíèÿ. Òîãäà â èòîãå ïîëó÷èì a q q q b rm m� � � � �( )1 2 � , ãäå ðÿä q q qm1 2� � �� — àïïðîêñèìàöèÿ ÷àñòíîãî, êîòîðîå ìîæåò ñîäåðæàòü ëèøíèå qi . Äàëåå íåîáõîäèìî ïðîâåñòè óòî÷íåíèå ïîëó÷åííîãî àïïðîêñèìèðóþùåãî ðÿäà. Óòî÷íåíèå íà÷íåì ñî ñòàðøåãî qm . Åñëè a bqm� , òî qm ÿâëÿåòñÿ ÷ëåíîì àï- ïðîêñèìèðóþùåãî ðÿäà îáðàçîâàííîãî ÷àñòíîãî. Äàëåå âûáåðåì ( )q qm m� �1 . Åñëè a b q qm m� � �( )1 , òî qm�1 âíîñèòñÿ â ðÿä, èíà÷å, åñëè a b q qm m� � �( )1 , òî qm èñêëþ÷àåòñÿ èç ðÿäà, è ò.ä. Ïîñëå ïðîâåðêè âñåõ qi ÷àñòíîå îïðåäåëÿåòñÿ îñòàâøèìèñÿ ÷ëåíàìè ðÿäà. Òîãäà èñêîìîå ÷àñòíîå îïðåäåëÿåòñÿ âûðàæåíèåì a q q q q b rm m i m� � � � � � ��( )1 1� � , ãäå q q q q b a i m m i� � � � �� 1 0 1ïðè ( ) ,� Äàííûé àëãîðèòì ëåãêî ìîäèôèöèðóåòñÿ â ìîäóëÿðíóþ ôîðìó, ïðè÷åì àáñî- ëþòíûå çíà÷åíèÿ âåëè÷èí çàìåíåíû èõ îòíîñèòåëüíûìè çíà÷åíèÿìè. Ñòðóêòóðà ïðåäëàãàåìîãî àëãîðèòìà îñíîâàíà íà ïðèìåíåíèè ïðèáëèæåííîãî ìåòîäà ïðè ñðàâíåíèè ÷èñåë, êîòîðîå âûïîëíÿåòñÿ ñ èñïîëüçîâàíèåì îïåðàöèè âû÷èòàíèÿ. Èçâåñòíûå àëãîðèòìû äåëåíèÿ îïðåäåëÿþò ÷àñòíîå íà îñíîâå èòåðàöèè A A QD' � � , ãäå A è �A — ñîîòâåòñòâåííî òåêóùåå è ñëåäóþùåå äåëèìîå, D — äåëèòåëü, Q1 — ÷àñòíîå, êîòîðîå ãåíåðèðóåòñÿ íà êàæäîé èòåðàöèè èç ïîëíîãî äèàïàçîíà ÑÎÊ, à íå âûáèðàåòñÿ èç íåáîëüøîãî ìíîæåñòâà êîíñòàíò. Â ïðåäëà- ãàåìîì àëãîðèòìå ÷àñòíîå îïðåäåëÿåòñÿ íà îñíîâå èòåðàöèè r A bi i� � 2 , ãäå A — íåêîòîðîå äåëèìîå, b — äåëèòåëü, 2 i — ÷ëåí àïïðîêñèìèðóþùåãî ðÿäà ÷àñòíîãî. Òàê êàê äåëèìîå âî âñåõ èòåðàöèÿõ íå ìåíÿåòñÿ, à äåëèòåëü óìíîæàåòñÿ íà êîíñòàíòó, ïðåäëîæåííûé àëãîðèòì ïîçâîëèò óìåíüøèòü âû÷èñëèòåëüíóþ ñëîæ- íîñòü ïî ñðàâíåíèþ ñ èçâåñòíûìè àíàëîãàìè. Ïðè èòåðàöèîííîì ïðîöåññå äåëå- íèÿ â ïîçèöèîííîé ñèñòåìå ñ÷èñëåíèÿ äëÿ ïîèñêà ñòàðøåé ñòåïåíè ðÿäà àïïðîê- ñèìàöèè ÷àñòíîãî è óòî÷íåíèÿ àïïðîêñèìèðóþùåãî ðÿäà ñðàâíèâàþòñÿ äåëèìîå ñ óäâîåííûìè äåëèòåëÿìè èëè ñóììîé ÷ëåíîâ ðÿäà. Ïðèìåíåíèå ýòîãî ïðèíöèïà äëÿ ÑÎÊ ìîæåò ïðèâåñòè ê íåêîððåêòíîé ðàáîòå àëãîðèòìà, ïîñêîëüêó ïðè ïå- ðåïîëíåíèè äèíàìè÷åñêîãî äèàïàçîíà ïðîìåæóòî÷íîãî äåëèòåëÿ âîññòàíîâëåííîå ÷èñëî ìîæåò âûéòè çà ïðåäåëû äàííîãî äèàïàçîíà, ÷òî âûçâàíî öèêëè÷íîñòüþ ÑÎÊ. Ïðè ýòîì çíà÷åíèå ïðîìåæóòî÷íîãî äåëèòåëÿ âñå åùå áóäåò ìåíüøå äåëèìî- ãî. Ýòî íå ñîîòâåòñòâóåò äåéñòâèòåëüíîñòè, òàê êàê íà ñàìîì äåëå ÷èñëà áóäóò ïðå- âûøàòü äèàïàçîí P è àëãîðèòì ïåðåéäåò â ðåæèì «çàöèêëèâàíèå». Íàïðèìåð, åñëè ìîäóëè ÑÎÊ ðàâíû p1 2� , p2 3� , p3 5� , p4 7� , òî äèàïàçîí P � � � � �2 3 5 7 210. Äîïóñòèì, ïðè âîññòàíîâëåíèè ïîëó÷èëè ÷èñëî A � 220. Â ÑÎÊ A � �220 0 1 0 3( , , , ), ò.å. A � 210 è � �A 10 èìåþò îäèíàêîâûå ïðåäñòàâëåíèÿ â ñèñòåìå. Óêàçàííàÿ íå- îäíîçíà÷íîñòü ìîæåò ïðèâåñòè ê íàðóøåíèþ ðàáîòû àëãîðèòìà. Äëÿ ïðåîäîëåíèÿ ýòîé òðóäíîñòè íåîáõîäèìî â ÑÎÊ ñðàâíèâàòü ðåçóëüòàòû òåêóùèõ çíà÷åíèé èòåðàöèé ñ ïðåäûäóùèìè, ÷òî ïîçâîëÿåò ïðàâèëüíî îïðåäå- ëèòü áîëüøåå èëè ìåíüøåå ÷èñëî. Èòàê, ôàêò ïåðåïîëíåíèÿ äèíàìè÷åñêîãî äèà- ïàçîíà â ÑÎÊ ìîæíî èñïîëüçîâàòü äëÿ ïðèíÿòèÿ ðåøåíèÿ «áîëüøå – ìåíüøå». Íà ïåðâîé èòåðàöèè ïðîèñõîäèò ñðàâíåíèå äåëèìîãî ñ äåëèòåëåì, íà îñòàëü- íûõ èòåðàöèÿõ — ñðàâíåíèå óäâîåííûõ çíà÷åíèé äåëèòåëåé q b q bi i� �1 . Íà êàæ- äîé íîâîé èòåðàöèè ïðîèñõîäèò ñðàâíåíèå òåêóùåãî çíà÷åíèÿ ñ ïðåäûäóùèì. Ïîñëåäîâàòåëüíîå ïðèìåíåíèå ýòèõ èòåðàöèé ïðèâîäèò ê ôîðìèðîâàíèþ öåïî÷- 180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 â ïðîòèâíîì ñëó÷àå. êè íåðàâåíñòâ bq bq bq bqm m1 2 1� � � � �� , îïðåäåëÿþùèõ íåîáõîäèìîå êîëè- ÷åñòâî òðåáóåìûõ èòåðàöèé, çàâèñÿùèõ îò âåëè÷èí äåëèìîãî è äåëèòåëÿ. Òàêèì îáðàçîì, àëãîðèòì ðåàëèçóåòñÿ çà êîíå÷íîå ÷èñëî èòåðàöèé. Ïóñòü íà m �1-é èòå- ðàöèè çàôèêñèðîâàí ñëó÷àé îêîí÷àíèÿ âîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè bq bqm m� �1, ÷òî ñîîòâåòñòâóåò ïåðåïîëíåíèþ äèàïàçîíà ÑÎÊ, ò.å. bq Pm� �1 è a bqm� �1. Íà ýòîì ïðîöåññ ôîðìèðîâàíèÿ èíòåðïîëÿöèè ÷àñòíîãî äâîè÷íûì ðÿäîì èëè íàáîðîì êîíñòàíò â ÑÎÊ çàâåðøàåòñÿ. Èòàê, ïðîöåññ àïïðîêñèìàöèè ÷àñòíîãî ìîæåò îñóùåñòâëÿòüñÿ ïóòåì ñðàâíåíèÿ ñîñåäíèõ ïðèáëèæåííûõ äåëèòåëåé. ÍÎÂÛÉ ÀËÃÎÐÈÒÌ ÎÑÍÎÂÍÎÃÎ ÄÅËÅÍÈß ÌÎÄÓËßÐÍÛÕ ×ÈÑÅË Ïðåäëàãàåìûé àëãîðèòì îñíîâíîãî äåëåíèÿ ìîäóëÿðíûõ ÷èñåë íà îñíîâå ïðè- áëèæåííîãî ìåòîäà ñðàâíåíèÿ ÷èñåë ðàáîòàåò ñëåäóþùèì îáðàçîì. Ïîäàâ íà âõîä äåëèìîå a è äåëèòåëü b, âû÷èñëÿåì ÷àñòíîå Q è îñòàòîê R òàêèå, ÷òî a Qb R� � è 0 � �R b. Ñòðóêòóðà àëãîðèòìà ñîñòîèò èç ñëåäóþùèõ áëîêîâ. Áëîê 1. Âû÷èñëåíèå îòíîñèòåëüíûõ çíà÷åíèé äåëèìîãî è äåëèòåëÿ. Ïîñòóïèâøèå íà âõîä àáñîëþòíûå çíà÷åíèÿ äåëèìîãî a è äåëèòåëÿ b ïåðåâî- äÿòñÿ â îòíîñèòåëüíûå çíà÷åíèÿ ê ïîëíîìó äèàïàçîíó ÑÎÊ â ñîîòâåòñòâèè ñ âû- ðàæåíèåì (2). Ïîëó÷åííûå îòíîñèòåëüíûå çíà÷åíèÿ F a a P ( ) � � � � � � 1 è F b b P ( ) � � � � � � 1 ïðåäñòàâëåíû â âèäå äâîè÷íîé äðîáè. Áëîê 2. Ñðàâíåíèå îòíîñèòåëüíûõ çíà÷åíèé äåëèìîãî è äåëèòåëÿ. Åñëè F a F b( ) ( )� , òî ïðîöåññ çàâåðøàåòñÿ, åñëè F a F b( ) ( )� , òî îñóùåñòâëÿ- åòñÿ ïîèñê ñòàðøåé ñòåïåíè äâîè÷íîé äðîáè 2� i ïðè àïïðîêñèìàöèè ÷àñòíîãî Q äâîè÷íîé äðîáüþ. Áëîê 3. Ïîèñê ñòàðøåé ñòåïåíè ðÿäà. Ñòàðøàÿ ñòåïåíü äåëèòåëÿ F b( ) îïðåäåëÿåòñÿ ôàêòîì ïåðåïîëíåíèÿ ðàçðÿä- íîé ñåòêè, âîçíèêàþùåé ïîñëå i-ãî óìíîæåíèÿ íà 2 äâîè÷íîé äðîáè. Â àëãîðèòìå óìíîæåíèå âûïîëíÿåòñÿ ñäâèãîì âëåâî äâîè÷íîé äðîáè äî ïîÿâëåíèÿ ïåðåíîñà ñòàðøåãî çíà÷àùåãî ðàçðÿäà â çíàêîâûé ðàçðÿä. Êîëè÷åñòâî ñäâèãîâ îïðåäåëÿåò ñòàðøóþ ñòåïåíü äâîè÷íîãî ðÿäà ïðè àïïðîêñèìàöèè ÷àñòíîãî Q. Áëîê 4. Îïðåäåëåíèå ÷ëåíîâ äâîè÷íîãî ðÿäà, íåîáõîäèìûõ äëÿ îáðàçîâàíèÿ ÷àñòíîãî Q. Ôîðìèðîâàíèå ÷ëåíîâ ðÿäà ÷àñòíîãî Q íà÷èíàåì ñî ñòàðøåé ñòåïåíè ðÿäà, âõîäÿùåé â àïïðîêñèìàöèîííûé ðÿä. Îñòàëüíûå ÷ëåíû ðÿäà ïîëó÷àþòñÿ ïóòåì åãî äåëåíèÿ íà 2, êîòîðîå â àëãîðèòìå ôîðìèðóåòñÿ ñ ïîìîùüþ îïåðàöèé ñäâèãà âïðàâî. Îïðåäåëåíèå ÷ëåíîâ àïïðîêñèìàöèîííîãî ðÿäà, íåîáõîäèìûõ äëÿ îáðà- çîâàíèÿ ÷àñòíîãî, îñóùåñòâëÿåòñÿ ïóòåì àíàëèçà ïîëó÷åííûõ çíà÷åíèé ïðîìå- æóòî÷íûõ ÷àñòíûõ, îáðàçîâàííûõ ïðè ïîñëåäîâàòåëüíîé èõ âûáîðêå, è ñóììè- ðîâàíèÿ. ×ëåíû ðÿäà, ñóììèðóåìûå ñ ïðîìåæóòî÷íûìè ÷àñòíûìè è íå ïðåâîñõî- äÿùèå äåëèìîãî, âêëþ÷àþòñÿ â îáðàçîâàíèå ÷àñòíîãî, à òå ÷ëåíû ðÿäà, ñóììèðîâàíèå êîòîðûõ ïðèâåäåò ê ïðåâûøåíèþ äåëèìîãî, îòáðàñûâàþòñÿ. Áëîê 5. Âû÷èñëåíèå ÷àñòíîãî Q a b � � � �� . Äëÿ ïîëó÷åíèÿ ÷àñòíîãî îò äåëåíèÿ a íà b ñóììèðóåì âñå îñòàâøèåñÿ ÷ëåíû àïïðîêñèìàöèîííîãî ðÿäà (áëîê 4), íåîáõîäèìûå äëÿ îáðàçîâàíèÿ ÷àñòíîãî. Íà ýòîì ðàáîòà àëãîðèòìà çàêàí÷èâàåòñÿ. Äàëåå ïðèâîäèòñÿ äåòàëüíîå îïèñàíèå óëó÷øåííîãî àëãîðèòìà äåëåíèÿ ìî- äóëÿðíûõ ÷èñåë. Âûïîëíèì àïïðîêñèìàöèþ ÷àñòíîãî. Øàã 1. Âû÷èñëÿåì ïðèáëèæåííûå çíà÷åíèÿ äåëèìîãî F a( ) è äåëèòåëÿ F b( ) è ñðàâíèâàåì èõ. Åñëè F a F b( ) ( )� , òî ïðîöåññ äåëåíèÿ çàêàí÷èâàåòñÿ è ÷àñòíîå a b � � �� ñî- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 181 îòâåòñòâåííî ðàâíî 0 èëè 1. Åñëè F a F b( ) ( )� , òî îñóùåñòâëÿåòñÿ ïîèñê ñòàðøåé ñòåïåíè 2� N ïðè àïïðîêñèìàöèè ÷àñòíîãî a äâîè÷íûì êîäîì, ãäå N — ìèíè- ìàëüíûé çíà÷àùèé ðàçðÿä äâîè÷íîé äðîáè. Ïðîâåäåì ïîèñê ñòàðøåé ñòåïåíè äâîè÷íîé äðîáè. Øàã 2. Ñäâèãàåì ôóíêöèþ [ ( )]F b N2� âëåâî äî èçìåíåíèÿ ïåðâîãî äâîè÷íîãî ðàçðÿäà ïîñëå çàïÿòîé. Êîëè÷åñòâî ñäâèãîâ îïðåäåëÿåò ñòàðøóþ ñòåïåíü j, êîòî- ðàÿ ðåãèñòðèðóåòñÿ ñ÷åò÷èêîì èìïóëüñîâ, ñîåäèíåííûõ ñ ïàìÿòüþ V . Íà ýòîì àïïðîêñèìàöèÿ ÷àñòíîãî çàêàí÷èâàåòñÿ. Äëÿ óòî÷íåíèÿ àïïðîêñè- ìàöèîííîãî ðÿäà ÷àñòíîãî âûïîëíèì ñëåäóþùèå øàãè. Øàã 3. Èç ïàìÿòè âûáèðàåì êîíñòàíòó 2 j (ñòàðøàÿ ñòåïåíü ðÿäà) è óìíîæà- åì åå íà äåëèòåëü. Âåëè÷èíó 2 j F b( ) ñðàâíèâàåì ñ äåëèìûì F a( ) ñ ïîìîùüþ ïðèáëèæåííîãî ìåòîäà ñðàâíåíèÿ ÷èñåë â ÑÎÊ. Êîíñòàíòû 2 j , 1 2� �j Plog , ïðåäâàðèòåëüíî çàïèñàíû â ïàìÿòü V , ñ÷åò÷èê j è ÷àñòíîå Q óñòàíîâëåíû â «0». Âûõîäû ñ÷åò÷èêà ÿâëÿþòñÿ àäðåñíûìè âõîäàìè ïàìÿòè V . Øàã 4. Âû÷èñëÿåì � 1 1� �F a F b( ) ( ). Åñëè â çíàêîâîì ðàçðÿäå � 1 çíà÷åíèå «1», òî ñîîòâåòñòâóþùàÿ ñòåïåíü ðÿäà îòáðàñûâàåòñÿ, åñëè çíà÷åíèå «0», òî â ñóììàòîð ÷àñòíîãî äîáàâëÿåì çíà÷åíèå ÷ëåíà ðÿäà ñ ýòîé ñòåïåíüþ, ò.å. 2 j ipmod , 1 � �i n, 0 � �j N . Øàã 5. Ïðîâåðÿåì ÷ëåí ðÿäà ñî ñòåïåíüþ 2 1j� ïóòåì ñäâèãà âïðàâî è ñðàâ- íåíèÿ. Ñðàâíèâàåì � 1 è 2 1j b� . Åñëè � 1 12� �j b, òî ñîîòâåòñòâóþùàÿ ñòåïåíü ðÿäà îòáðàñûâàåòñÿ; åñëè � 1 12� �j b, òî â ñóììàòîð ÷àñòíîãî äîáàâëÿåì çíà÷åíèå ÷ëåíà ðÿäà ñ ýòîé ñòåïåíüþ, ò.å. 2 1j ip� mod è � �2 1 12� � �j b. Øàã 6. Àíàëîãè÷íî ïðîâåðÿåì âñå îñòàâøèåñÿ ÷ëåíû ðÿäà äî íóëåâîé ñòå- ïåíè. Ïîñëåäíåå � �i i iR F� � �� 1 1, ò.å. 0 � �R b, áóäåò îñòàòêîì îò äåëåíèÿ a íà b. ×àñòíûì Q áóäåò ñóììà âñåõ 2 i , íåîáõîäèìûõ äëÿ îáðàçîâàíèÿ ÷àñòíîãî, êîòîðûå áûëè íàêîïëåíû â ñóììàòîðå. Ðàáîòà àëãîðèòìà çàâåðøàåòñÿ. Ïîêàæåì ðàáîòó ìîäèôèöèðîâàííîãî àëãîðèòìà íà ïðèìåðå. Ïðèìåð. Íàéòè ÷àñòíîå Q a b � îò äåëåíèÿ ÷èñëà a � 97 íà ÷èñëî b � 8 â ÑÎÊ ñ îñíîâàíèÿìè p1 2� , p2 3� , p3 5� , p4 7� . Òîãäà P � � � � �2 3 5 7 210, � � � � � � � �2 3 5 7 4 13, P P p 1 1 105� � , P P p 2 2 70� � , P P p 3 3 42� � , P P p 4 4 30� � . Êîíñòàíòû k i , èñïîëüçóåìûå äëÿ âû÷èñëåíèé îòíîñèòåëüíûõ âåëè÷èí, ðàâíû k1 2 1 105 2 1 2 � � � � � � � � , k2 3 1 70 3 1 3 � � � � � � � � , k3 5 1 42 5 3 5 � � � � � � � � , k4 7 1 30 7 4 7 � � � � � � � � . Äëÿ âûïîëíåíèÿ òî÷íûõ îïåðàöèé ñ îòíîñèòåëüíûìè âåëè÷èíàìè ÷èñåë â ÑÎÊ íåîáõîäèìî èñïîëüçîâàòü N P� � � �log 2 12( )� çíàêîâ ïîñëå çàïÿòîé. Êîí- ñòàíòû k i , îêðóãëåííûå äî 12 äâîè÷íûõ çíàêîâ ïîñëå çàïÿòîé, ðàâíû k1 0100000000000� , , k2 0 010101010101� , , k3 0100110011001� , , k4 0100100100100� , . Ïðåäñòàâèì â ÑÎÊ ÷èñëà a è b: a10 97 1 1 2 6� � ( , , , )ÑÎÊ , b10 8 0 2 3 1� � ( , , , )ÑÎÊ . 182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 Îòíîñèòåëüíûå âåëè÷èíû äåëèìîãî a è äåëèòåëÿ b ïðè ïîëíîé òî÷íîñòè âû- ÷èñëåíèé N ðàâíû [ ( )] ,F a 2 12 0 011101011111� � , [ ( )] ,F b 2 12 0 000010011001� � . Ñäâèãàÿ äðîáíóþ ÷àñòü äåëèòåëÿ b âëåâî, øàã çà øàãîì, îïðåäåëÿåì, ÷òî èç- ìåíåíèå ïåðâîãî äðîáíîãî ðàçðÿäà ïîñëå çàïÿòîé ïðîèñõîäèò íà ÷åòâåðòîì ñäâè- ãå. Òàêèì îáðàçîì, â àïïðîêñèìàöèîííûé ðÿä ìîãóò âõîäèòü òîëüêî âåëè÷èíû 20 , 21, 22 è 23 , êîòîðûå â ÑÎÊ èìåþò ñëåäóþùåå ïðåäñòàâëåíèå: q0 02 1 1 1 1� � ( , , , ), q1 12 0 2 2 2� � ( , , , ), q2 22 0 1 4 4� � ( , , , ), q3 32 0 2 3 1� � ( , , , ). Äàííûå âåëè÷èíû è áóäóò ôîðìèðîâàòü àïïðîêñèìàöèîííûé ðÿä ÷àñòíîãî, êîòîðûé â äàëüíåéøåì áóäåò óòî÷íåí. Äëÿ óòî÷íåíèÿ àïïðîêñèìàöèîííîãî ðÿäà âû÷èòàåì èç äðîáè [ ( )]F a 2 12� äåëèìîãî äðîáü [ ( )]F b 2 12� äåëèòåëÿ, ñäâèíóòóþ âëåâî íà òðè ðàçðÿäà (ò.å. óìíîæåííóþ íà 23): � 1 2 3 212 122 0 011101011111 0 010011� � � �� [ ( )] [ ( )] , ,F a F b 001 0 001010010111� , . Òàê êàê � 1 0� , òî 23 îñòàâëÿåì â àïïðîêñèìàöèîííîì ðÿäó, à âåëè÷èíó � 1 èñïîëüçóåì â äàëüíåéøèõ âû÷èñëåíèÿõ. Âû÷èòàåì èç � 1 äðîáü [ ( )]F b 2 12� äåëèòåëÿ, ñäâèíóòóþ âëåâî íà äâà ðàçðÿäà: � �2 1 2 2 2 0 001010010111 0 0010011001 0 012� � � � ��[ ( )] , , ,F b 00000110011. Ïîñêîëüêó � 2 0� , òî 22 îñòàâëÿåì â àïïðîêñèìàöèîííîì ðÿäó, à âåëè÷èíó � 2 èñïîëüçóåì â äàëüíåéøèõ âû÷èñëåíèÿõ. Âû÷èòàåì èç � 2 äðîáü [ ( )]F b 2 12� äåëèòåëÿ, ñäâèíóòóþ âëåâî íà îäèí ðàçðÿä: � �3 2 1 2 2 0 000000110011 0 00010011001 112� � � � ��[ ( )] , , ,F b 111100000001 . Ïîÿâëåíèå åäèíèöû â çíàêîâîì ðàçðÿäå îçíà÷àåò, ÷òî � 3 0� , ïîýòîìó 21 èñ- êëþ÷àåì èç àïïðîêñèìàöèîííîãî ðÿäà, à � 3 â äàëüíåéøåì íå èñïîëüçóåì (ïðî- äîëæàåì èñïîëüçîâàòü � 2). Âû÷èòàåì èç � 2 äðîáü [ ( )]F b 2 12� äåëèòåëÿ (áåç ñäâèãîâ): � �4 2 01 2 2 0 000000110011 0 00001001100112� � � � ��[ ( )] , ,F b 1111110011010, . Ïîÿâëåíèå åäèíèöû â çíàêîâîì ðàçðÿäå îçíà÷àåò, ÷òî � 4 0� , ïîýòîìó 20 èñ- êëþ÷àåì èç àïïðîêñèìàöèîííîãî ðÿäà. Íà ýòîì ïðîöåññ óòî÷íåíèÿ àïïðîêñèìàöèîííîãî ðÿäà çàâåðøàåòñÿ. Äëÿ îïðåäåëåíèÿ ÷àñòíîãî íåîáõîäèìî ñëîæèòü îñòàâøèåñÿ ÷ëåíû àïïðîêñèìàöèîí- íîãî ðÿäà. Â äàííîì ïðèìåðå îñòàëèñü ñëåäóþùèå ÷ëåíû ðÿäà: q3 32� � � ( , , , )0 2 3 1 è q2 22 0 1 4 4� � ( , , , ). Òîãäà ÷àñòíîå îïðåäåëÿåòñÿ ïóòåì ñóììèðîâà- íèÿ ÷ëåíîâ ðÿäà: a b � � �� ( , , , ) ( , , , ) ( , , , )0 2 3 1 0 1 4 4 0 0 2 5 12. Äëÿ îöåíêè ýôôåêòèâíîñòè ïðåäëîæåííîãî àëãîðèòìà ïðîàíàëèçèðóåì ñëîæíîñòü âûïîëíåíèÿ îïåðàöèé íà êàæäîì ýòàïå ðàáîòû àëãîðèòìà. 1. Íàõîæäåíèå äðîáåé F a( ) è F b( ) ïî ôîðìóëå (2) òðåáóåò âûïîëíåíèÿ n óìíîæåíèé, êîòîðûå ìîãóò áûòü ðåàëèçîâàíû òàáëè÷íî, ñ èñïîëüçîâàíèåì LUT òàáëèö ïî Npi áèò äëÿ êàæäîãî ìîäóëÿ ÑÎÊ. Äëÿ ñóììèðîâàíèÿ íåîáõîäèìî � �log 2n ñóììèðîâàíèé ÷èñåë äëèíû N . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 183 2. Ïðîöåäóðà ñîñòàâëåíèÿ àïïðîêñèìàöèîííîãî ðÿäà ÷àñòíîãî ïîòðåáóåò â õóäøåì ñëó÷àå � �log 2 P îïåðàöèé ñäâèãà. 3. Äëÿ óòî÷íåíèÿ ðÿäà ÷àñòíîãî ïîòðåáóåòñÿ â õóäøåì ñëó÷àå � �log 2 P îïå- ðàöèé ñäâèãà è � �log 2 P îïåðàöèé âû÷èòàíèÿ ÷èñåë äëèíû N . 4. Ñóììèðîâàíèå ÷ëåíîâ ðÿäà ïðè îêîí÷àòåëüíîì ïîëó÷åíèè çíà÷åíèÿ ÷àñòíîãî ìîæåò áûòü îðãàíèçîâàíî ïàðàëëåëüíî ñ ïðåäûäóùèìè ïóíêòàìè è íå òðåáóåò äîïîëíèòåëüíîãî âðåìåíè íà âûïîëíåíèå. Òàêèì îáðàçîì, äëÿ ðåàëèçàöèè àëãîðèòìà òðåáóåòñÿ N n� � �log 2 � � � �( )N P2 2log òàêòîâ âû÷èñëèòåëüíîé ñèñòåìû è N p p pn( )1 � � �2 � áèò ïàìÿòè. Àëãîðèòì, èçëîæåííûé â ðàáîòå [22], òðåáóåò âûïîëíåíèÿ â õóäøåì ñëó÷àå 2 2� �log P îïåðàöèé ñðàâíåíèÿ â ÑÎÊ. Íàèëó÷øèé ìåòîä ñðàâíåíèÿ ÷èñåë â ÑÎÊ òðåáóåò ïðèìåíåíèÿ ïðåîáðàçîâàíèÿ ÷èñëà â ÎÏÑÑ [27]. Äëÿ êàæäîé îïåðàöèè ïðåîáðàçîâàíèÿ íåîáõîäèìî âûïîëíèòü îäíî òàáëè÷íîå óìíîæåíèå è ñóììèðî- âàíèå n ÷èñåë øèðèíû max {log }2 pi , 1 � �i n, êîòîðîå â ñèëó îñîáåííîñòåé ìåòî- äà ÎÏÑÑ íå ìîæåò áûòü îðãàíèçîâàíî ïàðàëëåëüíî [11]. Òàêèì îáðàçîì, âû÷èñ- ëèòåëüíàÿ ñëîæíîñòü èçâåñòíîãî àëãîðèòìà ñîñòàâëÿåò 2 2 2n P pi� �log {log }max . Ñðàâíåíèå àëãîðèòìîâ äåëåíèÿ â ÑÎÊ ïðèâåäåíî íà ðèñ. 1. Áûëà ñìîäåëèðîâà- íà ðàáîòà ïðåäëîæåííîãî àëãîðèòìà è àëãîðèòìà èç [22] â ÑÎÊ ñ äèàïàçîíàìè 16, 32 è 64 áèò. Â êà÷åñòâå êðèòåðèÿ ñðàâíåíèÿ èñïîëüçîâàíî êîëè÷åñòâî òàêòîâ âû÷èñ- ëèòåëüíîé ñèñòåìû, íåîáõîäèìûõ äëÿ âûïîëíåíèÿ àëãîðèòìîâ. Ðåçóëüòàòû ìîäåëè- ðîâàíèÿ ïîêàçûâàþò, ÷òî ïðåäëîæåííûé àëãîðèòì ðàáîòàåò áûñòðåå. Äëÿ ÑÎÊ ñ äè- àïàçîíîì 16 áèò âðåìÿ ðàáîòû ñîêðàùàåòñÿ ïðèìåðíî â 1,4 ðàçà, ñ äèàïàçîíîì 32 áèò — â 2,6 ðàç, ñ äèàïàçîíîì 64 áèò — â 2,3 ðàçà. Äàííûé ðåçóëüòàò ñâèäåòåëüñòâó- åò î òîì, ÷òî ðàçðàáîòàííûé àëãîðèòì ïðåâîñõîäèò èçâåñòíûå àíàëîãè ïî ñêîðîñòè è ÿâëÿåòñÿ ëó÷øèì íà ñåãîäíÿøíèé äåíü. ÇÀÊËÞ×ÅÍÈÅ Èçëîæåííûé â ñòàòüå àëãîðèòì ïîçâîëÿåò âûïîëíÿòü îïåðàöèþ äåëåíèÿ â ÑÎÊ áûñòðåå, ÷åì ïðè èñïîëüçîâàíèè èçâåñòíûõ ïîäõîäîâ. Ýòî îáúÿñíÿåòñÿ òåì, ÷òî ñòðóêòóðà àëãîðèòìà ñîäåðæèò ïðîñòûå îïåðàöèè: ïðè ôîðìèðîâàíèè 184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 Ðèñ. 1. Ãðàôèê âðåìåíè ðàáîòû àëãîðèòìîâ äåëåíèÿ â ÑÎÊ Ïðåäëîæåííûé àëãîðèòì Èçâåñòíûé àëãîðèòì 12 9 6 3 0 áèò 16 32 64 t �103 äðîáåé-ýêâèâàëåíòîâ èñïîëüçóþòñÿ îïåðàöèè ñëîæåíèÿ è óìíîæåíèÿ, à ïðè íåïîñðåäñòâåííîì íàõîæäåíèè ÷àñòíîãî — îïåðàöèè ñäâèãà è âû÷èòàíèÿ. Ïå- ðåõîä ê ïðåäñòàâëåíèþ ÷èñåë â ÑÎÊ â âèäå îòíîøåíèÿ ê äèàïàçîíó ïîçâîëèë èçáåæàòü íåîáõîäèìîñòè ïðèìåíåíèÿ â àëãîðèòìå òàêèõ îïåðàöèé, êàê íàõîæ- äåíèå îñòàòêà ÷èñëà ïî ìîäóëþ è ïåðåâîä ÷èñëà â ÎÏÑÑ. Óêàçàííûå îïåðà- öèè âåñüìà çàòðàòíû â ÑÎÊ, ïîýòîìó ïðèâåäåííûé àëãîðèòì, íå èñïîëüçóþ- ùèé èõ, ðàáîòàåò áûñòðåå èçâåñòíûõ àíàëîãîâ. Óëó÷øåíèå ñêîðîñòè âûïîëíåíèÿ äåëåíèÿ ÷èñåë ïîçâîëèò ðàñøèðèòü ïðè- ìåíåíèå ÑÎÊ íà ïðàêòèêå. Ïðåäëîæåííûé ïîäõîä ìîæåò áûòü óñïåøíî èñïîëü- çîâàí â ïðèëîæåíèÿõ, òðåáóþùèõ âûïîëíåíèÿ íå òîëüêî îïåðàöèé ñëîæåíèÿ, âû- ÷èòàíèÿ, óìíîæåíèÿ, íî è äåëåíèÿ. Ïîèñê íîâûõ îáëàñòåé ïðèìåíåíèÿ ÑÎÊ íà ïðàêòèêå ïðîäîëæàåò îñòàâàòüñÿ àêòóàëüíîé çàäà÷åé, ïîýòîìó èçëîæåííûé â ðà- áîòå ïîäõîä ìîæåò ðàñøèðèòü ïðèêëàäíóþ çíà÷èìîñòü ìîäóëÿðíîé àðèôìåòèêè. Ñëåäóåò îòìåòèòü, ÷òî ñîâðåìåííîå ñîñòîÿíèå òåîðèè ÑÎÊ òàêîâî, ÷òî íà- õîæäåíèå óëó÷øåííûõ âàðèàíòîâ àëãîðèòìîâ âûïîëíåíèÿ íåìîäóëüíûõ îïåðà- öèé ÿâëÿåòñÿ âàæíîé è àêòóàëüíîé çàäà÷åé. Íàðÿäó ñ äåëåíèåì íåîáõîäèìà ðàç- ðàáîòêà áûñòðîäåéñòâóþùèõ àëãîðèòìîâ îïðåäåëåíèÿ çíàêà ÷èñëà, ñðàâíåíèÿ ÷èñåë, îáíàðóæåíèÿ è ëîêàëèçàöèè îøèáêè è äð. Â íàñòîÿùåå âðåìÿ âåäåòñÿ àê- òèâíûé ïîèñê îïòèìàëüíûõ íàáîðîâ ìîäóëåé ñïåöèàëüíîãî âèäà. Îäíàêî äàí- íûé ïîäõîä ÿâëÿåòñÿ äîñòàòî÷íî óçêèì è îäíîáîêèì, â òî âðåìÿ êàê ðàçðàáîòêà íîâûõ òåîðåòè÷åñêèõ ïðèíöèïîâ ÑÎÊ ìîæåò äàòü õîðîøèé ðåçóëüòàò íà ïðàêòè- êå. Ñîçäàíèå ïðèíöèïèàëüíî íîâûõ àëãîðèòìîâ âûïîëíåíèÿ ïðîáëåìíûõ îïåðà- öèé â ÑÎÊ áóäåò ñïîñîáñòâîâàòü ðàçâèòèþ äàííîé îáëàñòè ìàòåìàòèêè. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. M o l a h o s s e i n i A . S . , S o r o u r i S . , Z a r a n d i A . A . E . Research challenges in next-generation residue number system architectures // Computer Science & Education (ICCSE), 7th Intern. Conf. — 2012. — P. 1658–1661. 2. Y a t s k i v V . , S u J u n , Y a t s k i v N . , S a c h e n k o A . , O s o l i n s k i y O . Multilevel method of data coding in WSN // Intelligent Data Acquisition and Advanced Computing Systems (IDAACS), IEEE 6th Intern. Conf. — 2011. — P. 863–866. 3. S u J u n , Z h e n g b i n g H u . Method and dedicated processor for image coding based on residue number system // Modern Problems of Radio Engineering Telecommunications and Computer Science (TCSET), Intern. Conf. — 2012. — P. 406–407. 4. Ñ ó Ö ç ó í ü . Ìíîãîóðîâíåâûé ìåòîä êîäèðîâàíèÿ äàííûõ â áåñïðîâîäíûõ ñåíñîðíûõ ñåòÿõ // Ýëåêòðîòåõí. è êîìïüþòåð. ñèñòåìû. — 2011. — ¹ 4. — Ñ. 213–218. 5. Ë ÿ õ î â Ï . À . , × å ð â ÿ ê î â Í . È . Ðåàëèçàöèÿ ìíîãîêàíàëüíûõ ôèëüòðîâ â ñèñòåìå îñòà- òî÷íûõ êëàññîâ // Èíôîêîììóíèêàö. òåõíîëîãèè. — 2011. — 9, ¹ 2. — Ñ. 4–7. 6. C h e r v y a k o v N . I . , V e l i g o s h a A . V . , T y n c h e r o v K . T . , V e l i k i k h S . A . Use of modular coding for high-speed digital filter design // Cybernetics and Systems Analysis. — 1998. — N 34. — P. 254–260. 7. Z h e n g X D . , X u J . , L i W . Parallel DNA arithmetic operation based on n-moduli set // Appl. Math. and Comput. — 2009. — 212, N 1. — P. 177–184. 8. G o m a t h i s a n k a r a n M . , T y a g i A . , N a m u d u r i K . HORNS: A homomorphic encryption scheme for cloud computing using residue number system // Inform. Sci. and Systems (CISS), 45th Ann. Conf. — 2011. — P. 1–5. 9. A l i a G . , M a r t i n e l l i E . NEUROM: a ROM based RNS digital neuron // Neural Networks. — 2005. — 18. — P. 179–189. 10. × å ð â ÿ ê î â Í . È . , Ñ à õ í þ ê Ï . À . , Ø à ï î ø í è ê î â À . Â . , Ì à ê î õ à À . Í . Íåéðî- êîìïüþòåðû â îñòàòî÷íûõ êëàññàõ. — Ì.: Ðàäèîòåõíèêà, 2003. — 272 ñ. 11. × å ð â ÿ ê î â Í . È . , Ñ à õ í þ ê Ï . À . , Ø à ï î ø í è ê î â À . Â . , Ð ÿ ä í î â Ñ . À . Ìîäó- ëÿðíûå ïàðàëëåëüíûå âû÷èñëèòåëüíûå ñòðóêòóðû íåéðîïðîöåññîðíûõ ñèñòåì. — Ì.: Ôèçìàòëèò, 2003. — 288 ñ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 185 12. × å ð â ÿ ê î â Í . È . , Å â ä î ê è ì î â À . À . , Ã à ë ó ø ê è í À . È . , Ë à â ð è í å í ê î È . Í . , Ë à â ð è í å í ê î À . Â . Ïðèìåíåíèå èñêóññòâåííûõ íåéðîííûõ ñåòåé è ñèñòåìû îñòàòî÷íûõ êëàññîâ â êðèïòîãðàôèè. — Ì.: Ôèçìàòëèò, 2012. — 280 ñ. 13. Ò å ð å ù å í ê î À . Í . Îïòèìèçàöèÿ ìåòîäà Ìîíòãîìåðè çà ñ÷åò èñïîëüçîâàíèÿ îäíîñëîâíûõ óìíîæåíèé ïî îäíîñëîâíîìó ìîäóëþ // Êîìïüþòåð. ìàòåìàòèêà. — 2010. — ¹ 1. — Ñ. 73–82. 14. × å ð â ÿ ê î â Í . È . Îðãàíèçàöèÿ àðèôìåòè÷åñêèõ ðàñøèðèòåëåé â ìèêðîïðîöåññîðíûõ ñèñ- òåìàõ, áàçèðóþùèõñÿ íà ìíîæåñòâåííîì ïðåäñòàâëåíèè èíôîðìàöèè // Óïð. ñèñòåìû è ìàøè- íû. — 1987. — ¹ 1. — Ñ. 26–29. 15. × å ð â ÿ ê î â Í . È . Ìåòîäû è ïðèíöèïû ïîñòðîåíèÿ ìîäóëÿðíûõ íåéðîêîìïüþòåðîâ // 50 ëåò ìîäóëÿðíîé àðèôìåòèêå: Cá. òð. Þáèë. Ìåæäóíàð. íàó÷.-òåõí. êîíô. — Ì.: ÎÀÎ «Àíãñòðåì», ÌÈÝÒ. — 2006. — Ñ. 239–249. 16. × å ð â ÿ ê î â Í . È . Ðåàëèçàöèÿ âûñîêîýôôåêòèâíîé ìîäóëÿðíîé öèôðîâîé îáðàáîòêè ñèãíà- ëîâ íà îñíîâå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì // Íåéðîêîìïüþòåðû: ðàçðà- áîòêà, ïðèìåíåíèå. — 2006. — ¹ 10. — Ñ. 24–36. 17. Pat. WO 2013/176852 A1. Residue number arithmetic logic unit / E. Olsen. — Publ. 28.11.13. 18. × å ð â ÿ ê î â Í . È . , Ë à â ð è í å í ê î È . Í . Ìîäóëÿðíûå ìåòîäû è àëãîðèòìû äåëåíèÿ íà îñíîâå ñïóñêà Ôåðìà è èòåðàöèé Íüþòîíà // Èíôîêîììóíèêàö. òåõíîëîãèè. — 2009. — 7, ¹ 4. — Ñ. 9–12. 19. × å ð â ÿ ê î â Í . È . , Ë à â ð è í å í ê î È . Í . , Ë à â ð è í å í ê î Ñ . Â . , Ì å ç å í ö å â à Î . Ñ . Ìåòîäû è àëãîðèòìû îêðóãëåíèÿ, ìàñøòàáèðîâàíèÿ è äåëåíèÿ ìîäóëÿðíûõ ÷èñåë // 50 ëåò ìî- äóëÿðíîé àðèôìåòèêå: Cá. òð. Þáèë. Ìåæäóíàð. íàó÷.-òåõí. êîíô. — Ì.: ÎÀÎ «Àíãñòðåì», ÌÈÝÒ. — 2006. — Ñ. 291–310. 20. × å ð â ÿ ê î â Í . È . Ìåòîäû, àëãîðèòìû è òåõíè÷åñêàÿ ðåàëèçàöèÿ îñíîâíûõ ïðîáëåìíûõ îïåðàöèé, âûïîëíÿåìûõ â ñèñòåìå îñòàòî÷íûõ êëàññîâ // Èíôîêîììóíèêàö. òåõíîëîãèè. — 2011. — 9, ¹ 4. — Ñ. 4–12. 21. C h i n - C h e n C h a n g , Y e u - P o n g L a i . A division algorithm for residue numbers // Appl. Math. and Comput. — 2006. — 172, N 1. — P. 368–378. 22. Ñ è í ü ê î â Ì . Â . , Ñ è í ü ê î â à Ò . Â . , Ô å ä î ð å í ê î À . Â . , × à ï î ð À . À . Íåòðàäèöè- îííàÿ ñèñòåìà îñòàòî÷íûõ êëàññîâ è åå îñíîâîïîëîæíèê È.ß. Àêóøñêèé. — www.icfcst.kiev.ua/Symposium/Proceedings2/Sinkov.rtf. 23. Î í è ù å í ê î Ñ . Ì . Ïðèìåíåíèå ãèïåðêîìïëåêñíûõ ÷èñåë â òåîðèè èíåðöèàëüíîé íàâèãà- öèè. Àâòîíîìíûå ñèñòåìû. — Êèåâ: Íàóê. äóìêà, 1983. — 208 ñ. 24. Ï ó õ î â Ã . Å . , Å â ä î ê è ì î â Â . Ô . , Ñ è í ü ê î â Ì . Â . Ðàçðÿäíî-àíàëîãîâûå âû÷èñëè- òåëüíûå ñèñòåìû. — Ì.: Ñîâ. ðàäèî, 1978. — 256 ñ. 25. Y o u n e s D . , S t e f f a n P . A comparative study on different moduli sets in residue number system // Intern. Conf. on Computer Systems and Industrial Informatics (ICCSII). — 2012. — P. 1–6. 26. Y o u n e s D . , S t e f f a n P . Efficient image processing application using residue number system // Proc. of the 20th Intern. Conf. on Mixed Design of Integrated Circuits and Systems (MIXDES). — 2013. — P. 468–472. 27. Ê í ó ò Ä . Èñêóññòâî ïðîãðàììèðîâàíèÿ. — Ì.: Âèëüÿìñ, 2003. — T. 2. — 832 ñ. 28. O m o n d i A . , P r e m k u m a r B . Residue number systems: Theory and implementation. — London: Imperial College Press, 2007. — 296 p. 29. × å ð â ÿ ê î â Í . È . , Ë ÿ õ î â Ï . À . Ìåòîä îïðåäåëåíèÿ çíàêà ÷èñëà â ñèñòåìå îñòàòî÷íûõ êëàññîâ íà îñíîâå ïðèáëèæåííûõ âû÷èñëåíèé // Íåéðîêîìïüþòåðû: ðàçðàáîòêà, ïðèìåíåíèå. — 2012. — ¹ 12. — Ñ. 56–64. 30. × å ð â ÿ ê î â Í . È . , Á à á å í ê î Ì . Ã . , Ë ÿ õ î â Ï . À . , Ë à â ð è í å í ê î È . Í . Ïðèáëè- æåííûé ìåòîä îïðåäåëåíèÿ çíàêà ÷èñëà â ñèñòåìå îñòàòî÷íûõ êëàññîâ è åãî òåõíè÷åñêàÿ ðåà- ëèçàöèÿ // Íàó÷.-òåõí. âåäîìîñòè Ñ.-Ïåòåðáóðã. ãîñ. ïîëèòåõ. óí-òà. Èíôîðìàòèêà. Òåëåêîì- ìóíèêàöèè. Óïðàâëåíèå. — 2013. — ¹ 176. — Ñ. 131–141. Ïîñòóïèëà 01.08.2013 186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6

Приближенный метод сравнения модулярных чисел и его применение для деления чисел в системе остаточных классов

Institution

Ähnliche Einträge