Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k -th root operations for integral k , and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real .

We show that the combination of the CGAL framework for geometric computation and the number type ledareal yields easy-to-write, correct and efficient geometric programs.

International audience

In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision packages, we develop an easy-to-use expression compiler called EXPCOMP. EXPCOMP supports all common operations +; \\Gamma; \\Delta; =; p . Applying a new semi-static filter, EXPCOMP combines the speed of static filters with the power of dynamic filters. The filter stages deal with all kinds of floating-point exceptions, including underflow. The resulting programs show a very good runtime behaviour. 1 Introduction When computer scientists design geometric algorithms, they usually assume the availability of exact arithmetic on real numbers. Since no computer directly provides exact arithmetic on real numbers, programmers implementing these algorithms must find some substitution. Quite commonly, they resort to floating-point arithmetic due to its support by hardand software as well as its co...

No abstract available.