Cover Image

Об одном подходе к выполнению сложных операций в системе остаточных классов

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

Full description

Saved in:
Bibliographic Details
Published in:Электронное моделирование
Date:2015
Main Author: Полисский, Ю.Д.
Format: Article
Language:Russian
Published: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2015
Subjects:
Математическое моделирование и вычислительные методы
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/101163
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Об одном подходе к выполнению сложных операций в системе остаточных классов / Ю.Д. Полисский // Электронное моделирование. — 2015. — Т. 37, № 5. — С. 39-48. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1860259083391598592
author Полисский, Ю.Д.
author_facet Полисский, Ю.Д.
citation_txt Об одном подходе к выполнению сложных операций в системе остаточных классов / Ю.Д. Полисский // Электронное моделирование. — 2015. — Т. 37, № 5. — С. 39-48. — Бібліогр.: 5 назв. — рос.
collection DSpace DC
container_title Электронное моделирование
description Рассмотрен способ увеличения быстродействия операции определения принадлежности числа данной половине диапазона в системе остаточных классов. Предложено переупорядочение модулей на основе предварительной оценки вариантов упорядочения и выбора наилучшего варианта упорядочения на данной итерации. Розглянуто спосіб збільшення швидкодії операції визначення приналежності числа даній половині діапазону в системі залишкових класів. Запропоновано переупорядковування модулів на основі попередньої оцінки варіантів впорядкування і вибору найкращого варіанта впорядкування на даній ітерації. A method is considered for increasing the speed of response of the operation of determining a number belonging to the given half of range in the system of residual classes. The approach is based on reordering of modules with the preliminary estimation of variants of ordering and choice of the most preferable variant of ordering on this iteration. Thus the estimation of the variant of ordering consists in the subtraction from every remainder of a certain constant and in the count of quantity of the obtained zero residuals. The variant with the greatest quantity of modules, which residuals are equal to zero, are most preferable.
first_indexed 2025-12-07T18:52:57Z
format Article
fulltext ÓÄÊ 681.04 Þ.Ä. Ïîëèññêèé, êàíä. òåõí. íàóê, ÍÈÈ àâòîìàòèçàöèè ÷åðíîé ìåòàëëóðãèè (Óêðàèíà, 49000, Äíåïðîïåòðîâñê, òåë. (056) 7443365, e-mail: polissky@mail.ru) Îá îäíîì ïîäõîäå ê âûïîëíåíèþ ñëîæíûõ îïåðàöèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ Ðàññìîòðåí ñïîñîá óâåëè÷åíèÿ áûñòðîäåéñòâèÿ îïåðàöèè îïðåäåëåíèÿ ïðèíàäëåæíîñòè ÷èñëà äàííîé ïîëîâèíå äèàïàçîíà â ñèñòåìå îñòàòî÷íûõ êëàññîâ. Ïðåäëîæåíî ïåðåóïî- ðÿäî÷åíèå ìîäóëåé íà îñíîâå ïðåäâàðèòåëüíîé îöåíêè âàðèàíòîâ óïîðÿäî÷åíèÿ è âûáîðà íàèëó÷øåãî âàðèàíòà óïîðÿäî÷åíèÿ íà äàííîé èòåðàöèè. Ðîçãëÿíóòî ñïîñ³á çá³ëüøåííÿ øâèäêî䳿 îïåðàö³¿ âèçíà÷åííÿ ïðèíàëåæíîñò³ ÷èñëà äàí³é ïîëîâèí³ ä³àïàçîíó â ñèñòåì³ çàëèøêîâèõ êëàñ³â. Çàïðîïîíîâàíî ïåðåóïîðÿäêîâóâàííÿ ìîäóë³â íà îñíîâ³ ïîïåðåäíüî¿ îö³íêè âàð³àíò³â âïîðÿäêóâàííÿ ³ âèáîðó íàéêðàùîãî âàð³àíòà âïîðÿäêóâàííÿ íà äàí³é ³òåðàö³¿. Ê ë þ ÷ å â û å ñ ë î â à: îñòàòî÷íûå êëàññû, ñëîæíûå îïåðàöèè, ìîäóëè, äèàïàçîí. Ñîçäàíèå ýôôåêòèâíûõ âû÷èñëèòåëüíûõ ñòðóêòóð ñâÿçàíî ñ ïàðàëëåëü- íîé îáðàáîòêîé äàííûõ ñèñòåìàìè ñ íåòðàäèöèîííûìè ñïîñîáàìè êîäè- ðîâàíèÿ èíôîðìàöèè, â ÷àñòíîñòè ñèñòåìîé ñ÷èñëåíèÿ â îñòàòî÷íûõ êëàññàõ (ÑÎÊ) [1]. Ê äîñòîèíñòâàì òàêîãî ïðåäñòàâëåíèÿ ÷èñåë îòíîñèò- ñÿ âçàèìîíåçàâèñèìîñòü ðàçðÿäîâ ÷èñåë è âîçìîæíîñòü èõ ïàðàëëåëüíîé îáðàáîòêè, ìàëîðàçðÿäíîñòü îñòàòêîâ, âûñîêàÿ òî÷íîñòü, ñïîñîáíîñòü ñèñòåìû ê ñàìîêîððåêöèè. ÑÎÊ íàçûâàåòñÿ ñèñòåìà ñ÷èñëåíèÿ, â êîòîðîé ïðîèçâîëüíîå ÷èñëî N ïðåäñòàâëÿåòñÿ â âèäå íàáîðà íàèìåíüøèõ íåîòðèöàòåëüíûõ îñòàòêîâ ïî ìîäóëÿì m m mn1 2, ,..., , ò.å. N n� ( , ,..., )� � �1 2 . Çäåñü � i iN m� (mod ). Ïðè ýòîì, åñëè ÷èñëà mi — âçàèìíî ïðîñòûå, òî òàêîìó ïðåäñòàâëåíèþ ñîîò- âåòñòâóåò òîëüêî îäíî ÷èñëî N äèàïàçîíà [ , )0 M , ãäå M m m mn� 1 2 ... . Îñíîâíûå àðèôìåòè÷åñêèå îïåðàöèè â ÑÎÊ äåëÿòñÿ íà ìîäóëüíûå, — âûïîëíÿåìûå ïàðàëëåëüíî è íåçàâèñèìî íàä îòäåëüíûìè öèôðàìè ÷èñåë, è íåìîäóëüíûå, èëè ñëîæíûå, — äëÿ âûïîëíåíèÿ êîòîðûõ íåîáõîäèìî çíàíèå öèôð îïåðàíäîâ ïî âñåì ðàçðÿäàì. Ìîäóëüíûå îïåðàöèè — ýòî àðèôìåòè÷åñêèå îïåðàöèè ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿ, âûïîëíÿåìûå íàä îñòàòêàìè íåçàâèñèìî îäíà îò äðóãîé ïî ïðîñòûì ïðàâèëàì. ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 39 � Þ.Ä. Ïîëèññêèé, 2015 Ê íåìîäóëüíûì îïåðàöèÿì îòíîñÿòñÿ, â ÷àñòíîñòè, îïðåäåëåíèå ïðè- íàäëåæíîñòè ÷èñëà äàííîé ïîëîâèíå äèàïàçîíà, äåëåíèå íà äâà, îïðåäå- ëåíèå ïðèíàäëåæíîñòè ÷èñëà äàííîìó èíòåðâàëó, äåëåíèå íà ÷èñëî, êðàòíîå îäíîìó èç ìîäóëåé, ñðàâíåíèå ÷èñåë, ïåðåïîëíåíèå äèàïàçîíà ïðè ñëîæåíèè ïàðû ÷èñåë, ïåðåïîëíåíèå äèàïàçîíà è îïðåäåëåíèå ðàíãà ÷èñëà ïðè óìíî- æåíèè ïàðû ÷èñåë, ðàñøèðåíèå äèàïàçîíà ïðåäñòàâëåíèÿ ÷èñåë. Ìåæäó íåìîäóëüíûìè îïåðàöèÿìè ñóùåñòâóþò îïðåäåëåííûå âçàè- ìîñâÿçè [2, 3]. Ïîýòîìó, ïîëó÷èâ ðåøåíèå îäíîé èç îïåðàöèé, ìîæíî íàéòè ðåøåíèÿ îñòàëüíûõ. Âûáîð áàçîâîé îïåðàöèè çàâèñèò îò ðåçóëü- òàòîâ èññëåäîâàíèé áûñòðîäåéñòâèÿ è ñëîæíîñòè íåìîäóëüíûõ îïåðàöèé ÑÎÊ.  íàñòîÿùåå âðåìÿ ïîëó÷åíî ýôôåêòèâíîå ðåøåíèå ïî âûïîëíåíèþ îïåðàöèè îïðåäåëåíèÿ ïðèíàäëåæíîñòè ÷èñëà äàííîé ïîëîâèíå äèàïàçîíà [4], îñíîâàííîå íà îäíîâðåìåííîì ïðåäñòàâëåíèè ÷èñåë â ïðÿìîì è îáðàò- íîì êîäàõ ñ âûáîðîì àêòèâíîãî ïðåäñòàâëåíèÿ íà êàæäîé èòåðàöèè.  ñâÿçè ñ ýòèì ïðåäñòàâëÿåòñÿ öåëåñîîáðàçíûì ïðèíÿòü áàçîâîé îïåðàöèþ îïðåäåëåíèÿ ïðèíàäëåæíîñòè ÷èñëà äàííîé ïîëîâèíå äèàïàçîíà. Ïîñòàíîâêà çàäà÷è è åå ðåøåíèå. Ïóñòü mn �2. Áóäåì îòëè÷àòü ÷èñëà ïåðâîé R1è âòîðîé R2 ïîëîâèíû äèàïàçîíà: N R N M R M N M � � � � � � 1 0 2 2 2 , / , , / . Ïóñòü ñèñòåìîé îñíîâàíèé ïîëèàäè÷åñêîãî êîäà ÿâëÿåòñÿ ñèñòåìà m m mn1 2 2, ,..., � . Òîãäà ÷èñëî N â ïîëèàäè÷åñêîì êîäå èìååò âèä N m m m m m m mi i n n n� � � � � � �� � � 1 2 1 1 2 1 1 1 2 2... ... ... ... m m mn1 2 1... � , ãäå 0 1� � � i im .  ñîîòâåòñòâèè ñ [5] êðèòåðèåì ïðèíàäëåæíîñòè ÷èñëà äàííîé ïîëîâèíå äèàïàçîíà ÿâëÿåòñÿ çíà÷åíèå n : N R R n n � � � � 1 0 2 1 , , , . Îïðåäåëåíèå n îñóùåñòâëÿåòñÿ ïîñðåäñòâîì ïîñëåäîâàòåëüíîãî âû÷èòàíèÿ èç ÷èñëà N n� ( , ,..., )� � �1 2 , � i iN m� (mod ) ñëàãàåìûõ ýòîãî ÷èñëà â ïîëèàäè÷åñêîì êîäå, íà÷èíàÿ ñ ìîäóëÿ m1, äî ïîëó÷åíèÿ ~ N � � ( , , ..., , ~ )0 0 0 � n . Ïðè ýòîì � i t tm m m t� � � �� � � �� � ~ ... (mod ) 1 2 1 , à êîíñòàíòû âû÷è- òàíèÿ � s t tm m m s� �( ... ) (mod ) 1 2 1 , s t t n� �, , ...,1 . Ïðè ôèêñèðîâàííîé óïî- ðÿäî÷åííîñòè m m mn1 2 2, ,..., � ìîæíî ñîñòàâèòü òàáëèöû ïðåäâàðèòåëüíî ðàññ÷èòàííûõ êîíñòàíò, ÷òî ñîêðàòèò âðåìÿ îïðåäåëåíèÿ i . Ñðåäè ÷èñåë äèàïàçîíà [ , )0 M èìåþòñÿ ÷èñëà, êðàòíûå îäíîìó èëè íåñêîëüêèì ìîäóëÿì. Êîëè÷åñòâî ÷èñåë, êðàòíûõ ìîäóëþ mi , i n�1 2, , ..., , Þ.Ä. Ïîëèññêèé 40 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 ñîñòàâëÿåò K M mi i� / . Íàïðèìåð, â ñèñòåìå ìîäóëåé m1 13� , m2 7� , m3 11� , m4 5� , m5 3� , m6 2� êîëè÷åñòâî ÷èñåë, äëÿ êîòîðûõ îäíî èëè íåñêîëüêî çíà÷åíèé � i �0, i n� , K K K K K K� � � � � �1 2 3 4 5 25346 èç 30030 ÷èñåë äèàïàçîíà.  ñâÿçè ñ òàêèì çíà÷èòåëüíûì êîëè÷åñòâîì ÷èñåë (84% äèà- ïàçîíà), äëÿ êîòîðûõ � i �0, i n� , ñ öåëüþ ñîêðàùåíèÿ äëèòåëüíîñòè îïå- ðàöèè îïðåäåëåíèÿ ïðèíàäëåæíîñòè ÷èñëà äàííîé ïîëîâèíå äèàïàçîíà ïðåäñòàâëÿåòñÿ öåëåñîîáðàçíûì ñëåäóþùèé ïîäõîä. Ïîðÿäîê ìîäóëåé, êðîìå mn �2, íå ôèêñèðóåòñÿ. Ïðè ýòîì íà êàæäîé èòåðàöèè îñóùåñòâëÿåòñÿ ïåðåóïîðÿäî÷åíèå ìîäóëåé òàêèì îáðàçîì, ÷òîáû èõ ïîñëåäîâàòåëüíîñòü íà÷èíàëàñü ñ ìîäóëåé, äëÿ êîòîðûõ � i �0. Âûèãðûø âî âðåìåíè äîñòèãàåòñÿ â ðåçóëüòàòå òîãî, ÷òî ïî ýòèì ìîäóëÿì íå òðåáóåòñÿ îïðåäåëåíèÿ ïîçèöèîííûõ õàðàêòåðèñòèê, òàê êàê îíè ðàâíû íóëþ. Ðàññìîòðèì ðàáîòó àëãîðèòìà (ñì. ðèñóíîê) íà ïðèìåðå îïðåäåëåíèÿ ïðèíàäëåæíîñòè ïåðâîé èëè âòîðîé ïîëîâèíå äèàïàçîíà M � � � �13 7 11 � � � �5 3 2 30030 ÷èñëà N � �17893 5 1 7 3 1 1( , , , , , ) äëÿ ñèñòåìû ìîäóëåé m1 13� , m2 7� , m3 11� , m4 5� , m5 3� , m6 2� .  òàáë. 1 ïðèâåäåíû âàðèàíòû óïîðÿäî÷åíèÿ ìîäóëåé íà ïåðâîé èòå- ðàöèè, ãäå Ï — óïîðÿäî÷åííîñòü ìîäóëåé. Äëÿ êàæäîãî âàðèàíòà â ïåðâîé ñòðîêå — èñïûòóåìîå óìåíüøàåìîå ÷èñëî è åãî ïðåäñòàâëåíèå â ñèñòåìå Îá îäíîì ïîäõîäå ê âûïîëíåíèþ ñëîæíûõ îïåðàöèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 41 21 31 41 22 32 42 2i 3i 4i 2n 3n 4n 1  à ð è à í ò û 61 71 62 72 6i 7i 6n 7n 5 8 Íåò ÍåòÍåò Íåò Äà Äà Äà Äà Áëîê-ñõåìà àëãîðèòìà: 1 — íà÷àëî; 2 — îáðàçîâàíèå ÷èñëà N Ni i� � � , i n� �1 2 1, ,..., ; 3 — ïåðåóïîðÿäî÷åíèå ìîäóëåé â êàæäîì èç N i, i n� �1 2 1, ,..., ; 4 — ïîäñ÷åò êîëè÷åñòâà S i íóëåâûõ îñòàòêîâ â êàæäîì èç N i, i n� �1 2 1, ,..., ; 5 — îïðåäåëåíèå S S imax max{ }� , i � � �1 2 1, ,..., n ; 6 — ñðàâíåíèå S i ñ S max, âûõîä «äà» ïðè S Si � max; 7 — âêëþ÷åíèå i-ãî âàðèàíòà óïðÿäî÷åíèÿ ìîäóëåé â íàáîð âàðèàíòîâ äëÿ ñëåäóþùåé èòåðàöèè; 8 — êîíåö ìîäóëåé m1 13� , m2 7� , m3 11� , m4 5� , m5 3� , m6 2� . Âî âòîðîé ñòðîêå — âû÷èòàåìûé îñòàòîê è åãî ïðåäñòàâëåíèå â òîé æå ñèñòåìå ìîäóëåé.  òðåòüåé ñòðîêå — ðåçóëüòàò âû÷èòàíèÿ è åãî ïðåäñòàâëåíèå â òîé æå ñèñòåìå ìîäóëåé.  ÷åòâåðòîé ñòðîêå — íîâàÿ óïîðÿäî÷åííîñòü ìîäóëåé. Êàê âèäíî èç òàáë. 1, äëÿ âòîðîé èòåðàöèè öåëåñîîáðàçíî âûáðàòü âàðèàíò 2, �21 7 3 13 11 5 2 0 0 1 2 3 4 5 6 1 2 3 � � � � � � � � � m m m m m m, , , , , ~ , ~ , ~� � � � � � � � � � �4 6 2 04 5 6, ~ , ~ , ~� � � , âàðèàíò 3, �31 11 3 13 7 5 2 0 0 1 2 3 4 5 6 1 2 3 � � � � � � � � � m m m m m m, , , , , ~ , ~ , ~� � � � � � � � � � �11 1 1 04 5 6, ~ , ~ , ~� � � Þ.Ä. Ïîëèññêèé 42 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 Âàðèàíò Ï ×èñëî m6 2� m5 3� m4 5� m3 11� m2 7� m1 13� 1 Ï01 17 893 1 1 3 7 1 5 –5 1 2 0 5 5 5 17 888 0 2 3 2 3 0 Ï11 m6 2� m5 3� m4 5� m3 11� m2 7� m1 13� 2 17 893 1 1 3 7 1 5 –1 1 1 1 1 1 1 17 892 0 0 2 6 0 4 Ï21 m6 2� m5 5� m4 11� m3 13� m2 3� m1 7� 3 17 893 1 1 3 7 1 5 –7 1 1 2 7 0 7 17 886 0 0 1 0 1 11 Ï31 m6 2� m5 5� m4 7� m3 13� m2 3� m1 11� 4 17 893 1 1 3 7 1 5 –3 1 0 3 3 3 3 17 890 0 1 0 4 5 2 Ï41 m6 2� m5 3� m4 11� m3 7� m2 13� m1 5� 5 17 893 1 1 3 7 1 5 –1 1 1 1 1 1 1 17 892 0 0 2 6 0 4 Ï51 m6 2� m5 5� m4 11� m3 13� m2 3� m1 7� Òàáëèöà 1 èëè âàðèàíò 5, �51 7 3 13 11 5 2 0 0 1 2 3 4 5 6 1 2 3 � � � � � � � � � m m m m m m, , , , , ~ , ~ , ~� � � � � � � � � � �4 6 2 04 5 6, ~ , ~ , ~� � � , òàê êàê îíè äàþò áîëüøåå êîëè÷åñòâî íóëåé. Ïîñêîëüêó âàðèàíòû 2 è 5 ñîâïàäàþò, âûáèðàåì âàðèàíòû 2 è 3 óïîðÿäî÷åíèÿ ìîäóëåé. Ïåðåõîäèì ê òàáë. 2, ãäå áëîê À îçíà÷àåò ðåçóëüòàòû âòîðîãî âàðèàíòà óïîðÿäî÷åíèÿ ìîäóëåé, ïîëó÷åííûå íà ïåðâîé èòåðàöèè: �21 7 3 13 11 5 2 0 0 1 2 3 4 5 6 1 2 3 � � � � � � � � � m m m m m m, , , , , ~ , ~ , ~� � � � � � � � � � �4 6 2 04 5 6, ~ , ~ , ~� � � . Á ë î ê À. Ïî âàðèàíòó 1 óïîðÿäî÷åíèÿ ìîäóëåé âòîðîé èòåðàöèè äëÿ m3 13� � 3 3 1 2 3 4 7 3 13 7� � � � � � �� � � �� � � ~ ( ) ( ) (mod ) m m m . Êîíñòàíòû âû÷èòàíèÿ: � � � � � � 3 1 2 7 7 3 147m m , � �3 3 13 4� � �(mod )m , � �5 5 5 2� � �(mod )m , � �4 4 11 4� � �(mod )m , � �6 6 2 1� � �(mod )m . Îá îäíîì ïîäõîäå ê âûïîëíåíèþ ñëîæíûõ îïåðàöèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 43 Âàðèàíò Áëîê À ×èñëî m6 2� m5 5� m4 11� m3 13� m2 3� m1 7� 1 Ï21 17 892 0 2 6 4 0 0 –147 1 2 4 4 — — 17 745 1 0 2 0 0 0 Ï12À m6 2� m5 11� m4 5� m3 13� m2 3� m1 7� 2 Ï21 17 892 0 2 6 4 0 0 –105 1 0 6 1 — — 17 787 1 2 0 3 0 0 Ï22À m6 2� m5 5� m4 13� m3 11� m2 3� m1 7� 3 Ï21 17 892 0 2 6 4 0 0 – 42 0 2 9 3 — — 17 850 0 0 8 1 0 0 Ï32À m6 2� m5 11� m4 13� m3 5� m2 3� m1 7� Òàáëèöà 2 Ïî âàðèàíòó 2 óïîðÿäî÷åíèÿ ìîäóëåé âòîðîé èòåðàöèè äëÿ m4 11� � 4 4 1 2 4 6 7 3 11 5� � � � � � �� � � �� � � ~ ( ) ( ) (mod ) m m m . Êîíñòàíòû âû÷èòàíèÿ: � � � � � � 4 1 2 5 7 3 105m m , � �3 3 13 1� � �(mod )m , � �5 5 5 0� � �(mod )m , � �4 4 11 6� � �(mod )m , � �6 6 2 1� � �(mod )m . Ïî âàðèàíòó 3 óïîðÿäî÷åíèÿ ìîäóëåé âòîðîé èòåðàöèè äëÿ m5 5� � 5 5 1 2 5 2 7 3 5 2� � � � � � �� � � �� � � ~ ( ) ( ) (mod ) m m m . Êîíñòàíòû âû÷èòàíèÿ: � � � � � � 5 1 2 2 7 3 42m m , � �3 3 13 3� � �(mod )m , � �5 5 5 2� � �(mod )m , � �4 4 11 9� � �(mod )m , � �6 6 2 0� � �(mod )m . Þ.Ä. Ïîëèññêèé 44 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 Âàðèàíò Áëîê  ×èñëî m6 2� m5 5� m4 7� m3 13� m2 3� m1 11� 1 Ï31 17 886 0 1 1 11 0 0 –297 1 2 3 11 — — 17 589 1 4 5 0 0 0 Ï12 Á m6 2� m5 5� m4 7� m3 13� m2 3� m1 11� 2 Ï31 17 886 0 1 1 11 0 0 –99 1 4 1 8 — — 17 787 1 2 0 3 0 0 Ï22 Á m6 2� m5 5� m4 13� m3 7� m2 3� m1 11� 3 Ï31 17 886 0 1 1 11 0 0 –66 0 1 3 1 — — 17 820 0 0 5 10 0 0 Ï32 Á m6 2� m5 7� m4 13� m3 5� m2 3� m1 11� Òàáëèöà 3  òàáë. 3 áëîê Á îçíà÷àåò ðåçóëüòàòû òðåòüåãî âàðèàíòà óïîðÿäî÷åíèÿ ìîäóëåé, ïîëó÷åííûå íà ïåðâîé èòåðàöèè: �31 11 3 13 7 5 2 0 0 1 2 3 4 5 6 1 2 3 � � � � � � � � � m m m m m m, , , , , ~ , ~ , ~� � � � � � � � � � �11 1 1 04 5 6, ~ , ~ , ~� � � . Á ë î ê Á. Ïî âàðèàíòó 1 óïîðÿäî÷åíèÿ ìîäóëåé âòîðîé èòåðàöèè äëÿ m3 13� � 3 3 1 2 3 11 11 3 13 9� � � � � � �� � � �� � � ~ ( ) ( ) (mod ) m m m . Êîíñòàíòû âû÷èòàíèÿ: � � � � � � 3 1 2 9 11 3 297m m , � �3 3 13 11� � �(mod )m , � �5 5 5 2� � �(mod )m , � �4 4 7 3� � �(mod )m , � �6 6 2 1� � �(mod )m . Ïî âàðèàíòó 2 óïîðÿäî÷åíèÿ ìîäóëåé âòîðîé èòåðàöèè äëÿ m4 7� � 4 4 1 2 4 1 11 3 7 3� � � � � � �� � � �� � � ~ ( ) ( ) (mod ) m m m . Êîíñòàíòû âû÷èòàíèÿ: � � � � � � 3 1 2 3 11 3 99m m , � �3 3 13 8� � �(mod )m , � �5 5 5 4� � �(mod )m , � �4 4 7 1� � �(mod )m , � �6 6 2 1� � �(mod )m . Ïî âàðèàíòó 3 óïîðÿäî÷åíèÿ ìîäóëåé âòîðîé èòåðàöèè äëÿ m5 5� � 5 5 1 2 5 1 11 3 5 2� � � � � � �� � � �� � � ~ ( ) ( ) (mod ) m m m . Êîíñòàíòû âû÷èòàíèÿ: � � � � � � 5 1 2 2 11 3 66m m , � �3 3 13 1� � �(mod )m , � �5 5 5 1� � �(mod )m , � �4 4 7 3� � �(mod )m , � �6 6 2 0� � �(mod )m .  ñîîòâåòñòâèè ñ òàáë. 2 èìåþòñÿ øåñòü âàðèàíòîâ óïîðÿäî÷åíèÿ ìî- äóëåé: �12 7 3 13 5 11 2 0 1 2 3 4 5 6 1 2 Áëîê À � � � � � � � � m m m m m m, , , , , ~ , ~� � � � � � � � � � �0 0 0 2 13 4 5 6, ~ , ~ , ~ , ~� � � � , Îá îäíîì ïîäõîäå ê âûïîëíåíèþ ñëîæíûõ îïåðàöèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 45 �22 7 3 11 13 5 2 0 1 2 3 4 5 6 1 2 Áëîê À � � � � � � � � m m m m m m, , , , , ~ , ~� � � � � � � � � � �0 0 3 2 13 4 5 6, ~ , ~ , ~ , ~� � � � , ��2 7 3 5 13 11 2 0 1 2 3 4 5 6 1 2 Áëîê À � � � � � � � � m m m m m m, , , , , ~ , ~� � � � � � � � � � �0 0 1 8 03 4 5 6, ~ , ~ , ~ , ~� � � � , ��2 11 3 13 7 5 2 0 1 2 3 4 5 6 1 2 Áëîê Á � � � � � � � � m m m m m m, , , , , ~ , ~� � � � � � � � � � �0 0 5 4 13 4 5 6, ~ , ~ , ~ , ~� � � � , �22 11 3 7 13 5 2 0 1 2 3 4 5 6 1 2 Áëîê Á � � � � � � � � m m m m m m, , , , , ~ , ~� � � � � � � � � � �0 0 3 2 13 4 5 6, ~ , ~ , ~ , ~� � � � , ��2 11 3 5 13 7 2 0 1 2 3 4 5 6 1 2 Áëîê Á � � � � � � � � m m m m m m, , , , , ~ , ~� � � � � � � � � � �0 0 12 5 03 4 5 6, ~ , ~ , ~ , ~� � � � . Äëÿ òðåòüåé èòåðàöèè öåëåñîîáðàçíî âûáðàòü âàðèàíò 1 óïîðÿäî÷åíèÿ ìîäóëåé íà âòîðîé èòåðàöèè áëîêà À: �12 7 3 13 5 11 2 0 1 2 3 4 5 6 1 2 Áëîê À � � � � � � � � m m m m m m, , , , , ~ , ~� � � � � � � � � � �0 0 0 2 13 4 5 6, ~ , ~ , ~ , ~� � � � , òàê êàê îí äàåò áîëüøåå êîëè÷åñòâî íóëåé.  òàáë. 4 ïðèâåäåí âàðèàíò óïîðÿäî÷åíèÿ ìîäóëåé íà òðåòüåé èòåðà- öèè, ãäå äëÿ m5 11� � 5 5 1 2 3 4 5 2 7 3 13 5 11� � � � � � � � �� � � �� � ~ ( ) ( ) ( ) ( ) (mod m m m m m ) �2 . Êîíñòàíòû âû÷èòàíèÿ: � � � � � � � � 5 1 2 3 4 2 7 3 13 5 2730m m m m , � �5 5 11 2� � �(mod )m , � �6 6 2 0� � �(mod )m . Äëÿ m6 2� � 6 6 1 2 3 4 5 1 7 3 13 5 11 � � � � � � � � � �� � � �� ~ ( ) ( ) ( ) ( ) ( ) (m m m m m m od )m6 2 1� � . Þ.Ä. Ïîëèññêèé 46 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5 Âàðèàíò Áëîê À ×èñëî m6 2� m5 11� m4 5� m3 13� m2 3� m1 7� 1 Ï12 17 745 1 2 0 0 0 0 –2 730 0 2 — — — — 15 015 1 0 0 0 0 0 Ï13 m6 2� m5 11� m4 5� m3 13� m2 3� m1 7� Òàáëèöà 4 Ïîñêîëüêó 6 1� , ÷èñëî N � �17893 5 1 7 3 1 1( , , , , , ) â èñõîäíîé ñèñòåìå ìîäó- ëåé m1 13� , m2 7� , m3 11� , m4 5� , m5 3� , m6 2� ïðèíàäëåæèò âòîðîé ïîëî- âèíå äèàïàçîíà [ , )0 M . Äåéñòâèòåëüíî, M N M/2 15015 17893� � � � � �30030. Ðåçóëüòàò ïîëó÷åí çà òðè èòåðàöèè. Êàê óïîìÿíóòî âûøå, âûèãðûø âî âðåìåíè îáóñëîâëåí òåì, ÷òî ïî ìîäóëÿì, îñòàòêè ïî êîòîðûì ðàâíû íóëþ, íå òðåáóåòñÿ îïðåäåëåíèÿ ïîçè- öèîííûõ õàðàêòåðèñòèê, òàê êàê îíè ðàâíû íóëþ. Îäíàêî äëÿ ïîëó÷åíèÿ êîíñòàíò âû÷èòàíèÿ ïî îñòàëüíûì ìîäóëÿì âìåñòî âûáîðêè èç òàáëèö ïðåäâàðèòåëüíî ðàññ÷èòàííûõ êîíñòàíò íåîáõîäèìî âûïîëíåíèå ïðèâåäåí- íûõ âû÷èñëåíèé � t t tm m m t� � � �� � � �� �1 2 1... (mod ) è � s t tm m m s� �( ... )(mod ) 1 2 1 , s t t n� �, , ...,1 . Ïîýòîìó ïðåäëîæåííûé ïîäõîä ñëåäóåò ðàññìàòðèâàòü êàê îäíî èç íàïðàâëåíèé óñêîðåíèÿ îïðåäåëåíèÿ ïðèíàäëåæíîñòè ÷èñëà äàí- íîé ïîëîâèíå äèàïàçîíà, êîòîðîå òðåáóåò äàëüíåéøèõ èññëåäîâàíèé. Âûâîäû Ìåæäó ñëîæíûìè îïåðàöèÿìè ñèñòåìû îñòàòî÷íûõ êëàññîâ ñóùåñòâóþò îïðåäåëåííûå âçàèìîñâÿçè, ïîýòîìó, ïîëó÷èâ ðåøåíèå îäíîé èç îïåðà- öèé, ìîæíî íàéòè ðåøåíèÿ îñòàëüíûõ. Ïðåäëîæåííûé ïîäõîä ê óâåëè÷åíèþ áûñòðîäåéñòâèÿ îïåðàöèè îïðåäåëåíèÿ ïðèíàäëåæíîñòè ÷èñëà äàííîé ïîëî- âèíå äèàïàçîíà â ñèñòåìå îñòàòî÷íûõ êëàññîâ îñíîâàí íà ïåðåóïîðÿäî÷åíèè ìîäóëåé ñ ïðåäâàðèòåëüíîé îöåíêîé âàðèàíòîâ óïîðÿäî÷åíèÿ è âûáîðîì íàèáîëåå ïðåäïî÷òèòåëüíîãî âàðèàíòà óïîðÿäî÷åíèÿ íà äàííîé èòåðàöèè. Ïðåäñòàâëÿåòñÿ öåëåñîîáðàçíûì ïðèìåíèòü ïðåäëîæåííûé ïîäõîä â êà- ÷åñòâå íàïðàâëåíèÿ èññëåäîâàíèé äëÿ ïîëó÷åíèÿ ýôôåêòèâíûõ ðåøåíèé çàäà÷ âûïîëíåíèÿ íåìîäóëüíûõ îïåðàöèé. Ïîëó÷åííûå ðåçóëüòàòû ìîãóò áûòü èñïîëüçîâàíû äëÿ ðàçðàáîòêè ïàòåíòíîñïîñîáíûõ è íåñëîæíûõ ðå- øåíèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Aêóøñêèé È.ß., Þäèöêèé Ä.È. Ìàøèííàÿ àðèôìåòèêà â îñòàòî÷íûõ êëàññàõ.— Ì. : Ñîâ. ðàäèî, 1968. — 440 ñ. 2. Ïîëèññêèé Þ.Ä. Ôîðìèðîâàíèå ïîçèöèîííûõ õàðàêòåðèñòèê ïðè òàáëè÷íîé ðåàëè- çàöèè àëãîðèòìîâ ñèñòåìû îñòàòî÷íûõ êëàññîâ // Ñá. òð. êîíô. «Ìîäåëèðîâàíèå — 2008». Ò. 2. — Êèåâ: ÈÏÌÝ, 2008. — Ñ. 489—495. 3. Ïîëèññêèé Þ.Ä. Î âçàèìîñâÿçè íåìîäóëüíûõ îïåðàöèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ // Ìàòåìàòè÷íå ìîäåëþâàííÿ. — 2014. — ¹ 2 (31). — Ñ. 3—6. 4. Ïîëèññêèé Þ.Ä. Àëãîðèòì âûïîëíåíèÿ ñëîæíûõ îïåðàöèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ ñ ïîìîùüþ ïðåäñòàâëåíèÿ ÷èñåë â îáðàòíûõ êîäàõ // Ýëåêòðîí. ìîäåëèðîâà- íèå. — 2014. — 36, ¹ 4. — Ñ. 117—122. 5. Ïîëèññêèé Þ.Ä. Âûáîð êðèòåðèÿ ïðèíàäëåæíîñòè ÷èñëà äàííîé ïîëîâèíå äèàïàçîíà â ñèñòåìå îñòàòî÷íûõ êëàññîâ // Ïðîáëåìè ìàòåìàòè÷íîãî ìîäåëþâàííÿ. Ìàòåð³àëè íàóê.-ìåòîä. êîíô., 27—29 òðàâ. 2015 ð. — Äí³ïðîïåòðîâñüê, 2015. — Ñ. 91—92. Îá îäíîì ïîäõîäå ê âûïîëíåíèþ ñëîæíûõ îïåðàöèé â ñèñòåìå îñòàòî÷íûõ êëàññîâ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 5 47 Yu.D. Polissky ABOUT ONE APPROACH TO EXECUTION OF COMPLICATED OPERATIONS IN THE SYSTEM OF RESIDUAL CLASSES A method is considered for increasing the speed of response of the operation of determining a number belonging to the given half of range in the system of residual classes. The approach is based on reordering of modules with the preliminary estimation of variants of ordering and choice of the most preferable variant of ordering on this iteration. Thus the estimation of the vari- ant of ordering consists in the subtraction from every remainder of a certain constant and in the count of quantity of the obtained zero residuals. The variant with the greatest quantity of mo- dules, which residuals are equal to zero, are most preferable. K e y w o r d s: residual classes, complicated operations, modules, range. REFERENCES 1. Akushskiy, I.Ya. and Yuditskiy, D.I. (1968), Mashinnaya arifmetika v ostatochnykh klassov [Machine arithmetic in the residual classes], Sov. radio, Moscow, Russia. 2. Polissky, Yu.D. (2008), “Forming of position descriptions during tabular realization of algo- rithms of the system of residual classes”, Sbornik trudov konferentsii “Modelirovanie-2008” [Con- ference proceedings «Simulation-2008»], Vol. 2, Kiev, IPME, May, 14-16, 2008, pp. 489-495. 3. Polissky, Yu.D. (2014), “About intercommunication of unmodule operations in the system of residual classes”, Matematychne modelyuvannya, no. 2 (31), pp. 3-6. 4. Polissky, Yu.D. (2014), “Algorithm of implementation of complex operations in the system of residual classes with the help of numbers presentation in reverse codes”, Elektronnoe modelirovanie, Vol. 36, no. 4, pp. 117-122. 5. Polissky, Yu.D. (2015), “Choice of criterion of belonging of number to this half of range in the system of residual classes”, Problemy matematychnoho modelyuvannya. Materialy naukovo-metodychnoi konferentsii [Problems of mathematical modeling. Proc. of scientific- methodical conference], Dnepropetrovsk, May, 27-29, 2015, pp. 91-92. Ïîñòóïèëà 03.07.15; ïîñëå äîðàáîòêè 14.09.15 ÏÎËÈÑÑÊÈÉ Þðèé Äàâèäîâè÷, êàíä. òåõí. íàóê, ñò. íàó÷. ñîòð. Íàó÷íî-èññëåäî- âàòåëüñêîãî èí-òà àâòîìàòèçàöèè ÷åðíîé ìåòàëëóðãèè, ã. Äíåïðîïåòðîâñê.  1960 ã. îêîí÷èë Äíåïðîïåòðîâñêèé ìåòàëëóðãè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäî- âàíèé — ñèñòåìû è ñðåäñòâà óïðàâëåíèÿ. Þ.Ä. Ïîëèññêèé 48 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 5
id nasplib_isofts_kiev_ua-123456789-101163
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 0204-3572
language Russian
last_indexed 2025-12-07T18:52:57Z
publishDate 2015
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
record_format dspace
spelling Полисский, Ю.Д.
2016-05-31T17:59:26Z
2016-05-31T17:59:26Z
2015
Об одном подходе к выполнению сложных операций в системе остаточных классов / Ю.Д. Полисский // Электронное моделирование. — 2015. — Т. 37, № 5. — С. 39-48. — Бібліогр.: 5 назв. — рос.
0204-3572
https://nasplib.isofts.kiev.ua/handle/123456789/101163
681.04
Рассмотрен способ увеличения быстродействия операции определения принадлежности числа данной половине диапазона в системе остаточных классов. Предложено переупорядочение модулей на основе предварительной оценки вариантов упорядочения и выбора наилучшего варианта упорядочения на данной итерации.
Розглянуто спосіб збільшення швидкодії операції визначення приналежності числа даній половині діапазону в системі залишкових класів. Запропоновано переупорядковування модулів на основі попередньої оцінки варіантів впорядкування і вибору найкращого варіанта впорядкування на даній ітерації.
A method is considered for increasing the speed of response of the operation of determining a number belonging to the given half of range in the system of residual classes. The approach is based on reordering of modules with the preliminary estimation of variants of ordering and choice of the most preferable variant of ordering on this iteration. Thus the estimation of the variant of ordering consists in the subtraction from every remainder of a certain constant and in the count of quantity of the obtained zero residuals. The variant with the greatest quantity of modules, which residuals are equal to zero, are most preferable.
ru
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
Электронное моделирование
Математическое моделирование и вычислительные методы
Об одном подходе к выполнению сложных операций в системе остаточных классов
About one approach to execution of complicated operations in the system of residual classes
Article
published earlier
spellingShingle Об одном подходе к выполнению сложных операций в системе остаточных классов
Полисский, Ю.Д.
Математическое моделирование и вычислительные методы
title Об одном подходе к выполнению сложных операций в системе остаточных классов
title_alt About one approach to execution of complicated operations in the system of residual classes
title_full Об одном подходе к выполнению сложных операций в системе остаточных классов
title_fullStr Об одном подходе к выполнению сложных операций в системе остаточных классов
title_full_unstemmed Об одном подходе к выполнению сложных операций в системе остаточных классов
title_short Об одном подходе к выполнению сложных операций в системе остаточных классов
title_sort об одном подходе к выполнению сложных операций в системе остаточных классов
topic Математическое моделирование и вычислительные методы
topic_facet Математическое моделирование и вычислительные методы
url https://nasplib.isofts.kiev.ua/handle/123456789/101163
work_keys_str_mv AT polisskiiûd obodnompodhodekvypolneniûsložnyhoperaciivsistemeostatočnyhklassov
AT polisskiiûd aboutoneapproachtoexecutionofcomplicatedoperationsinthesystemofresidualclasses

Similar Items