Mathematical model and implementation of rational processing. (English) Zbl 1386.65133
Summary: Precision in computations is a considerable challenge to adequately addressing many current scientific or engineering problems. The way in which the numbers are represented constitutes the first step to compute them and determines the validity of the results. The aim of this research is to provide a formal framework and a set of computational primitives to address high precision problems of mathematical calculation in engineering and numerical simulation. The main contribution of this research is a mathematical model to build an exact arithmetical unit able to represent without error rational numbers in positional notation system. The functions under consideration are addition and multiplication because they form an algebraic commutative ring which contains a multiplicative inverse for every non-zero element. This paper reviews other specialized arithmetic units based on existing formats to show ways to make high precision computing. It is proposed a formal framework of the whole arithmetic architecture in which the operators are based. Then, the design of the addition operation is detailed and its hardware implementation is described. Finally, extensive evaluation of this operator is performed to prove its ability for exact processing.
MSC:
| 65G50 | Roundoff error |
| 65Y04 | Numerical algorithms for computer arithmetic, etc. |
| 68M07 | Mathematical problems of computer architecture |
Keywords:
computer arithmetic; computational methods; exact computation; rational processing; mathematical model; computational efficiencyReferences:
| [2] | Cowlishaw, M., The decNumber C library, IBM Corporation Report (2010) |
| [6] | Schwarz, E. M.; Kapernick, J. S.; Cowlishaw, M. F., Decimal floating-point support on the IBM System z10 processor, IBM J. Res. Dev., 53, 1, 1-10 (2009) |
| [8] | Bergner, P., Performance Optimization and Tuning Techniques for IBM Power Systems Processors Including IBM POWER8 (2015), IBM RedBooks |
| [9] | Sanchez, J. L., An iterative method for improving decimal calculations on computers, Math. Comput. Modelling, 50, 5, 869-878 (2009) · Zbl 1185.68018 |
| [10] | Bailey, David H., High-precision floating-point arithmetic in scientific computation, Comput. Sci. Eng., 7, 3, 54-61 (2005) |
| [11] | Lei, Yuanwu; Dou, Yong; Guo, Lei; Xu, Jinbo; Zhou, Jie; Dong, Yazhuo; Li, Hongjian, VLIW coprocessor for IEEE-754 quadruple-precision elementary functions, ACM Trans. Archit. Code Optim. (TACO), 10, 3, 1-22 (2013) |
| [12] | Kornerup, P.; Matula, D. W., Finite Precision Number Systems and Arithmetic (2010), Cambridge University Press · Zbl 1230.68008 |
| [14] | Piso, D.; Bruguera, J. D., Obtaining accurate error expressions and bounds for floating-point multiplicative algorithms, Comput. J., 2, 57, 319-331 (2014) |
| [15] | Matula, D.; Kornerup, P., Finite precision rational arithmetic: An arithmetic unit, IEEE Trans. Comput., C-32, 378-387 (1983) · Zbl 0515.65042 |
| [17] | Ménissier-Morain, V., Arbitrary precision real arithmetic: design and algorithms, J. Log. Algebr. Program., 64, 13-39 (2005) · Zbl 1080.03042 |
| [18] | Boehm, H. J., Constructive real interpretation of numerical programs, (ACM Conference on Interpreters and Interpretives Techniques (1987), ACM) |
| [20] | Vuillemin, J., Exact real computer arithmetic with continued fractions, IEEE Trans. Comput., 39, 8, 1087-1105 (1990) |
| [22] | Mencer, O., Rational arithmetic units in computer systems (2000), Stanford University, (Ph.D. thesis) |
| [23] | Niqui, M., Exact real arithmetic on the Stern-Brocot tree, J. Discrete Algorithms, 5, 2, 356-379 (2007) · Zbl 1127.68029 |
| [24] | Kazda, A.; Kůrka, P., Representing real numbers in Möbius number systems, (Actes des rencontres du CIRM, 1, No. 1 (2009)), 35-39 · Zbl 1479.37014 |
| [25] | Kůrka, P., Stern-Brocot graph in Möbius number systems, Nonlinearity, 25, 57-72 (2012) · Zbl 1254.54046 |
| [26] | Dawood, H., Theories of Interval Arithmetic: Mathematical Foundations and Applications (2011), LAP LAMBERT Academic Publishing: LAP LAMBERT Academic Publishing Saarbrücken |
| [27] | Krka, P., Exact real arithmetic for interval number systems, Theoret. Comput. Sci., 542, 32-43 (2014) · Zbl 1360.65138 |
| [28] | Bruguera, J. D., Optimizing the representation of intervals, Sci. Comput. Program., 90, A, 21-33 (2014) |
| [29] | Žilinskas, J., Comparison of packages for interval arithmetic, Informatica, 16, 1, 145-154 (2005) · Zbl 1082.65048 |
| [30] | Schulte, M. J., A family of variable-precision interval arithmetic processors, IEEE Trans. Comput., 49, 5, 1-11 (2000) |
| [31] | Von Gudenberg, J. W., Interval arithmetic on multimedia architectures, Reliab. Comput., 8, 4, 307-312 (2002) · Zbl 0999.65029 |
| [32] | Hormigo, J.; Villalba, J.; Zapata, E. L., CORDIC processor for variable-precision interval arithmetic, J. VLSI Signal Process., 37, 21-39 (2004) |
| [33] | Sukemi, A. G. P.; Putri, RatnaAgung; Sudibyo, H.; Anak, A. P.; Sudibyo, H., Incorporating different bitspaces to create a variable precision processor, Adv. Sci. Lett., 21, 1, 78-82 (2015) |
| [40] | Cohen, M. S.; Hull, T. E.; Hamacher, V. C., CADAC: A controlled-precision decimal arithmetic unit, IEEE Trans. Comput., C-32, 370-377 (1983) · Zbl 0512.65034 |
| [41] | Hsu, C.-Y., Variable precision arithmetic processor in FPGAs (1996), University of Toronto, (Master’s thesis) |
| [42] | Steven, F. L., Addressing mechanisms for VLIW and superscalar processors, Microprocess. Microprogr., 39, 75-78 (1993) |
| [47] | Mora-Mora, H.; Mora-Pascual, J.; Signes-Pont, M. T.; Sánchez-Romero, J. L., Mathematical model of stored logic based computation, Math. Comput. Modelling, 52, 7, 1243-1250 (2010) · Zbl 1205.68024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
