Sign In

Communications of the ACM

121 - 130 of 164 for bentley

How to print floating-point numbers accurately

We present algorithms for accurately converting floating-point numbers to decimal representation. The key idea is to carry along with the computation an explicit representation of the required rounding accuracy. We begin with the simpler problem of converting fixed-point fractions. A modification of the well-known algorithm for radix-conversion of fixed-point fractions by multiplication explicitly determines when to terminate the conversion process; a variable number of digits are produced. The algorithm has these properties: No information is lost; the original fraction can be recovered from the output by rounding. No “garbage digits” are produced. The output is correctly rounded. It is never necessary to propagate carries on rounding. We then derive two algorithms for free-formal output of floating-point numbers. The first simply scales the given floating-point number to an appropriate fractional range and then applies the algorithm for fractions. This is quite fast and simple to code but has inaccuracies stemming from round-off errors and oversimplification. The second algorithm guarantees mathematical accuracy by using multiple-precision integer arithmetic and handling special cases. Both algorithms produce no more digits than necessary (intuitively, the “1.3 prints as 1.2999999” problem does not occur). Finally, we modify the free-format conversion algorithm for use in fixed-format applications. Information may be lost if the fixed format provides too few digit positions, but the output is always correctly rounded. On the other hand, no “garbage digits” are ever produced, even if the fixed format specifies too many digit positions (intuitively, the “4/3 prints as 1.333333328366279602” problem does not occur).


K-d trees for semidynamic point sets

A K-d tree represents a set of N points in K-dimensional space. Operations on a semidynamic tree may delete and undelete points, but may not insert new points. This paper shows that several operations that require &Ogr;(log N) expected time in general K-d trees may be performed in constant expected time in semidynamic trees. These operations include deletion, undeletion, nearest neighbor searching, and fixed-radius near neighbor searching (the running times of the first two are proved, while the last two are supported by experiments and heuristic arguments). Other new techniques can also be applied to general K-d trees: simple sampling reduces the time to build a tree from &Ogr;(KN log N) to &Ogr;(KN + N log N), and more advanced sampling builds a robust tree in the same time. The methods are straightforward to implement, and lead to a data structure that is significantly faster and less vulnerable to pathological inputs than ordinary K-d trees.