Abstract
Exact rounding of numbers and functions is a fundamental computational problem. This paper introduces the mathematical and computational foundations for exact rounding. We show that all the elementary functions in ISO standard (ISO/IEC 10967) for Language Independent Arithmetic can be exactly rounded, in any format, and to any precision. Moreover, a priori complexity bounds can be given for these rounding problems. Our conclusions are derived from results in transcendental number theory.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brent, R.P.: Fast multiple-precision evaluation of elementary functions. J. of the ACM 23, 242–251 (1976)
Brönnimann, H., Burnikel, C., Pion, S.: Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics 109(1-2), 25–47 (2001)
Defour, D., Hanrot, G., Lefèvre, V., Muller, J.-M., Revol, N., Zimmermann, P.: Proposal for a standardization of mathematical function implementation in floating-point arithmetic. Numerical Algorithms 37(1-4), 367–375 (2004)
Du, Z.: Guaranteed Precision for Transcendental and Algebraic Computation made Easy. Ph.D. thesis, New York University, Department of Computer Science, Courant Institute (May 2006), http://cs.nyu.edu/exact/doc/
Du, Z., Eleftheriou, M., Moreira, J., Yap, C.: Hypergeometric functions in exact geometric computation. In: Brattka, V., Schoeder, M., Weihrauch, K. (eds.) Proc. 5th Workshop on Computability and Complexity in Analysis, Malaga, Spain, July 12–13. Electronic Notes in Theoretical Computer Science, vol. 66(1), pp. 55–66 (2002), http://www.elsevier.nl/locate/entcs/volume66.html
Du, Z., Yap, C.: Uniform complexity of approximating hypergeometric functions with absolute error. In: Pae, S., Park, H. (eds.) Proc. 7th Asian Symp. on Computer Math. (ASCM 2005), pp. 246–249 (2006)
Fel’dman, N., Nesterenko, Y.V.: Number Theory IV: Transcendental Numbers. Encyclopaedia of Mathematical Sciences, vol. 44. Springer, Berlin (1998); translated from Russian by N. Koblitz
Fousse, L., Hanrot, G., Lefévre, V., Pélissier, P., Zimmermann, P.: Mpfr: A multiple-precision binary floating-point library with correct rounding. ACM Trans. Math. Softw. 33(2), 13 (2007)
Gal, S., Bachelis, B.: An accurate elementary mathematical library for the IEEE floating point standard. ACM Trans. on Math. Software 17(1), 26–45 (1991)
Goldberg, D.: What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys 23(1), 5–48 (1991)
IEEE. ANSI/IEEE Standard 754-1985 for binary floating-point arithmetic, The Institute of Electrical and Electronic Engineers Inc., New York (1985)
Ko, K.-I.: Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston (1991)
Lefévre, V., Muller, J.-M., Tisserand, A.: Towards correctly rounded transcendentals. IEEE Trans. Computers 47(11), 1235–1243 (1998)
Lefèvre, V., Stehlé, D., Zimmermann, P.: Worst cases for the exponential function in the IEEE 754r decimal64 format. In: Hertling, P., Hoffmann, C.M., Luther, W., Revol, N. (eds.) Real Number Algorithms. LNCS, vol. 5045, pp. 114–126. Springer, Heidelberg (2008)
Li, C., Pion, S., Yap, C.: Recent progress in Exact Geometric Computation. J. of Logic and Algebraic Programming 64(1), 85–111 (2004); special issue on “Practical Development of Exact Real Number Computation”
Muller, J.-M.: Elementary Functions: Algorithms and Implementation. Birkhäuser, Boston (1997)
Nesterenko, Y., Waldschmidt, M.: On the approximation of the values of exponential function and logarithm by algebraic numbers. Mat. Zapiski 2, 23–42 (1996); Diophantine Approximations, Proc. of papers dedicated to the memory of Prof. N.I. Feldman, Moscow, http://arxiv.org/abs/math.NT/0002047
I. S. O. ISO/IEC 10967-2-2001 for Language Independne Arithmetic: Elementary Numerical Functions. International Standards Organisation, Geneva, Switzerland (2001)
Richardson, D.: How to recognize zero. J. of Symbolic Computation 24, 627–645 (1997)
Sharma, V., Du, Z., Yap, C.: Robust approximate zeros. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 874–887. Springer, Heidelberg (2005)
Yap, C.K.: Fundamental Problems of Algorithmic Algebra. Oxford University Press, Oxford (2000)
Yap, C.K.: On guaranteed accuracy computation. In: Chen, F., Wang, D. (eds.) Geometric Computation, ch. 12, pp. 322–373. World Scientific Publishing Co., Singapore (2004)
Yap, C.K.: Robust geometric computation. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., ch. 41, pp. 927–952. Chapman & Hall/CRC, Boca Raton (2004)
Yap, C.K.: Theory of real computation according to EGC. In: Hertling, P., Hoffmann, C.M., Luther, W., Revol, N. (eds.) Real Number Algorithms. LNCS, vol. 5045, pp. 193–237. Springer, Heidelberg (2008)
Ziv, A.: Fast evaluation of elementary mathematical functions with correctly rounded last bit. ACM Trans. on Math. Software 17(3), 410–423 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yap, C.K., Yu, J. (2009). Foundations of Exact Rounding. In: Das, S., Uehara, R. (eds) WALCOM: Algorithms and Computation. WALCOM 2009. Lecture Notes in Computer Science, vol 5431. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00202-1_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-00202-1_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00201-4
Online ISBN: 978-3-642-00202-1
eBook Packages: Computer ScienceComputer Science (R0)