Exact computation of the sign of a finite sum

Many geometric algorithms are dependent on the sign of a simple expression like a finite sum. Examples of such algorithms are left turn test, orientat ion questions, Boolean algorithms (point in circle versus not in circle), e tc. Implementing such algorithms in fixed length floating-point arithmetic can lead to inaccurate or wrong geometric configurations due to falsificati on of the computation by rounding errors. In this paper we present an algor ithm for determining the sign of a sum of a finite set of real numbers. The result is exact, i.e., the computation is free of rounding errors, when th e real numbers are machine numbers. The algorithm is extremely simple, only computation with fixed word-length is required (for example, single precis ion floating-point arithmetic), no splitting or other mantissa manipulation s are necessary, one only needs to know the exponential parts of the repres ented summands, and it is almost never necessary to compute the value of th e whole sum, (C) 1999 Published by Elsevier Science Inc. All rights reserve d.