toph/beloch
1
0
Fork 0
Code Issues 15 Pull requests 1 Activity Actions

feat(num): primitive-element tier in real_roots for compositum fields #56

Merged
toph merged 16 commits from worktree-spike+calcium-pe-merge into main 2026-07-04 13:45:35 +00:00
Conversation 0 Commits 16 Files changed 25 +2436 -3
toph commented 2026-07-03 21:23:45 +00:00
Owner
Copy link

Adds a primitive-element tier to Num.real_roots for axiom-6/7 polynomials whose algebraic coefficients span a field — a compositum of independent folds. The tier expresses every coefficient over one generator γ (via FLINT qqbar_express_in_field) and eliminates with a single resultant R = Res_x(μ_γ, F̃) of degree 3·[ℚ(γ):ℚ], then keeps only the candidates that pass the exact eval_p = 0 qqbar check. This replaces, for that case, the old path where FLINT's qqbar root-finder was either slow (~9s) or bailed out to a hopeless degree-3·d³ resultant.

Gated behind the existing FLINT-first fast path. Every failure mode — non-mergeable field, express_in_field bit-limit, degenerate R — falls through to the unchanged Mpoly multi-generator path, so correctness never regresses. FLINT re-verifies res(γ) = x exactly before reporting success, so the precision heuristic can only cause a false None (clean fallback), never a wrong polynomial.

Measured on this branch: a cubic with a single degree-8 coefficient (√(√2+√3)) — ~9s via qqbar-native root-finding in the spike — now solves in ~0.5s. The #33 round-4 tripling-stack case (coefficients over a degree-9 field), previously >300s killed, is estimated at ~0.5–2s — extrapolated from the spike's degree-scaling curve, not yet directly benchmarked. Independent-fold and degree-≥4 cases route through the tier and verify exactly.

Calcium (ca_t) was evaluated as an alternative backend and rejected — it caps out below the status quo. See notes/2026-07-03-calcium-pe-spike.md for the spike and notes/2026-07-03-33-verdict.md for the ceiling analysis.

New surface: Qqbar.express_over, lib/field_merge.ml. Full suite green (beloch-num 51/51, cube-root.bel golden byte-identical).

Note: this branch also carries the throwaway spike probes under scratch/ (normally gitignored, force-committed here as evidence) plus the design spec/plan under docs/superpowers/ — drop before squash-merge if you don't want them in main.

https://claude.ai/code/session_01TinroyhVWz1RBZtXMZoLdd

Adds a primitive-element tier to `Num.real_roots` for axiom-6/7 polynomials whose algebraic coefficients span a field — a compositum of independent folds. The tier expresses every coefficient over one generator γ (via FLINT `qqbar_express_in_field`) and eliminates with a single resultant `R = Res_x(μ_γ, F̃)` of degree `3·[ℚ(γ):ℚ]`, then keeps only the candidates that pass the exact `eval_p = 0` qqbar check. This replaces, for that case, the old path where FLINT's qqbar root-finder was either slow (~9s) or bailed out to a hopeless degree-`3·d³` resultant. Gated behind the existing FLINT-first fast path. Every failure mode — non-mergeable field, `express_in_field` bit-limit, degenerate `R` — falls through to the unchanged Mpoly multi-generator path, so correctness never regresses. FLINT re-verifies `res(γ) = x` exactly before reporting success, so the precision heuristic can only cause a false `None` (clean fallback), never a wrong polynomial. Measured on this branch: a cubic with a single degree-8 coefficient (`√(√2+√3)`) — ~9s via qqbar-native root-finding in the spike — now solves in ~0.5s. The #33 round-4 tripling-stack case (coefficients over a degree-9 field), previously `>300s killed`, is estimated at ~0.5–2s — extrapolated from the spike's degree-scaling curve, not yet directly benchmarked. Independent-fold and degree-≥4 cases route through the tier and verify exactly. Calcium (`ca_t`) was evaluated as an alternative backend and rejected — it caps out below the status quo. See `notes/2026-07-03-calcium-pe-spike.md` for the spike and `notes/2026-07-03-33-verdict.md` for the ceiling analysis. New surface: `Qqbar.express_over`, `lib/field_merge.ml`. Full suite green (beloch-num 51/51, `cube-root.bel` golden byte-identical). Note: this branch also carries the throwaway spike probes under `scratch/` (normally gitignored, force-committed here as evidence) plus the design spec/plan under `docs/superpowers/` — drop before squash-merge if you don't want them in `main`. https://claude.ai/code/session_01TinroyhVWz1RBZtXMZoLdd
toph added 12 commits 2026-07-03 21:23:45 +00:00 
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TinroyhVWz1RBZtXMZoLdd
Benchmark spike (throwaway, not for merge). Findings:
- Calcium ca_poly_roots is weaker than qqbar here: caps at round 3,
  declines irreducible cubics over degree-4 fields (verified not a
  monic/normalization artifact via x^3-2, x^3-sqrt2 sanity).
