fix(num): Num.equal/compare report distinct close roots as equal #23

New issue

Closed

opened 2026-07-02 14:03:37 +00:00 by toph · 1 comment

toph commented

2026-07-02 14:03:37 +00:00

Owner

Num.equal/Num.compare decide two distinct algebraic numbers as equal when they lie close together. Repro: among the four real roots of x⁴ − 5x² + ε for ε = 5e-8 are x ≈ +10⁻⁴ and y ≈ −10⁻⁴; Num.equal x y returns true and Num.compare x y returns 0 (must be false / +1). Exact sign determination is the one guarantee the real-algebraic kernel (ADR 0012) exists to provide — everything downstream (incidence checks, solution selection, dedup) leans on it.

Likely cause: comparison decided by an interval/precision cutoff without an exact fallback. Equality should be decided exactly (sign of the difference via the minimal-polynomial machinery), with intervals only as a fast path refined until separation or an exact decision.

Related: Num.real_roots hits a wall as root separation shrinks — 0.07s → 0.39s → 3.47s → timeout (>150s) for ε = 5e-12 … 5e-20 on the same quartic. Root isolation likely needs Descartes/VCA instead of plain bisection.

Stages:

Check in the failing repro as a test (close-roots quartic)
Exact equality/compare with interval fast path
Profile and fix the real_roots isolation wall

`Num.equal`/`Num.compare` decide two *distinct* algebraic numbers as equal when they lie close together. Repro: among the four real roots of x⁴ − 5x² + ε for ε = 5e-8 are x ≈ +10⁻⁴ and y ≈ −10⁻⁴; `Num.equal x y` returns `true` and `Num.compare x y` returns `0` (must be `false` / `+1`). Exact sign determination is the one guarantee the real-algebraic kernel (ADR 0012) exists to provide — everything downstream (incidence checks, solution selection, dedup) leans on it. Likely cause: comparison decided by an interval/precision cutoff without an exact fallback. Equality should be decided exactly (sign of the difference via the minimal-polynomial machinery), with intervals only as a fast path refined until separation or an exact decision. Related: `Num.real_roots` hits a wall as root separation shrinks — 0.07s → 0.39s → 3.47s → timeout (>150s) for ε = 5e-12 … 5e-20 on the same quartic. Root isolation likely needs Descartes/VCA instead of plain bisection. ### Stages: - [ ] Check in the failing repro as a test (close-roots quartic) - [ ] Exact equality/compare with interval fast path - [ ] Profile and fix the `real_roots` isolation wall

toph referenced this issue

2026-07-02 14:03:40 +00:00

research: kernel scaling under repeated cubic folds #33

toph referenced this issue from a commit

2026-07-02 22:08:15 +00:00

docs(spec): exact-kernel design — #23 fixes + D5-style field joins

toph referenced this issue from a commit

2026-07-02 22:08:15 +00:00

docs(plan): exact-kernel slice 1 (#23) implementation plan

toph closed this issue

2026-07-02 22:26:04 +00:00

toph commented

2026-07-02 22:29:54 +00:00

Author

Owner

All three stages landed on main (325bc90..1ae7cac): select_root decides zero via isolating intervals now (the close-roots repro is checked in as a regression test), the rational-root search replaces trial division with a continued-fraction search below the 1/an^2 separation bound, and isolate_roots uses Descartes/VCA instead of Sturm bisection. The e-ladder (5e-8 … 5e-20) runs at <1s per rung, was >150s at the last rung — the final second turned out to be real_roots re-sorting already-ascending roots with exact compare, also removed.

All three stages landed on main (`325bc90..1ae7cac`): `select_root` decides zero via isolating intervals now (the close-roots repro is checked in as a regression test), the rational-root search replaces trial division with a continued-fraction search below the 1/an^2 separation bound, and `isolate_roots` uses Descartes/VCA instead of Sturm bisection. The e-ladder (5e-8 … 5e-20) runs at <1s per rung, was >150s at the last rung — the final second turned out to be `real_roots` re-sorting already-ascending roots with exact compare, also removed.

No labels

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

toph/beloch#23

No description provided.

Rows
Columns