scienceitНаука. Инновации. ТехнологииScience. Innovations. Technologies2308-4758North-Caucasus Federal Universityscienceit-294Research ArticleФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИPHYSICAL AND MATHEMATICAL SCIENCESАЛГОРИТМЫ ОЦЕНКИ МОДУЛЯРНЫХ ЧИСЕЛ В АРИФМЕТИКЕ С ПЛАВАЮЩЕЙ ТОЧКОЙAlgorithms for estimating modular numbers in floating-point arithmeticИсуповКонстантин СергеевичIsupovKonstantin Sergeevichks_isupov@vyatsu.ruВятский государственный университетРоссияVyatka State UniversityRussian Federation201606092022044356Copyright © Исупов К.С., 20222022Исупов К.С.Isupov K.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://scienceit.elpub.ru/jour/article/view/294

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

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.

система остаточных классовоценка величиныточностьвысокая производительностьалгоритмыresidue number systemmagnitude estimationaccuracyhigh performancealgorithmsReferencesАкушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М.: Сов. pадио, 1968.Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М.: Сов. pадио, 1968.Szabo N.S., Tanaka R.I. Residue Arithmetic and its Application to Computer Technology. New York: McGraw-Hill, 1967.Szabo N.S., Tanaka R.I. Residue Arithmetic and its Application to Computer Technology. New York: McGraw-Hill, 1967.Parhami B. Computer Arithmetic: Algorithms and Hardware Designs. New York: Oxford Univ. Press, 2000.Parhami B. Computer Arithmetic: Algorithms and Hardware Designs. New York: Oxford Univ. Press, 2000.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.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.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.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.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.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.Червяков Н.И., Нагорнов Н.Н. Коррекция ошибок при передаче и обработке информации, представленной в СОК, методом синдромного декодирования // Наука. Инновации. Технологии. 2015. № 2. С. 15-40.Червяков Н.И., Нагорнов Н.Н. Коррекция ошибок при передаче и обработке информации, представленной в СОК, методом синдромного декодирования // Наука. Инновации. Технологии. 2015. № 2. С. 15-40.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.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.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.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.Князьков В.С., Исупов К.С. Немодульные вычисления в системах остаточных классов с интервально-позиционными характеристиками / ВятГУ. Киров, 2015. 92 с. Библиогр. 54 назв. Деп. в ВИНИТИ РАН 26.03.2015, № 61-В2015.Князьков В.С., Исупов К.С. Немодульные вычисления в системах остаточных классов с интервально-позиционными характеристиками / ВятГУ. Киров, 2015. 92 с. Библиогр. 54 назв. Деп. в ВИНИТИ РАН 26.03.2015, № 61-В2015.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.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.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.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.Goldberg D. What Every Computer Scientist Should Know About Floating-Point Arithmetic // ACM Computing Surveys. 1991. Vol. 23. №. 1. P. 5-48.Goldberg D. What Every Computer Scientist Should Know About Floating-Point Arithmetic // ACM Computing Surveys. 1991. Vol. 23. №. 1. P. 5-48.Higham N.J. The accuracy of floating point summation // SIAM Journal on Scientific Computing. 1993. Vol. 14. № 4. P. 783-799.Higham N.J. The accuracy of floating point summation // SIAM Journal on Scientific Computing. 1993. Vol. 14. № 4. P. 783-799.

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