Abstract
We report on the design and implementation of a number type called Real_algebraic. This number type allows us to compute the sign of arithmetic expressions involving the operations \({+,-,\cdot,/, \sqrt[d]{}}\). The sign computation is always correct and, in this sense, not subject to rounding errors. We focus on modularity and use generic programming techniques to make key parts of the implementation exchangeable. Thus, our design allows for easily performing experiments with different implementations or thereby tailoring the number type for specific tasks. For many problems in computational geometry, instantiations of our number type Real_algebraic are a user-friendly alternative for implementing the exact geometric computation paradigm in order to abandon numerical robustness problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alexandrescu A.: Modern C++ design: generic programming and design patterns applied. Addison-Wesley Longman Publishing Co. Inc., Boston (2001)
boost C++ Libraries. http://www.boost.org/
Burnikel, C., Fleischer, R., Mehlhorn, K., Schirra, S.: Efficient exact geometric computation made easy. In: 15th ACM Symposium on Computational Geometry (SCG’99), pp. 341–350. ACM, New York (1999)
Burnikel C., Funke S., Mehlhorn K., Schirra S., Schmitt S.: A separation bound for real algebraic expressions. Algorithmica 55(1), 14–28 (2009)
CGAL: Computational Geometry Algorithms Library http://www.cgal.org/
Dekker T.J.: A floating-point technique for extending the available precision. Num. Math. 18(2), 224–242 (1971)
Du, Z.: Guaranteed precision for transcendental and algebraic computation made easy. PhD thesis, Courant Institute of Mathematical Sciences, New York University, May 2006
Funke S., Mehlhorn K., Näher S.: Structural filtering: a paradigm for efficient and exact geometric programs. Comput. Geometry 31(3), 179–194 (2005)
Gamma E., Helm R., Johnson R., Vlissides J.: Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading (1995)
GMP: The GNU multiple precision arithmetic library. http://www.gmplib.org/
Kahan W.: Further remarks on reducing truncation errors. Commun. ACM 8(1), 40 (1965)
Karamcheti, V., Li, C., Pechtchanski, I., Yap, C.: A core library for robust numeric and geometric computation. In: 15th ACM Symposium on Computational Geometry (SCG’99), pp. 351–359. ACM, New York (1999)
Knuth D.E.: Seminumerical algorithms. The Art of Computer Programming, vol. 2, 3rd edn. Addison-Wesley, Reading (1997)
LEDA: Library of Efficient Data Structures and Algorithms. http://www.algorithmic-solutions.com/
Li, C., Yap, C.: A new constructive root bound for algebraic expressions. In: SODA ’01: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 496–505, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics (2001)
Mörig, M.: Deferring dag construction by storing sums of floats speeds-up exact decision computations based on expression dags. In: 3rd International Congress on Mathematical Software (ICMS 2010). LNCS, vol. 6327, pp. 109–120, September 2010
Mörig, M., Schirra, S.: On the design and performance of reliable geometric predicates using error-free transformations and exact sign of sum algorithms. In: 19th Canadian Conference on Computational Geometry (CCCG’07), pp. 45–48, August 2007
MPFR: A multiple precision floating-point library. http://www.mpfr.org/
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. Birkhäuser Boston 2010
Ogita T., Rump S.M., Oishi S.: Accurate sum and dot product. SIAM J. Sci. Comput. 26(6), 1955–1988 (2005)
Pion, S., Yap, C.: Constructive root bound for k-ary rational input numbers. In: Proceedings of the 19th ACM Symposium on Computational Geometry, pp. 256–263. ACM Press, San Diego, January 2003
RealAlgebraic: A number type for exact geometric computation. http://www.isg.cs.uni-magdeburg.de/ag/RealAlgebraic/
Schirra, S.: Much Ado about Zero. In: Efficient Algorithms. LNCS, vol. 5760, pp. 408–421, September 2009
Shewchuk J.R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete Comput. Geom. 18(3), 305–363 (1997)
Shewchuk, J.R.: http://www.cs.cmu.edu/~quake/robust.html (1997)
Yap C.: Towards exact geometric computation. Comput. Geom. Theory Appl. 7(1-2), 3–23 (1997)
Yap, C.-K.: Robust geometric computation. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, chap. 41, 2nd edn., pp. 927–952. Chapman & Hall/CRC (2004)
Yu, J., Yap, C., Du, Z., Pion, S., Brönnimann, H.: The design of Core 2: a library for exact numeric computation in geometry and algebra. In: 3rd International Congress on Mathematical Software (ICMS 2010). LNCS, vol. 6327, September 2010
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by DFG grant SCHI 858/1-1.
Rights and permissions
About this article
Cite this article
Mörig, M., Rössling, I. & Schirra, S. On Design and Implementation of a Generic Number Type for Real Algebraic Number Computations Based on Expression Dags. Math.Comput.Sci. 4, 539 (2010). https://doi.org/10.1007/s11786-011-0086-1
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11786-011-0086-1