- Single-generator resultant R=Res(mu_px,F) (degree 3d, not 3d^3) is
  43x faster than qqbar native root-finding at coeff-deg 8 (9.1s->0.21s)
  and solves degrees qqbar rejects. Exact eval_p filter guarantees
  correctness; gate MATCHes qqbar everywhere it succeeds.
- Cracks the #33 round-4 case (>300s -> ~1s est.), ceiling round 3 -> ~5.

Full writeup: notes/2026-07-03-calcium-pe-spike.md

Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TinroyhVWz1RBZtXMZoLdd
Instrumented round 6 (R deg 48): Mpoly.resultant 0.058s, FLINT root
isolation 0.005s, exact eval_p filter 5.400s. The resultant was never
the bottleneck — a faster fmpz_poly resultant buys nothing. The cost is
qqbar high-degree arithmetic in candidate verification (same filter the
current kernel already runs). Real slice needs no new FFI.

Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TinroyhVWz1RBZtXMZoLdd
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TinroyhVWz1RBZtXMZoLdd
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TinroyhVWz1RBZtXMZoLdd
Adds test_real_roots_deep_stack_fast: a cubic with a single
qqbar-degree-8 coefficient (sqrt(sqrt2+sqrt3)), forcing max_deg >= 5
so real_roots skips flint_first and routes through the new pe_tier —
the case the spike measured at ~9s via qqbar-native elimination vs
~0.2s via PE. Measured well under the 2s budget (~0.5s including
Alcotest overhead). Full suite green (51 beloch-num tests incl. the
new one; golden cube-root.bel byte-identical).

The existing Mpoly-routed tests (casus irreducibilis distinct, real
roots two/independent-folds generators) continue to exercise the
Tier-4 fallback whenever pe_tier's gate doesn't fire or merge_generators
returns None, so no new fallback-specific test was added.

Appends the closing verdict update to notes/2026-07-03-33-verdict.md.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01TinroyhVWz1RBZtXMZoLdd
Post-final-review polish (all Minor): the FLINT 3.6 max_bits param is
FLINT_UNUSED — the retry works via prec=4*mb; comments now say so. Add a
note that real_roots' max_deg gate is per-coefficient (perf-only, never
correctness). Comment-only; suite green (51 num tests).
Corpus of rational/quad/independent/deepstack/stacked:N cases through the
real Num.real_roots pipeline, with a public-API stage breakdown
(merge/resultant/roots/filter) to attribute cost per optimization. run.sh
loops the corpus under per-case timeouts and emits a CSV block to diff
before/after a change. Baseline documents the two open targets: the
Mpoly.resultant (stacked:6 10s) and the eval_p filter (deepstack 1.7s).
resultant_superset replaces the general multivariate Mpoly.resultant with
univariate evaluation-interpolation in t: sample R(t_j)=Res_x(mu,F~(t_j,.))
via Poly.resultant, interpolate. Sampled only where F~(t_j) keeps full
formal x-degree, so a vanishing leading coefficient can't corrupt R.

Behavior-preserving (R same up to nonzero constant; root set + exact filter
unchanged), 51/51 green. Measured stacked:6 (coeff-deg 16): resultant
10.08s -> 1.00s, total 15.8s -> 6.8s. field_merge no longer uses Mpoly
(the Tier-4 fallback in num.ml still does). Filter (eval_p) is now the
dominant cost at high degree.
Before the exact eval_p qqbar check, compute a rational-interval enclosure
of P(z) via interval Horner over Qqbar.enclosure. If it excludes 0, z is
provably not a root -> reject without any exact qqbar arithmetic. Rigorous:
a true root (P(z)=0, interval straddles 0) is never rejected; inconclusive
intervals fall through to the exact check. Pure optimization -> identical
root set, 51/51 green (num suite 1.12s -> 0.58s).

Measured: deepstack (6 candidates, 5 extraneous) filter 1.72s -> 0.14s,
total 1.76s -> 0.21s. Negligible on stacked:6 (true roots are the expensive
high-degree evals, not rejectable) -> that residue is intrinsic to exact
confirmation. Bench filter replica mirrors the pre-screen.
One axiom-7 cubic over a clean degree-D generator (2^(1/D)) with the Tier-3
stage breakdown, D = 3^(N-1) modelling a generic fold N. Measured:
field-deg 3 0.014s, 9 0.50s, 27 167s (filter 161s = 97%, single deg-81
true root). This is the honest curve for the 3^N wall: generic interactive
ceiling ~3 folds, fold 4 (deg 27) ~3min, fold 5 out of reach. The exact
eval_p confirmation of a high-degree true root is the dominant cost.
toph merged commit feec9b973d into main 2026-07-04 13:45:35 +00:00
toph deleted branch worktree-spike+calcium-pe-merge 2026-07-04 13:45:36 +00:00
Sign in to join this conversation.
Reviewers
No reviewers
Labels
Clear labels
No items
No labels
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
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!56
No description provided.