Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates
Discrete & Computational Geometry, 1997 · paper · Computer science
Offers fast software algorithms for exact arbitrary-precision floating-point addition and multiplication, plus an adaptive-precision technique. It uses them to build robust geometric predicates, such as orientation and incircle tests, whose running time is usually small.
Checked: PDF from people.eecs.berkeley.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
1 finding
Substance "I found that EXPANSION-SUM runs in 0.83(m + n) − 0.7 microseconds, and FAST-EXPANSION-SUM runs in 0.54mn + 0.6 microseconds" — the two fitted formulas are attached to the wrong procedures.
- p. 22 Section 2.4, first paragraph (p.18)
EXPANSION-SUM runs in 0.83(m + n) − 0.7 microseconds, and FAST-EXPANSION-SUM runs in 0.54mn + 0.6 microseconds
- p. 13 Section 2.4 intro (p.9)
EXPANSION-SUM adds an m-component expansion to an n-component expansion in O(mn) time
- p. 21 Section 2.4, operation counts
EXPANSION-SUM uses mn TWO-SUM operations, for a total of 6mn flops
- p. 13 Section 2.4 opening, p. 9
in O(mn) time. LINEAR-EXPANSION-SUM and FAST-EXPANSION-SUM do the same in O(m + n) time
Judge's note: Images of pages 13, 21 and 22 checked. Page 13 says EXPANSION-SUM is O(mn) and FAST-EXPANSION-SUM is O(m+n). Page 21 gives 6mn flops for EXPANSION-SUM and ~9m+9n−12 for FAST-EXPANSION-SUM, and says 'These estimates correlate well with the measured performance'. The next sentence on page 22, that FAST-EXPANSION-SUM is always faster except when one expansion has one component, holds only with the formulas swapped. As printed, for m=n=10 the 'FAST' procedure would be far slower.
Second check: another model agreed
Report a problem with this finding
7 minor (typos and the like; most checked by the judge only)
Wording Proof of Corollary 9 reads "Exact rounding guarantees that y ≤ ½ulp(x)" and "If y = ½ulp(x)" without absolute values.
- p. 13 Proof of Corollary 9 (p.9)
Exact rounding guarantees that y ≤ ½ulp(x)
Only the authors can say what is right here.
Judge's note: Page 13 image checked: no absolute-value bars appear. Reworking the step: exact rounding gives |y| ≤ ½ulp(x). As printed, y ≤ ½ulp(x) is true but weaker. The case analysis 'strict / y = ½ulp(x)' then leaves out y = −½ulp(x). That case is handled by the same round-to-even argument, so the corollary stands; the step needs |y|. Elsewhere (p.4) the paper itself writes |err(a⊛b)| ≤ ½ulp(a⊛b).
Second check: another model agreed
Report a problem with this finding
Wording Section 4.2 says 'Expression 9 takes about 50% more time than Expression 8', but the Exact (9)/Exact (8) timings in Tables 6 and 7 show increases of about 16–43%.
- p. 41 Section 4.2, paragraph before Figure 20
Expression 9 takes about 50% more time than Expression 8
- p. 49 Table 6, Exact (8) vs Exact (9)
Exact (9) 91.71 118.30 104.44
- p. 50 Table 7, Exact (8) vs Exact (9)
Exact (9) 374.59 480.28 414.13
Only the authors can say what is right here.
Judge's note: Text on p.41 (PDF p.41 crop). Table 6 (INCIRCLE, 2D versions of Expressions 8 and 9) gives ratios of 1.28, 1.43 and 1.39. Table 7 (INSPHERE, Expressions 8 and 9 themselves) gives 1.16, 1.27 and 1.19. None of these reaches 50%. The companion claim of 'roughly 25%' for Expression 7 vs 6 does fit Table 2 (8.35/6.56 = 1.27). The text may rest on a measurement not shown in the paper, so I am raising this as a query to the authors.
Second check: another model agreed
Report a problem with this finding
Wording Text p.45 says 'The timings for the exact versions of all four predicates ... take 5% to 30% longer to execute with geometrically distributed operands', but in Table 2 ORIENT2D Exact (7) goes only from 8.35 to 8.48 µs (about 1.6%).
- p. 49 Section 4.4, paragraph after Table 6 (p.45)
they take 5% to 30% longer to execute with geometrically distributed operands
- p. 46 Table 2, row Exact (7)
8.35
Judge's note: I checked Table 2 (p.42), Table 4 (p.44), Table 6 (p.45) and the sentence that runs from p.44 to p.45 on the page images. The ORIENT2D Exact (7) row reads 8.35 / 8.48, which is below the stated lower bound of 5%. Every other exact row falls between 5.0% and 29%. The captions say individual timings vary by about 10%, so the range is probably meant loosely. That makes this a minor wording point, not a data error.
Second check: another model agreed
Report a problem with this finding
Typo "FAST-EXPANSION-SUM does not always preserve either the nonoverlapping nor the nonadjacent property" pairs 'either' with 'nor'; should be 'either ... or'.
- p. 14 p. 10, first paragraph, first disadvantage
does not always preserve either the nonoverlapping nor the nonadjacent property
- p. 14
preserve either the nonoverlapping nor the nonadjacent property
Judge's note: Confirmed in the page 14 image (p.10, first paragraph). With the negation 'does not', the correct pairing is 'either ... or'. This is a grammatical slip and the meaning is unchanged.
Second check: none (judge only)
Report a problem with this finding
Typo Appendix A LINEAR-EXPANSION-SUM line 1 reads '(possibly with interspersed zeroes)', while FAST-EXPANSION-SUM line 1 and the rest of the paper use 'zeros'.
- p. 55 Appendix A, LINEAR-EXPANSION-SUM line 1
(possibly with interspersed zeroes)
- p. 17 FAST-EXPANSION-SUM line 1
(possibly with interspersed zeros)
Judge's note: The crop of p.55 shows 'zeroes'. A text search finds every other occurrence spelled 'zeros', including the identical phrase on p.17. Both spellings are valid English, so this is only a cosmetic inconsistency.
Second check: none (judge only)
Report a problem with this finding
Typo The COMPRESS proof sketch prints the signed bound 'q ≤ ½ulp(Q)' where a magnitude bound |q| ≤ ½ulp(Q) is meant.
- p. 30 Proof sketch of Theorem 23 (p.26)
q ≤ ½ulp(Q)
Judge's note: Page 26 (PDF p.30) prints 'q ≤ ½ulp(Q)' with no absolute value bars. The neighbouring 'g_{j−1} ≤ ulp(g_j)' also leaves them out. The roundoff term q can be negative, so the bound the argument needs is on |q|. The meaning is clear from context, so this is a cosmetic notation point.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [26] reads 'Pat H. Sterbenz. Floating-Point Computatation.'; 'Computatation' is misspelled and should be 'Computation'.
- p. 59 Reference [26]
Floating-Point Computatation
- p. 59 References, [26]
Floating-Point Computatation.
- p. 59
Floating-Point Computatation. Prentice-Hall, Englewood Cliffs, New Jersey, 1974.
Judge's note: The crop of reference [26] on p.59 shows 'Computatation' in the typeset italic title, so this is not an extraction artefact. It is a misspelling whatever the book's exact title, so no outside knowledge is needed.
Second check: none (judge only)