msiСовременная наука и инновацииModern Science and Innovations2307-910XNorth-Caucasus Federal University10.33236/2307-910Х-2018-4-24-18-28msi-633Research ArticleТЕХНИЧЕСКИЕ НАУКИ ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕTECHNICAL SCIENCES INFORMATION, COMPUTING AND MANAGEMENTВЫСОКОСКОРОСТНОЙ АЛГОРИТМ ДЕЛЕНИЯ МОДУЛЯРНЫХ ЧИСЕЛ НА ОСНОВЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ С ДРОБЯМИTHE HIGH-SPEED ALGORITHM OF DIVISION OF MODULAR NUMBERS BASED ON CHINESE REMINDER THEOREM WITH FRACTIONSЧервяковНиколай ИвановичChervyakovNikolay Ivanovichncherviakov@ncfu.ruЛяховПавел АлексеевичLyakhovPavel Alekseevichljahov@mail.ruЛавриненкоИрина НиколаевнаLavrinenkoIrina Nikolaevnalavrinenko_irl@mail.ruДерябинМаксим АнатольевичDeryabinMaxim Anatolievichmaderiabin@ncfu.ruСеверо-Кавказский федеральный университетРоссияNorth-Caucasus Federal UniversityRussian Federation201811102022041828Copyright © Червяков Н.И., Ляхов П.А., Лавриненко И.Н., Дерябин М.А., 20222022Червяков Н.И., Ляхов П.А., Лавриненко И.Н., Дерябин М.А.Chervyakov N.I., Lyakhov P.A., Lavrinenko I.N., Deryabin M.A.This work is licensed under a Creative Commons Attribution 4.0 License.https://msi.elpub.ru/jour/article/view/633

В даннойработе представлен новый алгоритм деления чисел, представленных в системе остаточных классов. Данный алгоритм опирается на новую Китайскую теорему об остатках с дробными числами, что позволило существенно ускорить выполнение операций. В работе приведено детальное описание алгоритма и произведена оценка его сложности. Особенностью традиционных вычислительных средств является наличие ограниченной разрядной сетки, которая приводит к вычислительной сложности при выполнении операций над числами большой размерности. Вычисления с многоразрядными числами или вычисления с величинами, меняющимися в больших диапазонах, являются одной из областей, в которой система остаточных классов (СОК) имеет преимущество перед позиционными системами счисления. Однако существует ряд операций, которые в СОК сложно реализуемы. К ним относится и операция деления чисел. Известные итеративные алгоритмы модулярного деления в системе остаточных классов выполняются с помощью итераций, которые состоят из таких трудно выполняемых операций над абсолютными значениями делимого и делителя как: преобразование Китайской теоремы об остатках и обобщенной позиционной системы счисления, сравнение, определение знаков числа и проверки четности, расширения, специальной логики и таблиц для получения приблизительного делителя и другие, что и определяет большую вычислительную сложность операции деления. В данной статье предлагается альтернативный вариант модулярного деления чисел большой размерности, в котором абсолютные значения делимого и делителя заменяются на относительные их значения по отношению к модулям системы остаточных классов.

The paper about a new algorithm for division the numbers represented in the residue number system. This algorithm is based on a new Chinese Reminder Theorem with fractional numbers, which made it possible to significantly accelerate the operations. The paper gives the detailed description of the algorithm and the estimation of its complexity.

