stillwater-sc / universal / 26486877158

85%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

fix(internal): correct inverted is_nonoverlapping expansion predicate (#999) (#1012)

expansion_ops::is_nonoverlapping used a fast_two_sum error heuristic that was
backwards: for a genuinely non-overlapping pair (a, b) with b below a's ulp,
fast_two_sum returns err == b (the small component passes through unchanged),
and the guard `|err| > |e[i]|*1e-10` then declared an overlap -- the opposite of
the truth. Conversely an overlapping pair like (1.0, 0.5) combines exactly
(err == 0) and was declared non-overlapping.

Reimplement both predicates with the Shewchuk/Priest exponent-gap test (the same
one the verified check_priest_normal oracle uses):
- is_nonoverlapping: |e[i]| <= ulp(e[i-1])/2 == 2^(ilogb(e[i-1]) - 53), with
  finite/zero guards.
- is_strongly_nonoverlapping (was an unused stub forwarding to the broken
  predicate): Shewchuk's strict rule -- non-overlapping, and an adjacent pair
  (ilogb gap of exactly 53) is allowed only when the smaller component is a power
  of two. (For canonical decreasing expansions this coincides with
  non-overlapping, which is expected: Priest-canonical expansions are strongly
  non-overlapping.)

Add regression cases to expansion_ops test_invariants covering the issue's
crafted vectors ({2.0, 2^-60} -> yes, {1.0, 0.5} -> no), the half-ulp boundary,
multi-component, single/empty, and negative-magnitude expansions. These fail
against the old inverted predicate.

is_nonoverlapping has no production call sites (add/multiply use
linear_expansion_sum/renormalize_expansion), so blast radius is limited to this
public predicate and any test relying on it.

Resolves #999

Co-authored-by: Claude Opus 4.7 (1M context) <noreply@anthropic.com>

Coverage Stats

29 of 29 new or added lines in 2 files covered. (100.0%)

6 existing lines in 2 files now uncovered.

46874 of 55795 relevant lines covered (84.01%)

5773562.86 hits per line