Exact computation of the sign of a finite sum

Citation
H. Ratschek et J. Rokne, Exact computation of the sign of a finite sum, APPL MATH C, 99(2-3), 1999, pp. 99-127
Citations number
22
Categorie Soggetti
Engineering Mathematics
Journal title
APPLIED MATHEMATICS AND COMPUTATION
ISSN journal
00963003 → ACNP
Volume
99
Issue
2-3
Year of publication
1999
Pages
99 - 127
Database
ISI
SICI code
0096-3003(19990315)99:2-3<99:ECOTSO>2.0.ZU;2-J
Abstract
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.