THE HIGH-SPEED ALGORITHM OF DIVISION OF MODULAR NUMBERS BASED ON CHINESE REMINDER THEOREM WITH FRACTIONS
https://doi.org/10.33236/2307- 910Х-2018-4-24-18-28
Abstract
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.
About the Authors
Nikolay Ivanovich Chervyakov
North-Caucasus Federal University
Russian Federation
Russian Federation
Pavel Alekseevich Lyakhov
North-Caucasus Federal University
Russian Federation
Russian Federation
Irina Nikolaevna Lavrinenko
North-Caucasus Federal University
Russian Federation
Russian Federation
Maxim Anatolievich Deryabin
North-Caucasus Federal University
Russian Federation
Russian Federation
References
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.
Review
For citations:
Chervyakov N.I., Lyakhov P.A., Lavrinenko I.N., Deryabin M.A. THE HIGH-SPEED ALGORITHM OF DIVISION OF MODULAR NUMBERS BASED ON CHINESE REMINDER THEOREM WITH FRACTIONS. Modern Science and Innovations. 2018;(4):18-28. (In Russ.) https://doi.org/10.33236/2307- 910Х-2018-4-24-18-28
Views:
79
Email this article 