Реализация высокоточных вычислений в базисе модулярно-интервальной арифметики
Автор: Коржавина Анастасия Сергеевна, Князьков Владимир Сергеевич
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Математические основы программирования
Статья в выпуске: 3 (42) т.10, 2019 года.
Бесплатный доступ
Проблема влияния ошибок округления возникает в большом количестве задач в различных областях знаний, включая вычислительную математику, математическую физику, биохимию, квантовую механику, математическое программирование. Для решения таких задач может потребоваться точность в 100-1000 десятичных цифр. В рамках данного исследования разработаны новые способы представления числовой информации - модулярно-позиционные интервально-логарифмические системы счисления, а также методы выполнения арифметических операций для повышения скорости высокоточных вычислений.
Модулярная арифметика, гибридные системы счисления, логарифмическая интервальная характеристика, высокоточные вычисления, длинная арифметика
Короткий адрес: https://sciup.org/143169803
IDR: 143169803 | DOI: 10.25209/2079-3316-2019-10-3-81-127
Список литературы Реализация высокоточных вычислений в базисе модулярно-интервальной арифметики
- T. Kawahira. “The Riemann hypothesis and holomorphic index in complex dynamics”, Experimental Mathematics, 27:1 (2018), pp. 37-46. DOI: 10.1080/10586458.2016.1217443
- W. Worden. “Experimental statistics of veering triangulations”, Experimental Mathematics, 2018, 22 pp. DOI: 10.1080/10586458.2018.1437850
- A. Ash, L. Beltis, R. Gross, W. Sinnott. “Frequencies of successive pairs of prime residues”, Experimental Mathematics, 20:4 (2011), pp. 400-411. DOI: 10.1080/10586458.2011.565256
- A. Voros. “Discretized Keiper/Li approach to the Riemann hypothesis”, Experimental Mathematics, 2018, 18 pp. DOI: 10.1080/10586458.2018.1482480
- N. K. Johnson-McDaniel, A. G. Shah, B. F. Whiting. “Experimental mathematics meets gravitational self-force”, Physical Review D, 92:4 (2015), 044007. DOI: 10.1103/PhysRevD.92.044007
- D. H. Bailey, J. M. Borwein. “High-precision numerical integration: Progress and challenges”, Journal of Symbolic Computation, 46:7 (2011), pp. 741-754.
- DOI: 10.1016/j.jsc.2010.08.010
- E. Panzer. “Algorithms for the symbolic integration of hyperlogarithms with applications to Feynman integrals”, Computer Physics Communications, 188 (2015), pp. 148-166.
- DOI: 10.1016/j.cpc.2014.10.019
- D. H. Bailey, J. M. Borwein, J. S. Kimberley, W. Ladd. “Computer discovery and analysis of large Poisson polynomials”, Experimental Mathematics, 26:3 (2017), pp. 349-363.
- DOI: 10.1080/10586458.2016.1180565
- K. K. H. Cheung, A. Gleixner, D. E. Steffy. “Verifying integer programming results”, IPCO 2017: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 10328, Springer, 2017, pp. 148-160.
- DOI: 10.1007/978-3-319-59250-3_13
- A. V. Panyukov, V. A. Golodov. «Parallel algorithms of integer arithmetic in radix notations for heterogeneous computation systems with massive parallelism», Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 8:2 (2015), с. 117-126 (in English).
- DOI: 10.14529/mmp150210
- M. Miltenberger, T. Ralphs, D. E. Steffy. “Exploring the numerics of branch-and-cut for mixed integer linear optimization”, Operations Research Proceedings 2017, Operations Research Proceedings, Springer, 2018, pp. 151-157.
- DOI: 10.1007/978-3-319-89920-6_21
- W. Cook, Th. Koch, D. E. Steffy, K. Wolter. “An exact rational mixed-integer programming solver”, IPCO 2011: Integer Programming and Combinatoral Optimization, Lecture Notes in Computer Science, vol. 6655, Springer, Berlin-Heidelberg, 2011, pp. 104-116.
- DOI: 10.1007/978-3-642-20807-2_9
- A. M. Gleixner, D. E. Steffy, K. Wolter. “Iterative refinement for linear programming”, INFORMS Journal on Computing, 28:3 (2016), pp. 449-464.
- DOI: 10.1287/ijoc.2016.0692
- A. F. Cheviakov, J. He. “A symbolic computation framework for constitutive modelling based on entropy principles”, Applied Mathematics and Computation, 324 (2018), pp. 105-118.
- DOI: 10.1016/j.amc.2017.12.004
- M. Wei, J. Cai. “The exact rational solutions to a shallow water wave-like equation by generalized bilinear method”, Journal of Applied Mathematics and Physics, 5:03 (2017), pp. 715-721.
- DOI: 10.4236/jamp.2017.53060
- Z. Cao, X. Hou. “A symbolic computation approach to parameterizing controller for polynomial Hamiltonian systems”, Mathematical Problems in Engineering, 2014 (2014), 806428, 8 pp.
- DOI: 10.1155/2014/806428
- Z. Krougly, M. Davison, S. Aiyar. “The role of high precision arithmetic in calculating numerical Laplace and inverse Laplace transforms”, Applied Mathematics, 8:04 (2017), pp. 562.
- DOI: 10.4236/am.2017.84045
- L. N. Gergidis, D. Kourounis, S. Mavratzas, A. Charalambopoulos. “Numerical investigation of the acoustic scattering problem from penetrable prolate spheroidal structures using the Vekua transformation and arbitrary precision arithmetic”, Mathematical Methods in the Applied Sciences, 41:13.
- DOI: 10.1002/mma.5058
- R. Barrio, A. Dena, W. Tucker. “A database of rigorous and high-precision periodic orbits of the Lorenz model”, Computer Physics Communications, 194 (2015), pp. 76-83.
- DOI: 10.1016/j.cpc.2015.04.007
- G. Khanna. “High-precision numerical simulations on a CUDA GPU: Kerr black hole tails”, Journal of Scientific Computing, 56:2 (2013), pp. 366-380.
- DOI: 10.1007/s10915-012-9679-3
- L. Yang, D. Ma, A. Ebrahim, C. J. Lloyd, M. A. Saunders, B. O. Palsson. “solveME: fast and reliable solution of nonlinear ME models”, BMC bioinformatics, 17:1 (2016), 391.
- DOI: 10.1186/s12859-016-1240-1
- M. Fasi, N. J. Higham. “Multiprecision algorithms for computing the matrix logarithm”, SIAM Journal on Matrix Analysis and Applications, 39:1 (2018), pp. 472-491.
- DOI: 10.1137/17M1129866
- R. Iakymchuk, D. Defour, S. Collange, S. Graillat. “Reproducible and accurate matrix multiplication”, SCAN 2015: Scientific Computing, Computer Arithmetic, and Validated Numerics, Lecture Notes in Computer Science, vol. 9553, Springer, 2015, pp. 126-137.
- DOI: 10.1007/978-3-319-31769-4_11
- M. Cornea. “Precision, accuracy, rounding, and error propagation in exascale computing”, 2013 IEEE 21st Symposium on Computer Arithmetic (7-10 April 2013, Austin, TX, USA), pp. 231-234.
- DOI: 10.1109/ARITH.2013.42
- К. С. Исупов, В. С. Князьков. «Арифметика многократной точности на основе систем остаточных классов», Программные системы: теория и приложения, 7:1 (2016), с. 61-97.
- DOI: 10.25209/2079-3316-2016-7-1-61-97
- K. Isupov, V. Knyazkov. “A modular-positional computation technique for multiple-precision floating-point arithmetic”, PaCT 2015: Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 9251, Springer, 2015, pp. 47-61.
- DOI: 10.1007/978-3-319-21909-7_5
- N. Nakasato, H. Daisaka, T. Fukushige, A. Kawai, J. Makino, T. Ishikawa, F. Yuasa. “GRAPE-MPs: Implementation of an SIMD for quadruple/hexuple/octuple-precision arithmetic operation on a structured ASIC and an FPGA”, 2012 IEEE 6th International Symposium on Embedded Multicore SoCs (20-22 Sept. 2012, Aizu-Wakamatsu, Japan), 2012, pp. 75-83.
- DOI: 10.1109/MCSoC.2012.31
- H. Daisaka, N. Nakasato, T. Ishikawa, F. Yuasa. “Application of GRAPE9-MPX for high precision calculation in particle physics and performance results”, Procedia Computer Science, 51 (2015), pp. 1323-1332.
- DOI: 10.1016/j.procs.2015.05.317
- E. El-Araby, I. Gonzalez, T. A El-Ghazawi. “Bringing high-performance reconfigurable computing to exact computations”, 2007 International Conference on Field Programmable Logic and Applications (27-29 Aug. 2007, Amsterdam, Netherlands), 2007, pp. 79-85.
- DOI: 10.1109/FPL.2007.4380629
- Y. Lei, Y. Dou, J. Zhou. “FPGA-specific custom VLIW architecture for arbitrary precision floating-point arithmetic”, IEICE Transactions on Information and Systems, E94.D:11 (2011), pp. 2173-2183.
- DOI: 10.1587/transinf.E94.D.2173
- M. Ishii, J. Detrey, P. Gaudry, A. Inomata, K. Fujikawa. “Fast modular arithmetic on the Kalray MPPA-256 processor for an energy-efficient implementation of ECM”, IEEE Transactions on Computers, 66:12 (2017), pp. 2019-2030.
- DOI: 10.1109/TC.2017.2704082
- M. J. Schulte, E. E. Swartzlander. “A family of variable-precision interval arithmetic processors”, IEEE Transactions on Computers, 49:5 (2000), pp. 387-397.
- DOI: 10.1109/12.859535
- B. Pan, Y. Wang, S. Tian. “A high-precision single shooting method for solving hypersensitive optimal control problems”, Mathematical Problems in Engineering, 2018 (2018), 7908378, 11 pp.
- DOI: 10.1155/2018/7908378
- I. V. Grossu, C. Besliu, D. Felea, A. Jipa. “High precision framework for chaos many-body engine”, Computer Physics Communications, 185:4 (2014), pp. 1339-1342.
- DOI: 10.1016/j.cpc.2013.12.024
- V. Nehra, R. Sehgal. “Symbolic computation of mathematical transforms and its application: A MATLAB computational project-based approach”, IUP Journal of Electrical and Electronics Engineering, 8:1 (2015), pp. 53-76.
- M. A. Agwa, A. P. Da Costa. “Using symbolic computation in the characterization of frictional instabilities involving orthotropic materials”, International Journal of Applied Mathematics and Computer Science, 25:2 (2015), pp. 259-267.
- DOI: 10.1515/amcs-2015-0020
- E. Dovlo, N. Baddour. “Building a symbolic computer algebra toolbox to compute 2D Fourier transforms in polar coordinates”, MethodsX, 2 (2015), pp. 192-197.
- DOI: 10.1016/j.mex.2015.03.008
- J. G. Liu, Z. F. Zeng. “Extended generalized hyperbolic-function method and new exact solutions of the generalized hamiltonian and NNV equations by the symbolic computation”, Fundamenta Informaticae, 132:4 (2014), pp. 501-517.
- DOI: 10.3233/FI-2014-1056
- S. Asif, Y. Kong. “Highly parallel modular multiplier for elliptic curve cryptography in residue number system”, Circuits, Systems, and Signal Processing, 36:3 (2017), pp. 1027-1051.
- DOI: 10.1007/s00034-016-0336-1
- Y. Li, J. Wang, X. Zeng, X. Ye. “Fast Montgomery modular multiplication and squaring on embedded processors”, IEICE Transactions on Communications, 100:5 (2017), pp. 680-690.
- DOI: 10.1587/transcom.2016EBP3189
- J.-C. Bajard, L. Imbert. “A full RNS implementation of RSA”, IEEE Transactions on Computers, 53:6 (2004), pp. 769-774.
- DOI: 10.1109/TC.2004.2
- S. Antao, J. C. Bajard, L. Sousa. “RNS-based elliptic curve point multiplication for massive parallel architectures”, The Computer Journal, 55:5 (2011), pp. 629-647.
- DOI: 10.1093/comjnl/bxr119
- O. Harrison, J. Waldron. “Efficient acceleration of asymmetric cryptography on graphics hardware”, AFRICACRYPT 2009: Progress in Cryptology - AFRICACRYPT 2009, Lecture Notes in Computer Science, vol. 5580, Springer, 2009, pp. 350-367.
- DOI: 10.1007/978-3-642-02384-2_22
- K. Bigou, A. Tisserand. “Single base modular multiplication for efficient hardware RNS implementations of ECC”, CHES 2015: Cryptographic Hardware and Embedded Systems - CHES 2015, Lecture Notes in Computer Science, vol. 9293, Springer, 2015, pp. 123-140.
- DOI: 10.1007/978-3-662-48324-4_7
- S. Asif, M. S. Hossain, Y. Kong, W. Abdul. “A fully RNS based ECC processor”, Integration, 61 (2018), pp. 138-149.
- DOI: 10.1016/j.vlsi.2017.11.010
- Н. Н. Непейвода. «Использование локализации и переполнения для управления параллельными и распределёнными вычислениями», Программные системы: теория и приложения, 8:3 (2017), с. 87-107.
- DOI: 10.25209/2079-3316-2017-8-3-87-107
- N. I. Chervyakov, P. A. Lyakhov, M. G. Babenko, I. N. Lavrinenko, A. V. Lavrinenko, A. S. Nazarov. “The architecture of a fault-tolerant modular neurocomputer based on modular number projections”, Neurocomputing, 272 (2018), pp. 96-107.
- DOI: 10.1016/j.neucom.2017.06.063
- М. Г. Бабенко, А. Н. Черных, Н. И. Червяков, В. А. Кучуков, В. Миранда-Лопес, Р. Ривера-Родригес, Чж. Ду. «Эффективное сравнение чисел в системе остаточных классов на основе позиционной характеристики», Труды ИСП РАН, 31:2 (2019), с. 187-202.
- DOI: 10.15514/ISPRAS-2019-31(2)-13
- D. V. Telpukhov, R. A. Solovyev, V.M. Amerbaev, E.S. Balaka. «Hardware implementation of FIR filter based on number-theoretic fast Fourier transform in residue number system», Проблемы разработки перспективных микро-и наноэлектронных систем (МЭС), 2015, №4, с. 42-42 (in English).
- N. Revol. “Introduction to the IEEE 1788-2015 standard for interval arithmetic”, NSV 2017: Numerical Software Verification, Lecture Notes in Computer Science, vol. 10381, Springer, 2017, pp. 14-21.
- DOI: 10.1007/978-3-319-63501-9_2
- F. Johansson. “Arb: efficient arbitrary-precision midpoint-radius interval arithmetic”, IEEE Transactions on Computers, 66:8 (2017), pp. 1281-1292.
- DOI: 10.1109/TC.2017.2690633
- 1788-2015 IEEE Standard for Interval Arithmetic, 2015 URL https://standards.ieee.org/standard/1788-2015.html.
- N. Revol, Ph. Theveny. “Numerical reproducibility and parallel computations: Issues for interval algorithms”, IEEE Transactions on Computers, 63:8 (2014), pp. 1915-1924.
- DOI: 10.1109/TC.2014.2322593
- M. G. Arnold, J. Garcia, M. J. Schulte. “The interval logarithmic number system” (15-18 June 2003, Santiago de Compostela, Spain), pp. 253-261.
- DOI: 10.1109/ARITH.2003.1207686
- U. Lotri P. Bulić. “Logarithmic arithmetic for low-power adaptive control systems”, Circuits, Systems, and Signal Processing, 36:9 (2017), pp. 3564-3584.
- DOI: 10.1007/s00034-016-0486-1
- U. Lotri P. Bulić. “Applicability of approximate multipliers in hardware neural networks”, Neurocomputing, 96 (2012), pp. 57-65.
- DOI: 10.1016/j.neucom.2011.09.039
- M. S. Kim, A. A Del Barrio, R. Hermida, N. Bagherzadeh. “Low-power implementation of Mitchell's approximate logarithmic multiplication for convolutional neural networks”, 2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC) (22-25 Jan. 2018, Jeju, South Korea), pp. 617-622.
- DOI: 10.1109/ASPDAC.2018.8297391
- H. Kim, B.-G. Nam, J.-H. Sohn, J.-H. Woo, H.-J. Yoo. “A 231-MHz, 2.18-mW 32-bit logarithmic arithmetic unit for fixed-point 3-D graphics system”, IEEE Journal of Solid-State Circuits, 41:11 (2006), pp. 2373-2381.
- DOI: 10.1109/JSSC.2006.882887
- A. Avramovć, Z. Babić, D. Rai D. Strle, P. Bulić. “An approximate logarithmic squaring circuit with error compensation for DSP applications”, Microelectronics Journal, 45:3 (2014), pp. 263-271.
- DOI: 10.1016/j.mejo.2014.01.005
- M. Gautschi, M. Schaffner, F. K. Gürkaynak, L. Benini. “An extended shared logarithmic unit for nonlinear function kernel acceleration in a 65-nm CMOS multicore cluster”, IEEE Journal of Solid-State Circuits, 52:1 (2017), pp. 98-112.
- DOI: 10.1109/JSSC.2016.2626272
- D. Nandan, J. Kanungo, A. Mahajan. “An error-efficient gaussian filter for image processing by using the expanded operand decomposition logarithm multiplication”, Journal of Ambient Intelligence and Humanized Computing, 2018, pp. 1-8.
- DOI: 10.1007/s12652-018-0933-x
- J. Coleman, R C. Ismail. “LNS with co-transformation competes with floating-point”, IEEE Transactions on Computers, 65:1 (2016), pp. 136-146.
- DOI: 10.1109/TC.2015.2409059
- J. Le Maire, N. Brunie, F. De Dinechin, J. M. Muller. “Computing floating-point logarithms with fixed-point operations”, 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH) (10-13 July 2016, Santa Clara, CA, USA), pp. 156-163.
- DOI: 10.1109/ARITH.2016.24
- H. Fu, O. Mencer, W. Luk. “Comparing floating-point and logarithmic number representations for reconfigurable acceleration”, 2006 IEEE International Conference on Field Programmable Technology (13-15 Dec. 2006, Bangkok, Thailand), pp. 337-340.
- DOI: 10.1109/FPT.2006.270342
- M. Chugh, B. Parhami. “Logarithmic arithmetic as an alternative to floating-point: A review”, 2013 Asilomar Conference on Signals, Systems and Computers (3-6 Nov. 2013, Pacific Grove, CA, USA), 2013, pp. 1139-1143.
- DOI: 10.1109/ACSSC.2013.6810472
- M. Haselman, M. Beauchamp, A. Wood, S. Hauck, K. Underwood, K. S. Hemmert. “A comparison of floating point and logarithmic number systems for FPGAs”, 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'05) (18-20 April 2005, Napa, CA, USA, USA), pp. 181-190.
- DOI: 10.1109/FCCM.2005.6
- R. C. Ismail, J. N. Coleman, N. Norzahiyah, Z. Sauli. “A comparative analysis between logarithmic number system and floating-point ALU”, Advances in Environmental Biology, 7:12 (2013), pp. 3601-3606.
- M. G. Arnold. “Iterative methods for logarithmic subtraction”, ASAP 2003 (24-26 June 2003, The Hague, Netherlands), pp. 315-325.
- DOI: 10.1109/ASAP.2003.1212855
- A. R. Omondi, B. Premkumar. Residue Number Systems: Theory and Implementation, Advances in Computer Science and Engineering Texts, World Scientific, 2007, , 296 pp.
- ISBN: 978-1860948664
- N. S. Szabo, R. I. Tanaka. Residue Arithmetic and its Applications to Computer Technology, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill, 1967, 236 pp.
- И. Я. Акушский, Д. И. Юдицкий. Машинная арифметика в остаточных классах, Сов. радио, М., 1968, 440 с.
- K. Bigou, A. Tisserand. “RNS modular multiplication through reduced base extensions”, 2014 IEEE 25th International Conference on Application-Specific Systems, Architectures and Processors (18-20 June 2014, Zurich, Switzerland), pp. 57-62.
- DOI: 10.1109/ASAP.2014.6868631
- J. C. Bajard, J. Eynard, N. Merkiche. “Montgomery reduction within the context of residue number system arithmetic”, Journal of Cryptographic Engineering, 8:3 (2018), pp. 189-200.
- DOI: 10.1007/s13389-017-0154-9
- M. Langhammer, B. Pasca. “Single precision natural logarithm architecture for hard floating-point and DSP-enabled FPGAs”, 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH) (10-13 July 2016, Santa Clara, CA, USA), pp. 164-171.
- DOI: 10.1109/ARITH.2016.20
- 754-2008 - IEEE Standard for Floating-Point Arithmetic, IEEE, 2008 URL
- DOI: 10.1109/IEEESTD.2008.4610935
- M. Cornea, J. Harrison, P. T. P. Tang. Scientific Computing on Itanium-Based Systems, Intel Press, Hillsboro, 2002, , 280 pp.
- ISBN: 978-0971288775
- M. Czyzak, R. Smyk, Z. Ulman. “Pipelined scaling of signed residue numbers with the mixed-radix conversion in the programmable gate array”, Poznan University of Technology Academic Journals. Electrical Engineering, 2013, no.76, pp. 89-99.
- A. P. Shenoy, R. Kumaresan. “Fast base extension using a redundant modulus in RNS”, IEEE Transactions on Computers, 38:2 (1989), pp. 292-297.
- DOI: 10.1109/12.16508
- S. Kawamura, M. Koike, F. Sano, A. Shimbo. “Cox-Rower architecture for fast parallel Montgomery multiplication”, EUROCRYPT 2000: Advances in Cryptology - EUROCRYPT 2000, Lecture Notes in Computer Science, vol. 1807, Springer, 2000, pp. 523-538.
- DOI: 10.1007/3-540-45539-6_37
- K. C. Posch, R. Posch. “Base extension using a convolution sum in residue number systems”, Computing, 50:2 (1993), pp. 93-104.
- DOI: 10.1007/BF02238608
- А. С. Коржавина, В. С. Князьков. «Методы расширения базиса в системе остаточных классов: обзор и анализ вычислительной сложности», Современные наукоемкие технологии, 2017, №12, с. 37-42.
- А. С. Коржавина, В. С. Князьков. «Метод расширения базиса систем остаточных классов с применением систем счисления со смешанными основаниями», Научно-технический вестник Поволжья, 2017, №6, с. 204-207.
- G. A. Jullien. “Residue number scaling and other operations using ROM arrays”, IEEE Transactions on Computers, C-27:4 (1978), pp. 325-336.
- DOI: 10.1109/TC.1978.1675105
- Y. Kong, B. Phillips. “Fast scaling in the residue number system”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 17:3 (2009), pp. 443-447.
- DOI: 10.1109/TVLSI.2008.2004550
- S. Ma, J. Hu, Y. Ye, L. Zhang, X. Ling. “A 2ⁿ scaling scheme for signed RNS integers and its VLSI implementation”, Science in China Series F: Information Sciences, 53:1 (2010), pp. 203-212.
- DOI: 10.1007/s11432-010-0015-y
- C. H. Chang, J. Y. S. Low. “Simple, fast, and exact RNS scaler for the three-moduli set three-moduli set 2ⁿ-1,2ⁿ,2ⁿ1”, IEEE Transactions on Circuits and Systems I: Regular Papers, 58:11 (2011), pp. 2686-2697.
- DOI: 10.1109/TCSI.2011.2142950
- A. Hiasat. “Efficient RNS scalers for the extended three-moduli set 2ⁿ-1,2^np,2ⁿ1”, IEEE Transactions on Computers, 66:7 (2017), pp. 1253-1260.
- DOI: 10.1109/TC.2017.2652474
- А. С. Коржавина, В. С. Князьков. Способ организации выполнения операции умножения двух чисел в модулярно-логарифмическом формате представления с плавающей точкой на гибридных многоядерных процессорах, 2018.