The algorithm that computes the midpoint of an interval with floating-point bounds requires some careful devising to handle all possible inputs correctly. We review several implementations from prominent C/C++ interval arithmetic packages and analyze their potential failure to deliver the expected results. We then show how to amend them to avoid common pitfalls. The results presented are also relevant to noninterval arithmetic computation such as the implementation of bisection methods. Enough background on IEEE 754 floating-point arithmetic is provided for this article to serve as a practical introduction to the analysis of floating-point computation.

Numerical methods based on interval arithmetic are efficient means to reliably solve nonlinear systems of equations. Algorithm bc3revise is an interval method that tightens variables' domains by enforcing a property called box consistency. It has been successfully used on difficult problems whose solving eluded traditional numerical methods.We present a new algorithm to enforce box consistency that is simpler than bc3revise, faster, and easily data parallelizable. A parallel implementation with Intel SSE2 SIMD instructions shows that an increase in performance of up to an order of magnitude and more is achievable.

Many problems in robust control and motion planning can be reduced to either finding a sound approximation of the solution space determined by a set of nonlinear inequalities, or to the "guaranteed tuning problem" as defined by Jaulin and Walter, which amounts to finding a value for some tuning parameter such that a set of inequalities be verified for all the possible values of some perturbation vector. A classical approach to solving these problems, which satisfies the strong soundness requirement, involves some quantifier elimination procedure such as Collins' Cylindrical Algebraic Decomposition symbolic method. Sound numerical methods using interval arithmetic and local consistency enforcement to prune the search space are presented in this article as much faster alternatives for both soundly solving systems of nonlinear inequalities, and addressing the guaranteed tuning problem whenever the perturbation vector has dimension 1. The use of these methods in camera control is investigated, and experiments with the prototype of a declarative modeler to express camera motion using a cinematic language are reported and commented upon.

Interval constraint solvers use local consistencies-among which one worth mentioning is box consistency-for computing verified solutions of real constraint systems. Though among the most efficient ones, the algorithm for enforcing box consistency suffers from the use of time-consuming operators. This paper first introduces box/sub /spl phi// consistency, a weakening of box consistency; this new notion then allows us to devise an adaptive algorithm that computes box consistency by enforcing box/sub /spl phi// consistency, decreasing the /spl phi/ parameter as variables' domains get tightened, then achieving eventually box/sub 0/ consistency, which is equivalent to box consistency. A new propagation algorithm is also given, that intensifies the use of the most contracting pruning functions based on box/spl phi/ consistency. The resulting algorithm is finally shown to outperform the original scheme for enforcing box consistency on a set of standard benchmarks.

Constraint programming is an emerging technology that offers an original approach allowing for efficient and flexible solving of complex problems. Its main advantage relies in its ability to compute with partial information expressed in terms of constraints. These constraints are monotonically, accumulated during the program execution in order to restrict the problem search space. We address one of the cornerstones of this technology, namely the current lack of debugging facilities. In particular visualization and understanding of the underlying constraint system during program executions is very important. We propose to structure this huge, flat and intricate part of the execution data in order to provide access to high level examination of its evolution. More precisely, we present a means to hierarchically organize sets of constraints in order to divide them into manageable parts while presenting computation correctness. Soundness of our method is shown, an algorithm supporting it is given, and an implemented prototype exhibiting its effectiveness is described.