stillwater-sc / universal / 26341266844

84%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

fix(ereal): port Priest canonical renormalize to fix associativity (#961)

Resolves the associativity-on-random-multi-limb-inputs bug surfaced by
the fuzzer in PR #958. Root cause documented in #959: the prior
renormalize_expansion used grow_expansion sequentially, producing a
non-overlapping but order-dependent output. Two expressions with the
same real value could renormalize to different limb sequences, and
compare_adaptive's limb-by-limb test reported them unequal -- breaking
associativity for ~0.5% of random multi-limb pairs.

Algorithm
- Replace renormalize_expansion's body with a Priest-style canonical
  renormalize: sweepUp (back-to-front cumulative twoSum, residual-first)
  then recurse on the tail, then sweepDown (top-down accumulation), then
  prepend the leading carry. The output is value-canonical: equal-valued
  inputs produce equal limb sequences regardless of how the input was
  built.
- Helpers live in `detail_priest::` namespace inside
  internal/expansion/expansion_ops.hpp:
    sweepUpRec, sweepUp, sweepDownRec, sweepDown, remove_zeros,
    priest_renormalize.
- Algorithm ported from elreal's Phase 4 McCleeary work
  (threeAdd.hpp sweepUp/sweepDown/priestRenorm); same pattern also
  appears in Bailey/Hida's qd Renormalize.

Cost: O(m^2) two_sum calls per renormalize in the worst case. For
ereal<maxlimbs <= 19> this is at most ~190 two_sum calls -- still O(1)
in practice for fixed maxlimbs.

Test updates
- Un-gated the fuzzer associativity check in
  elastic/ereal/arithmetic/addition.cpp (the #if 0 with
  "re-enable when #959 is fixed").

Validation
- gcc 13.3 debug: foundational PASS, fuzz x1k PASS, fuzz x100k PASS,
  fuzz x10M PASS (0 associativity failures across 10M random
  multi-limb triples; previously this saw ~45k failures).

Resolves #959

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

Coverage Stats

56 of 60 new or added lines in 1 file covered. (93.33%)

16 existing lines in 4 files now uncovered.

47176 of 55981 relevant lines covered (84.27%)

5290751.59 hits per line