ВЫСОКОСКОРОСТНОЙ АЛГОРИТМ ДЕЛЕНИЯ МОДУЛЯРНЫХ ЧИСЕЛ НА ОСНОВЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ С ДРОБЯМИ

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

алгоритм, система остаточных классов, модулярная арифметика, деление, algorithm, Residue Number System, modular arithmetic, division

1. Szabo N. S., Tanaka R. I. Residue Arithmetic and Its Application to Computer Technology: McGraw-Hill, 1967.

2. Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. London: Imperial College Press, 2007.

3. Alia G., Martinelli E. NEUROM: a ROM based RNS digital neuron // Neural Networks. 2005. No. 18. P. 179-189.

4. 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.

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.

6. 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.

7. Mohan P. V.A.: 'Residue Number Systems: Theory and Applications', Birkhauser Basel, 2016.

8. 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.

9. 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.

10. 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.

11. W. A. Chren Jr. A new residue number division algorithm // Computers & Mathematics with Aplications. 1990. V. 19. P. 1329.

12. J.-S. Chiang, Mi Lu. A general Division Algotithm for Residue Number Systems.// 10lh IEEE Symposium on Computer Arithmetic. 1991.

13. D. Gamberger. New Approach to Integer Division in Residue Number Systems.// 10Lh IEEE Symposium on Computer Arithmetic. 1991.

14. 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.

15. 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.

16. 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.

17. 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 сов рем ен н ая н аука и ин н оваци и

18. 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.

19. 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.

20. J. C. Bajard et. F. Rico. How to improve division in residue number systems. // 16Lh IMACS world congress. 2000. P 110-121.

21. S. Talahmeh, P. Siy. Arithmetic division in RSN using field GF(p). // Computers & mathematics with applications. 2000. V. 39. P. 227-238.

22. 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.

23. Chin-Chen Chang, Yeu-Pong Lai. A division algorithm for residue numbers // Applied Mathematics and Computation. 2006. V. 172, No. LP. 368-378.

24. 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.

25. 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.

26. 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.

27. Червяков H. И., Ляхов П. А. Метод определения знака числа в системе остаточных классов на основе приближенных вычислений // Нейрокомпьютеры: разработка, применение. 2012. № 12. С. 56-64.

28. Червяков Н. И., Бабенко М. Г., Ляхов П. А., Лавриненко И. Н. Приближенный метод определения знака числа в системе остаточных классов и его техническая реализация // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. 2013. № 176. С. 131-141.