алгоритмсистема остаточных классовмодулярная арифметикаделениеalgorithmResidue Number Systemmodular arithmeticdivisionReferencesSzabo N. S., Tanaka R. I. Residue Arithmetic and Its Application to Computer Technology: McGraw-Hill, 1967.Szabo N. S., Tanaka R. I. Residue Arithmetic and Its Application to Computer Technology: McGraw-Hill, 1967.Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. London: Imperial College Press, 2007.Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. London: Imperial College Press, 2007.Alia G., Martinelli E. NEUROM: a ROM based RNS digital neuron // Neural Networks. 2005. No. 18. P. 179-189.Alia G., Martinelli E. NEUROM: a ROM based RNS digital neuron // Neural Networks. 2005. No. 18. P. 179-189.Gomathisankaran M., Tyagi A., Namuduri K. HORNS: A homomorphic encryption scheme for Cloud Computing using Residue Number System // Information Sciences and Systems (CISS), 45th Annual Conference. 2011. P. 1-5.Gomathisankaran M., Tyagi A., Namuduri K. HORNS: A homomorphic encryption scheme for Cloud Computing using Residue Number System // Information Sciences and Systems (CISS), 45th Annual Conference. 2011. P. 1-5.Zheng XD., Xu J., Li W. Parallel DNA arithmetic operation based on n-moduli set // Applied Mathematics and Computation. 2009. No. 212(1). P. 177-184.Zheng XD., Xu J., Li W. Parallel DNA arithmetic operation based on n-moduli set // Applied Mathematics and Computation. 2009. No. 212(1). P. 177-184.Su Jun, Zhengbing Hu. Method and dedicated processor for image coding based on residue number system // Modern Problems of Radio Engineering Telecommunications and Computer Science (TCSET), International Conference. 2012. P. 406-407.Su Jun, Zhengbing Hu. Method and dedicated processor for image coding based on residue number system // Modern Problems of Radio Engineering Telecommunications and Computer Science (TCSET), International Conference. 2012. P. 406-407.Mohan P. V.A.: 'Residue Number Systems: Theory and Applications', Birkhauser Basel, 2016.Mohan P. V.A.: 'Residue Number Systems: Theory and Applications', Birkhauser Basel, 2016.Molahosseini A.S., Sorouri S., Zarandi A.A.E. Research challenges in next-generation residue number system architectures // Computer Science & Education (ICCSE), 7th International Conference. 2012. P. 1658-1661.Molahosseini A.S., Sorouri S., Zarandi A.A.E. Research challenges in next-generation residue number system architectures // Computer Science & Education (ICCSE), 7th International Conference. 2012. P. 1658-1661.N. I. Chervyakov, P. A. Lyakhov, M. G. Babenko, A. I. Garyanina, I. N. Lavrinenko, A. V. Lavrinenko, M. A. Deryabin, "An efficient method of error correction in fault-tolerant modular neurocomputers," Neurocomputing, Elsevier Journal, vol. 205, pp. 3244, 2016.N. I. Chervyakov, P. A. Lyakhov, M. G. Babenko, A. I. Garyanina, I. N. Lavrinenko, A. V. Lavrinenko, M. A. Deryabin, "An efficient method of error correction in fault-tolerant modular neurocomputers," Neurocomputing, Elsevier Journal, vol. 205, pp. 3244, 2016.Chervyakov N. I., Molahosseini A. S., Lyakhov P. A., Babenko M. G., Deryabin M. A.: 'Residue-to-Binary Conversion for General Moduli Sets Based on Approximate Chinese Remainder Theorem', International Journal of Computer Mathematics, August 2016, Pages 1-17.Chervyakov N. I., Molahosseini A. S., Lyakhov P. A., Babenko M. G., Deryabin M. A.: 'Residue-to-Binary Conversion for General Moduli Sets Based on Approximate Chinese Remainder Theorem', International Journal of Computer Mathematics, August 2016, Pages 1-17.W. A. Chren Jr. A new residue number division algorithm // Computers & Mathematics with Aplications. 1990. V. 19. P. 1329.W. A. Chren Jr. A new residue number division algorithm // Computers & Mathematics with Aplications. 1990. V. 19. P. 1329.J.-S. Chiang, Mi Lu. A general Division Algotithm for Residue Number Systems.// 10lh IEEE Symposium on Computer Arithmetic. 1991.J.-S. Chiang, Mi Lu. A general Division Algotithm for Residue Number Systems.// 10lh IEEE Symposium on Computer Arithmetic. 1991.D. Gamberger. New Approach to Integer Division in Residue Number Systems.// 10Lh IEEE Symposium on Computer Arithmetic. 1991.D. Gamberger. New Approach to Integer Division in Residue Number Systems.// 10Lh IEEE Symposium on Computer Arithmetic. 1991.M. Lu and J. S. Chiang. A novel division algorithm for Reside Number Systems.// IEEE Transactions on Computers. 1992. V. 41, No. 8. P.1026-1032.M. Lu and J. S. Chiang. A novel division algorithm for Reside Number Systems.// IEEE Transactions on Computers. 1992. V. 41, No. 8. P.1026-1032.Hung C. Y., Parhami B. Fast RNS division algorithms for fixed divisors with application to RSA encryption // Information Processing Letters. 1994. V. 51, No. 4. P. 163-169.Hung C. Y., Parhami B. Fast RNS division algorithms for fixed divisors with application to RSA encryption // Information Processing Letters. 1994. V. 51, No. 4. P. 163-169.Hung C. Y., Parhami В., An Approximate Sign Detection Method for Residue Numbers and its Application to RNS Division// Computers and Mathematics with Applications. 1994. P. 23-35.Hung C. Y., Parhami В., An Approximate Sign Detection Method for Residue Numbers and its Application to RNS Division// Computers and Mathematics with Applications. 1994. P. 23-35.A. A. Hiasat, H. S. Abdel-Aty-Zohdy. Design and Implementation of an RSN Division Algorithm.// 13Lh IEEE Symposium on Computer Arithmetic. 1997. Выпуск #4, 2018 26 сов рем ен н ая н аука и ин н оваци иA. A. Hiasat, H. S. Abdel-Aty-Zohdy. Design and Implementation of an RSN Division Algorithm.// 13Lh IEEE Symposium on Computer Arithmetic. 1997. Выпуск #4, 2018 26 сов рем ен н ая н аука и ин н оваци иLean Claude Bajard, Laurent Stephane Didier, Jean Michel Muller. A new Euclidean division algorithm for residue number systems// Journal of VLSI signal processing systems for signal, image and video technology. 1998. V. 19. P 167-178.Lean Claude Bajard, Laurent Stephane Didier, Jean Michel Muller. A new Euclidean division algorithm for residue number systems// Journal of VLSI signal processing systems for signal, image and video technology. 1998. V. 19. P 167-178.A. A. Hiasat, H. S. Abdel-Aty-Zohdy. Semi-custom VLSI design and implementation of a new efficient RSN division algorithm.// The Computer journal. 1999. V. 42, No. 3. P. 232-240.A. A. Hiasat, H. S. Abdel-Aty-Zohdy. Semi-custom VLSI design and implementation of a new efficient RSN division algorithm.// The Computer journal. 1999. V. 42, No. 3. P. 232-240.J. C. Bajard et. F. Rico. How to improve division in residue number systems. // 16Lh IMACS world congress. 2000. P 110-121.J. C. Bajard et. F. Rico. How to improve division in residue number systems. // 16Lh IMACS world congress. 2000. P 110-121.S. Talahmeh, P. Siy. Arithmetic division in RSN using field GF(p). // Computers & mathematics with applications. 2000. V. 39. P. 227-238.S. Talahmeh, P. Siy. Arithmetic division in RSN using field GF(p). // Computers & mathematics with applications. 2000. V. 39. P. 227-238.Y. H. Yang, С. C. Chang and C. Y. Chen. A high-speed division algorithm in residue number system using parity-checking technique // International journal of computer mathematics. 2004. V. 81, No. 6. P 775-780.Y. H. Yang, С. C. Chang and C. Y. Chen. A high-speed division algorithm in residue number system using parity-checking technique // International journal of computer mathematics. 2004. V. 81, No. 6. P 775-780.Chin-Chen Chang, Yeu-Pong Lai. A division algorithm for residue numbers // Applied Mathematics and Computation. 2006. V. 172, No. LP. 368-378.Chin-Chen Chang, Yeu-Pong Lai. A division algorithm for residue numbers // Applied Mathematics and Computation. 2006. V. 172, No. LP. 368-378.Chin-Chen Chang, Jen-Ho Yang. A division algorithm using bisection method in residue number system. // International journal of computer, computer and control (IJ3C). 2013. V. 2, No. 1. P 59.Chin-Chen Chang, Jen-Ho Yang. A division algorithm using bisection method in residue number system. // International journal of computer, computer and control (IJ3C). 2013. V. 2, No. 1. P 59.Chervyakov N.I., Babenko M.G., Lyakhov P.A., Lavrinenko I.N. An approximate method for comparing modular numbers and its application to the division of numbers in residue number systems // Cybernetics and Systems Analysis. 2014. V. 50. No. 6. P. 977-984.Chervyakov N.I., Babenko M.G., Lyakhov P.A., Lavrinenko I.N. An approximate method for comparing modular numbers and its application to the division of numbers in residue number systems // Cybernetics and Systems Analysis. 2014. V. 50. No. 6. P. 977-984.Yones D., Steffan P. A comparative study on different moduli sets in residue number system // Proc. IEEE Int. conf. on computer systems and industrial informatics (ICCSII). P. 1-6, 2012.Yones D., Steffan P. A comparative study on different moduli sets in residue number system // Proc. IEEE Int. conf. on computer systems and industrial informatics (ICCSII). P. 1-6, 2012.Червяков H. И., Ляхов П. А. Метод определения знака числа в системе остаточных классов на основе приближенных вычислений // Нейрокомпьютеры: разработка, применение. 2012. № 12. С. 56-64.Червяков H. И., Ляхов П. А. Метод определения знака числа в системе остаточных классов на основе приближенных вычислений // Нейрокомпьютеры: разработка, применение. 2012. № 12. С. 56-64.Червяков Н. И., Бабенко М. Г., Ляхов П. А., Лавриненко И. Н. Приближенный метод определения знака числа в системе остаточных классов и его техническая реализация // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. 2013. № 176. С. 131-141.Червяков Н. И., Бабенко М. Г., Ляхов П. А., Лавриненко И. Н. Приближенный метод определения знака числа в системе остаточных классов и его техническая реализация // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. 2013. № 176. С. 131-141.

The authors declare that there are no conflicts of interest present.