Метод умножения с масштабированием результата для высокоточных модулярно-позиционных интервально-логарифмических вычислений
Аннотация
Введение. Для решения задач моделирования, критичных к ошибкам округления (включая задачи вычислительной математики, математической физики, оптимального управления, биохимии, квантовой механики, математического программирования и криптографии), требуется точность от 100 до 1 000 десятичных цифр и более. Главным недостатком программных библиотек высокоточных вычислений является неприемлемое для практических задач снижение быстродействия, в особенности при выполнении операции умножения. Одним из способов повышения скорости вычислений над длинными числами является использование системы счисления в остаточных классах. В данной статье рассматривается новый, более быстрый по сравнению с аналогами метод выполнения операции умножения длинных чисел с масштабированием результата за счет применения оригинальной гибридной модулярно-позиционной интервально-логарифмической формы представления чисел с плавающей точкой.
Материалы и методы. Для повышения скорости вычислений разработан новый способ организации числовой информации (модулярно-позиционная интервальнологарифмическая форма), в котором мантисса представлена в системе остаточных классов, а информация об абсолютной величине числа (характеристика) – в интервально-логарифмической системе счисления, что позволяет ускорить выполнение операций сравнения и масштабирования. Для сравнения модулярных чисел применяются положения интервального анализа; для масштабирования модулярных чисел – свойства логарифмической системы счисления, а также приближенные интервальные вычисления с использованием китайской теоремы об остатках.
Результаты исследования. Разработан и запатентован новый быстрый метод умножения модулярных чисел с плавающей точкой, проведена оценка быстродействия разработанного метода, выполнено сравнение данного метода с классическими и конвейерными методами умножения длинных чисел.
Обсуждение и заключение. Разработанный метод в 2,4–4,0 раза быстрее конвейерного метода умножения и в 6,4–12,9 раз – классических методов умножения.
Литература
2. Voros A. Discretized Keiper/Li approach to the Riemann hypothesis // Experimental Mathematics. 2018. P. 1–18.
3. solveME: fast and reliable solution of nonlinear ME models / L. Yang [et al.] // BMC Bioinformatics. 2016. Vol. 17. P. 391.
4. Panzer E. Algorithms for the symbolic integration of hyperlogarithms with applications to Feynman integrals // Computer Physics Communications. 2015. Vol. 188. P. 148–166.
5. Miltenberger M., Ralphs T., Steffy D. E. Exploring the numerics of branch-and-cut for mixed integer linear optimization // Operations Research Proceedings 2017. Operations Research Proceedings (GOR (Gesellschaft für Operations Research e.V.)) / Eds. N. Kliewer, J. Ehmke, R. Borndörfer. Cham : Springer, 2018. P. 151–157.
6. Computer discovery and analysis of large Poisson polynomials / D. H. Bailey [et al.] // Experimental Mathematics. 2017. Vol. 26, no. 3. P. 349–363.
7. Pan B., Wang Y., Tian S. A high-precision single shooting method for solving hypersensitive optimal control problems // Mathematical Problems in Engineering. 2018. Vol. 2018. Article ID 7908378.
8. Isupov K., Knyazkov V. Interval estimation of relative values in residue number system // Journal of Circuits, Systems and Computers. 2018. Vol. 27, no. 1. P. 1850004.
9. GRAPE-MPs: implementation of an SIMD for quadruple/hexuple/octuple-precision arithmetic operation on a structured ASIC and an FPGA / N. Nakasato [et al.] // 2012 IEEE 6th International Symposium on Embedded Multicore SoCs. IEEE, 2012. P. 75–83.
10. Application of GRAPE9-MPX for high precision calculation in particle physics and performance results / H. Daisaka [et al.] // Procedia Computer Science. 2015. Vol. 51. P. 1323–1332.
11. El-Araby E., Gonzalez I., El-Ghazawi T. Bringing high-performance reconfigurable computing to exact computations // 2007 International Conference on Field Programmable Logic and Applications / Eds. K. Bertels [et al.]. IEEE, 2007. P. 79–85.
12. Lei Y., Dou Y., Zhou J. FPGA-specific custom VLIW architecture for arbitrary precision floatingpoint arithmetic // IEICE Transactions on Information and Systems. 2011. Vol. 94, no. 11. P. 2173–2183.
13. Fast modular arithmetic on the Kalray MPPA-256 processor for an energy-efficient implementation of ECM / M. Ishii [et al.] // IEEE Transactions on Computers. 2017. Vol. 66, issue 12. P. 2019–2030.
14. Schulte M. J., Swartzlander E. E. A family of variable-precision interval arithmetic processors // IEEE Transactions on Computers. 2000. Vol. 49, issue 5. P. 387–397.
15. Asif S., Kong Y. Highly parallel modular multiplier for elliptic curve cryptography in residue number system // Circuits, Systems, and Signal Processing. 2017. Vol. 36, issue 3. P. 1027–1051.
16. Kong Y., Lai Y. Low latency modular multiplication for public-key cryptosystems using a scalable array of parallel processing elements // 2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS). IEEE, 2013. P. 1039–1042.
17. Coleman J. N., Che Ismail R. LNS with co-transformation competes with floating-point // IEEE Transactions on Computers. 2016. Vol. 65, issue 1. P. 136–146.
18. Kouretas I., Basetas C., Paliouras V. Low-power logarithmic number system addition/subtraction and their impact on digital filters // IEEE Transactions on Computers. 2013. Vol. 62, issue 11. P. 2196–2209.
19. The European logarithmic microprocesor / J. N. Coleman [et al.] // IEEE Transactions on Computers. 2008. Vol. 57, issue 4. P. 532–546.
20. Bigou K., Tisserand A. Single base modular multiplication for efficient hardware RNS implementations of ECC // Cryptographic Hardware and Embedded Systems – CHES 2015 / Еds. T. Güneysu, H. Handschuh. Lecture Notes in Computer Science. 2015. Vol. 9293. P. 123–140.
21. Bajard J.-C., Eynard J., Merkiche N. Montgomery reduction within the context of residue number system arithmetic // Journal of Cryptographic Engineering. 2018. Vol. 8, issue 3. P. 189–200.
22. Czyżak M., Smyk R., Ulman Z. Pipelined scaling of signed residue numbers with the mixedradix conversion in the programmable gate array // Poznan University of Technology Academic Journals. Electrical Engineering. 2013. No. 76. P. 89–99.
23. A fully RNS based ECC processor / S. Asif [et al.] // Integration. 2018. Vol. 61. P. 138–149.
24. Pipelined FPGA coprocessor for elliptic curve cryptography based on residue number system / P. M. Matutino [et al.] // 2017 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS) / Eds. Y. Patt, S. K. Nandy. IEEE, 2017. P. 261–268.
25. Коржавина А. С., Князьков В. С. Методы расширения базиса в системе остаточных классов: обзор и анализ вычислительной сложности // Современные наукоемкие технологии. 2017. № 12. С. 37–42.
26. Harvey D., van der Hoeven J., Lecerf G. Even faster integer multiplication // Journal of Complexity. 2016. Vol. 36. P. 1–30.
27. Chang C. H., Low J. Y. S. Simple, fast, and exact RNS scaler for the three-moduli set (2n – 1, 2n, 2n + 1) // IEEE Transactions on Circuits and Systems I: Regular Papers. 2011. Vol. 58, issue 11. P. 2686–2697.
28. Hiasat A. Efficient RNS scalers for the extended three-moduli set (2n – 1, 2n + p, 2n + 1) // IEEE Transactions on Computers. 2017. Vol. 66, issue 7. P. 1253–1260.
29. Kong Y., Phillips B. Fast scaling in the residue number system // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2009. Vol. 17, issue 3. P. 443–447.
30. Meyer-Base U., Stouraitis T. New power-of-2 RNS scaling scheme for cell-based IC design // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2003. Vol. 11, issue 2. P. 280–283.
31. Johansson F. Arb: efficient arbitrary-precision midpoint-radius interval arithmetic // IEEE Transactions on Computers. 2017. Vol. 66, issue 8. P. 1281–1292.
32. Revol N. Introduction to the IEEE 1788-2015 standard for interval arithmetic // Numerical Software Verification. NSV 2017 / Еds. A. Abate, S. Boldo. Lecture Notes in Computer Science. 2017. Vol. 10381. P. 14–21.
33. Osinin I. A modular-logarithmic coprocessor concept // 2017 International Conference on High Performance Computing & Simulation (HPCS). IEEE, 2017. P. 588–594.
34. Способ организации выполнения операции умножения двух чисел в модулярно-логарифмическом формате представления с плавающей точкой на гибридных многоядерных процессорах : пат. 2666285 Рос. Федерация : МПК G 06 F 7/483, G 06 F 7/487 / Князьков В. С., Коржавина А. С. ; заявитель и патентообладатель ФГБОУ ВО «Вятский государственный университет». № 2017135775/22 ; заявл. 06.10.2017; опубл. 06.09.2018, Бюл. № 25.
