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, orientation questions, Boolean algorithms (point in circle versus not in circle), etc. Implementing such algorithms in fixed length floating-point arithmetic can lead to inaccurate or wrong geometric configurations due to falsification of the computation by rounding errors. In this paper we present an algorithm 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 the real numbers are machine numbers. The algorithm is extremely simple, only computation with fixed word-length is required (for example, single precision floating-point arithmetic), no splitting or other mantissa manipulations are necessary, one only needs to know the exponential parts of the represented summands, and it is almost never necessary to compute the value of the whole sum.