Построение модифицированной совершенной формы системы остаточных классов с использованием факторизации

Abstract

RU: Актуальность. Решена актуальная задача нахождения модулей системы остаточных классов, в которой повышается скорость перевода чисел из системы остаточных классов в десятичную систему исчисления. Цель работы – разработка метода построения четырeхмодульной модифицированной совершенной формы системы остаточных классов, в которой отсутствует процедура поиска обратного элемента по модулю при переводе чисел из системы остаточных классов в десятичную систему исчисления. Метод. Предложен метод определения набора модулей модифицированной совершенной формы системы остаточных классов на основе факторизации произведения чисел. Использование данного метода позволяет существенно уменьшить вычислительную сложность при выполнении арифметических операций над многоразрядными числами путeм распараллеливания процесса вычислений и переводе чисел из системы остаточных классов в десятичную систему исчисления за счeт исключения процедуры поиска обратного элемента по модулю и умножения на базисные числа. Определены условия для нахождения любого количества модулей модифицированной совершенной формы системы остаточных классов, два из которых являются неизвестными. Приведeн пример использования предложенного метода для четырeхмодульной модифицированной совершенной формы системы остаточных классов, в котором получены все возможные наборы модулей при заданном наименьшем модуле. Представлены табличные значения и проанализированы графические зависимости полученных модулей. Результаты. Использование предложенного метода подбора модулей, которые образуют модифицированную совершенную форму, позволит увеличить быстродействие вычислительных систем, работающих в системе остаточных классов. Выводы. Впервые предложен метод построения четырeхмодульной модифицированной совершенной формы системы остаточных классов на основе факторизации, в которой отсутствует сложная процедура поиска обратного элемента по модулю. Это позволяет упростить процессы вычислений над многоразрядными числами и перевода чисел из системы остаточных классов в десятичную систему исчисления. UK: Актуальність. Вирішено актуальне завдання знаходження модулів системи залишкових класів, в якій підвищується швидкість переведення чисел із системи залишкових класів у десяткову систему числення. Мета роботи – розробка методу побудови чотирьохмодульної модифікованої досконалої форми системи залишкових класів, в якій відсутня процедура пошуку оберненого елемента за модулем при переведенні чисел із системи залишкових класів у десяткову систему числення. Метод. Запропоновано метод визначення набору модулів модифікованої досконалої форми системи залишкових класів на основі факторизації добутку чисел. Використання даного методу дозволяє істотно зменшити обчислювальну складність при виконанні арифметичних операцій над багаторозрядними числами шляхом розпаралелювання процесу обчислень та переведенні чисел із системи залишкових класів у десяткову систему числення за рахунок уникнення процедури пошуку оберненого елемента за модулем і множення на базисні числа. Визначено умови для знаходження будь-якої кількості модулів модифікованої досконалої форми системи залишкових класів, два з яких є невідомими. Наведено приклад використання запропонованого методу для чотирьохмодульної модифікованої досконалої форми системи залишкових класів, в якому отримані всі можливі набори модулів при заданому найменшому модулі. Представлено табличні значення та проаналізовані графічні залежності отриманих модулів. Результати. Використання запропонованого методу підбору модулів, що утворюють модифіковану досконалу форму, дозволить збільшити швидкодію обчислювальних систем, які працюють у системі залишкових класів. Висновки. Вперше запропоновано метод побудови чотирьохмодульної модифікованої досконалої форми системи залишкових класів на основі факторизації, в якій відсутня складна процедура пошуку оберненого елемента за модулем. Це дозволяє спростити процеси обчислень над багаторозрядними числами і переведення чисел із системи залишкових класів у десяткову систему числення. EN: Context. The urgent task of finding modules of the system of residue classes, which characterize by increasing the speed of transition of numbers from the system of residue classes into decimal number system. Objective is to develop a method of constructing modified fourth-module perfect form of the system of residue classes without procedure of finding of the absolute value for inverse element under number transition from residue number system to decimal number system. Method. The method of determining a set of modules if modified perfect form of system’s of residue number was proposed which was based on factorization of numbers product. Usage of this form significantly reduced the computational complexity when arithmetic operations were performing on multi-digital numbers and transferring of numbers from the system of residual classes in the decimal system of calculation by eliminating of the searching procedure of the inverse element in absolute value and multiplying by the basic numbers. The conditions of discovering of any absolute number of modified perfect form of system of residual classes and two of them are unknown. An example of the proposed method for forth-module with modified perfect form system, which received all possible sets of modules with given smallest module. Tabular amounts are presented and analyzed according to the received image of modules. Results. Utilization of the proposed method of modules selection which has constructed modified perfect form allows to increase the performance of computing systems operating in the system residual classes. Conclusions. It’s the first time of discover of the method which allows to construct modified fourth-module perfect form of the system of residue classes based on factorization without complicated procedure of finding of the absolute value for inverse element. Present work helps to simplify the process of calculating digit number and transfer numbers from the system of residual classes into decimal system.