Adaptive precision floating-point arithmetic and fast robust geometric predicates

Abstract Exact computer arithmetic has a variety of uses, including the robust implementation of geometric algorithms. Thisarticle has three purposes. The first is to offer fast software-level algorithms for exact addition and multiplication of arbitrary precision floating-point values. The second is to propose a technique for adaptive precision arithmetic thatcan often speed these algorithms when one wishes to perform multiprecision calculations that do not always require exact arithmetic, but must satisfy some error bound. The third is to use these techniques to develop implementationsof several common geometric calculations whose required degree of accuracy depends on their inputs. These robust geometric predicates are adaptive; their running time depends on the degree of uncertainty of the result, and is usuallysmall