АЛГОРИТМЫ ОЦЕНКИ МОДУЛЯРНЫХ ЧИСЕЛ В АРИФМЕТИКЕ С ПЛАВАЮЩЕЙ ТОЧКОЙ
Аннотация
В системе остаточных классов (СОК) операции сложения, вычитания и умножения выполняются параллельно по различным цифрам (остаткам) модулярных чисел. Благодаря этому СОК используется для получения максимальной производительности во многих приложениях высокоскоростной компьютерной арифметики. Однако, СОК имеет свои недостатки, особенно в отношении таких вопросов, как оценка величины модулярных чисел. Традиционные техники для оценки величины в СОК, которые основаны на китайской теореме об остатках или преобразовании к системе со смешанными основаниями, приводят к довольно медленным и неэффективным реализациям. Для того, чтобы решить эту проблему был предложен метод интервально-позиционных характеристик (ИПХ). В данной работе рассматриваются прямые и пошаговые алгоритмы вычисления ИПХ в арифметике с плавающей точкой фиксированной разрядности. Для каждого из алгоритмов оценивается сложность (в терминах элементарных арифметических операций) и точность.
Список литературы
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.
Рецензия
Для цитирования:
Исупов К.С. АЛГОРИТМЫ ОЦЕНКИ МОДУЛЯРНЫХ ЧИСЕЛ В АРИФМЕТИКЕ С ПЛАВАЮЩЕЙ ТОЧКОЙ. Наука. Инновации. Технологии. 2016;(4):43-56.
For citation:
Isupov K.S. Algorithms for estimating modular numbers in floating-point arithmetic. Science. Innovations. Technologies. 2016;(4):43-56. (In Russ.)
Просмотров:
31
Послать статью по эл. почте 