Algorithms for estimating modular numbers in floating-point arithmetic
Abstract
In the residue number system (RNS), the operations of addition, subtraction, and multiplication are executed in parallel for different digits (residues) of the modular numbers. Therefore, RNS is used for reaching the maximum performance in many high-speed computer arithmetic applications. However, RNS has disadvantages, especially in issues like estimating the magnitudes of modular numbers. Traditional methods for estimating the magnitudes in RNS that are based on the Chinese remainder theorem, or on the Mixed-Radix Conversion, result in rather slow and inefficient implementation. For solving this problem, the interval floating-point characteristic (IFC) method was proposed. This paper describes direct and stepwise algorithms for IFC computation in fixed-precision floating-point arithmetic. Time complexity (in terms of the elementary arithmetic operations) and accuracy are assessed for each algorithm.
References
1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М.: Сов. pадио, 1968.
2. Szabo N.S., Tanaka R.I. Residue Arithmetic and its Application to Computer Technology. New York: McGraw-Hill, 1967.
3. Parhami B. Computer Arithmetic: Algorithms and Hardware Designs. New York: Oxford Univ. Press, 2000.
4. Albicocco P., Cardarilli G.C., Nannarelli A., Re M. Twenty years of research on RNS for DSP: Lessons learned and future perspectives // Proceedings of the 2014 International Symposium on Integrated Circuits (ISIC). Singapore, 2014. P. 436-439.
5. Esmaeildoust M., Schinianakis D., Javashi H., Stouraitis T., Navi K. Efficient RNS implementation of elliptic curve point multiplication over GF(p) // IEEE Trans. VLSI Syst. 2013. Vol. 21. № 8. P. 15451549.
6. Goh V.T., Siddiqi M.U. Multiple error detection and correction based on redundant residue number systems // IEEE Trans. Commun. 2008. Vol. 56. № 3. P. 325-330.
7. Червяков Н.И., Нагорнов Н.Н. Коррекция ошибок при передаче и обработке информации, представленной в СОК, методом синдромного декодирования // Наука. Инновации. Технологии. 2015. № 2. С. 15-40.
8. Dimauro G., Impedovo S., Pirlo G. A new technique for fast number comparison in the residue number system // IEEE Trans. Comput. 1993. Vol. 42. № 5. P. 608-612.
9. Yang J.-H., Chang C.-C., Chen C.-Y. A high-speed division algorithm in residue number system using parity-checking technique // International Journal of Computer Mathematics. 2004. Vol. 81. №6. P. 775-780.
10. Князьков В.С., Исупов К.С. Немодульные вычисления в системах остаточных классов с интервально-позиционными характеристиками / ВятГУ. Киров, 2015. 92 с. Библиогр. 54 назв. Деп. в ВИНИТИ РАН 26.03.2015, № 61-В2015.
11. Hung C.Y., Parhami B. An approximate sign detection method for residue numbers and its application to RNS division // Computers & Mathematics with Applications. 1994. Vol. 27. № 4. P. 23-35.
12. Muller J.-M., Brisebarre N., de Dinechin F., Jeannerod C.-P., Lefèvre V., Melquiond G., Revol N., Stehlé D., Torres S. Handbook of Floating-Point Arithmetic. Boston: Birkhäuser, 2010.
13. Goldberg D. What Every Computer Scientist Should Know About Floating-Point Arithmetic // ACM Computing Surveys. 1991. Vol. 23. №. 1. P. 5-48.
14. Higham N.J. The accuracy of floating point summation // SIAM Journal on Scientific Computing. 1993. Vol. 14. № 4. P. 783-799.
Review
For citations:
Isupov K.S. Algorithms for estimating modular numbers in floating-point arithmetic. Science. Innovations. Technologies. 2016;(4):43-56. (In Russ.)
Views:
33
Email this article 